java面试题

Question

N个人围成一圈，从第一个人开始数数，数到3的人退出，问：最后剩下的人的第几位？

Answer 1

package com.wayfoon.test;import Java.util.LinkedList;
import Java.util.List;
/**
 * 有M个人，其编号分别为1－M。这M个人按顺序排成一个圈。
 * 现在给定一个数N，从第一个人开始依次报数，数到N的人出列，
 * 然后又从下一个人开始又从1开始依次报数，
 * 数到N的人又出列．．．如此循环，直到最后所有人出列为止。
 * 输出出列轨迹
 *
 */public class Tx
{
    //存放M
    List<String> list = new LinkedList<String>();
    //一圈数数完之后，临时存放出列的人
    List<String> tmp = new LinkedList<String>();    public Tx(int m)
    {
        for (int i = 1; i <= m; i++)
        {
            list.add(i + "");
        }
    }    /**
     * 递归 执行主体
     * @param start
     * @param n
     */
    public void start(int start,int n)
    {
        int size = list.size();
        if (list.size() == 0)
        {
            System.out.println("结束！！");
            return ;
        }
        for (int i = 1; i <= size; i++)
        {
            if ((i + start) % n == 0)
            {
                System.out.println(list.get(i - 1) + " 出局,");
                tmp.add(list.get(i - 1));
            }
        }
        //在m中删除临时队列的人
        for (String str : tmp)
        {
            list.remove(str);
        }
        //清除list
        tmp.clear();
        //递归
        start((size + start) % n,n);
    }    public static void main(String[] args)
    {
        long t1=System.currentTimeMillis();
       
        //M=100
        Tx tx = new Tx(100);
        //n=7
        tx.start(0,7);
       
        System.out.print("花费时间：");
        System.out.println(System.currentTimeMillis()-t1);    }}

Answer 2

int N=... // 假设队列长度用N表示
// 先初始化, list(i)=i+1
List<integer> people = new LinkedList<Intger>;
int skip = 3;
for(int i=0;i<N;i++){
    people.add(i+1);
}int pos = 0;
while(people.size() > 1){
    pos = (pos+skip-1)%people.size();
    int x = people.remove(pos);  //<=== 移出队列
    System.out.println("这次"+x+"被移出队列了");
}
System.out.println("最后剩下"+people.get(0));

Answer 3

public class Test6 {
//num个人围圈，数到num2个人出局
public static void getLeft(int num,int num2){
//定义一个数组标识
boolean[] b = new boolean[num];
//剩余的个数
int leftCount=b.length;
//索引 
int index=0;
//数数
int count=0;
//开始都没出局 都设为true
for(int i=0;i<b.length;i++){
b[i]=true;
}
while(leftCount>1){
if(b[index]){
count++;
if(count==num2){
count=0;
b[index]=false;
leftCount--;
}
}
index++;
if(index==b.length){
index=0;
}
}
for(int i=0;i<b.length;i++){
if(b[i]){
System.out.println(i);
}
}
} public static void main(String[] args) {

getLeft(100,3);

}

Answer 4

package cn.hovy.test4;public class Test6 {
public static void getLeft(int num,int num2){
boolean[] b = new boolean[num];
int leftCount=b.length;
int index=0;
int count=0;
for(int i=0;i<b.length;i++){
b[i]=true;
}
while(leftCount>1){
if(b[index]){
count++;
if(count==num2){
count=0;
b[index]=false;
leftCount--;
}
}
index++;
if(index==b.length){
index=0;
}
}
for(int i=0;i<b.length;i++){
if(b[i]){
System.out.println(i);
}
}
}
public static void main(String[] args) {
getLeft(100,3);
}
}
结果90

Answer 5

楼主看看这
import java.util.Vector;public class YueSeFuHuan { public static void main(String[] args) {
//第几个人退出圈
int m = 3;
//共多少人
int n = 10;
int point = 0;
int number = 1;
Vector v = new Vector();
for (int i = 0; i < n; i++) {
v.add(i + 1);// 初始化链表list；
}
while (v.size() > 1) {
if (number % m == 0) {
System.out.println(v.get(point));
v.remove(point);// 删除倍数为m的数字 point--;
} point++;
number++;
if (point > v.size() - 1) {
point = 0;// 若指针越界，从新开始
}
}
System.out.println(v.get(0));
}}

Answer 6

public class JosePhus { public static void main(String[] args) {
System.out.println(getLastone(100,3));
}

//persNum 游戏人数，喊到 count 的人退出
public static int getLastone(int persNum, int count){
int r = 0;
for (int i = 2; i <= persNum; i++)
r = (r + count) % i;
return r;
}
}

Answer 7

public class Test { /**
 * @param args
 */
public static void main(String[] args) {
// TODO Auto-generated method stub
int leng = 500;
int[] arr = new int[leng];

for (int i = 1; i <= leng ; i++){
arr[i-1] = i;
}

int tmp = leng;//现在总长度的
int a = 0; //剔除多少人
int step = 0; //步数
while(true){
if(tmp == 2){
step = step + 2;
break;
}
a = (int)Math.floor(tmp/3);
tmp = tmp - a;
step++;

}
System.out.println("总循环圈数："+step);
boolean hasFind = false;
int cycleTimes = 0;
for(int i = 0 ; i < leng ; i++){
int tmpNum = arr[i];
int maxStep = 1;
if(tmpNum%3==0){
continue;
}
while(true){
cycleTimes ++;
if(tmpNum<maxStep*3){
tmpNum = tmpNum + leng - (int)Math.floor(tmpNum/3);
}
if(maxStep == step - 1){
if(tmpNum == maxStep*3 + 1){
System.out.println("最后数字"+arr[i]);
hasFind = true;
break;
}
else {
//System.out.println("倒数第二位数字");
break;
}
}

if(hasFind){
break;
}
//System.out.println("x"+tmpNum);
maxStep ++;
if(tmpNum%3==0){
break;
}
}


}
System.out.println("总循环次数："+cycleTimes);
}
}
我的计算结果是 ：以500个人为例：
总循环圈数：17
最后数字49
总循环次数：744

Answer 8

马士兵 视频 --> javase  ---> 数据结构 ，有讲过。