求问一道面试题

昨天去面试的时候对方给出了一道题。求问答案。
题目内容是。国王要对死刑犯执行死刑。但是同时他想赦免一个人。所以他的方法是。
让犯人们围成一个圈。给第一个人一把剑。让他把站在他左边第一个的人杀死。然后把剑递给左边的人。也就是死的左边的第一个。一次类推。5个人的时候最后活下来的是第三个。求写代码可以计算出来人数为N的时候第几个人可以活下来。
感觉我写的代码可能不对或者不好。求高人指点。

我的代码是：Public class solution{
   Public int solution(int number){
      If(number==0) return 0;
      If(number<=2) return 1;
      Person head = new Person(1);
      Person current = head;
      For(int i=2; i<=number; i++){
         Person temp = new Person(i);
         current.next = temp;
         current = current.next;
      }
      current.next = head;
      Person current = head;
      While（current.next != null）{
         If(current.next.next!=null){
            current.next = current.next.next;
            current = current.next;
         }else{
             current.next = null;
             Break;
         }
      }
      return curren.id;
   }
}
Class Person{
   int id;
   Person next;
   Person(int number){
      Id = number;
      Next = null;
   }
}

7 个解决方案

#1

看到这题之后， 首先题意很简单。但人数多了以后，貌似只能暴力求解。
然而看着题意如此简单的份上，直觉上来看，这应该是到数学题，会有规律，可以直接数学运算求解。
做了如下尝试：
人数1：活1
人数2：活1
人数3：活3
4:1
5:3
6:5
7:7
8:1
9:3
10:5
11:7
12:9
好了。规律很明显了。有了规律，输入任何一个人数就能直接求解第几个活下来了。
代码就不写了。

#2

补充一下：
13:11
14:13
15:15
16:1

#3

凡是2^n -1个人，活的就是左后那个。
在x^(n-1)和2^n-1之间的人数，往前数个数就行了。

#4

问题类似约瑟夫环

#5

public class Solution {
	public Solution(int position) {
		this.position = position;
	}
	public int number;
	public final int position;
	public Solution left; // 前一个
	public Solution right; // 后一个

}

public class TestSolution {
	public static void main(String[] args) {

		functin(11);
	}

	private static void functin (int n){
		Solution[] s = new Solution[n];
		for (int i = 0; i < n; i++) {
			s[i] = new Solution(i + 1);
			if (i > 0) {
				circle(s[i - 1], s[i]);

			}
			if (i == n - 1) {
				circle(s[i], s[0]);
			}
		}
		Solution curren = s[0];
		curren.number = 1;
		while (true) {
			if (curren.right == curren) {
				break;
			}
			if (curren.number == 2) {
				circle(curren.left, curren.right);
				curren.right.number = 1;
			} else if (curren.number < 2) {
				curren.right.number = curren.number + 1;
			}
			curren = curren.right;
		}
		System.out.println(n+"个人的时候最后活下来的是第"+curren.position+"个");
	}

	private static void circle(Solution left, Solution right) {
		left.right = right;
		right.left = left;
	}
}

#6

就是约瑟夫环的问题
以5人为例，这个过程表示如下:
a).1 2 3 4 5 //1杀2，剑给3. 序列为 1   3 4 5,由于从3开始，于是给3编号为1，后面依次+1，新序列为 b)
b).4    1 2 3 //a)和b)序列关系为 ai = (bi + 2) > i ? ((bi + 2) - i) : (bi + 2),这里i=5
c).2     3   1 //序列生成方法同上,但c)和b)序列关系稍变，因为b序列只有4个元素，所以这里i=4
d)        1   2 //同上
e)        1
为了求最后一个人变换后的序列中序号1在最初始序列的编号，可以依次向上推倒

int solve(int n)
	{
		if(n == 1 || n == 2) return 1;

		int m = 1;
		for(int i = 2 ; i <= n ; ++ i)
		{
			m += 2;
			if(m > i) m -= i;
		}
		return m;
	}

#7

其实也就是约瑟夫环的问题,1,2报数   喊2的人退出

import java.util.*;


public class Solution{

    public static void main(final String[] args) {
        int numberOfChildren =8; // 犯人总数
        int quitNo = 2; // 报quitNo的就是第二个
        System.out.println(
                numberOfChildren + "个犯人，剩下的是第"
                + getCountOffResult(numberOfChildren, quitNo) + "个犯人");
    }

    /**
     * 获得报数结果
     *
     * @param numberOfChildren 犯人总数
     * @param quitNo 报quitNo的犯人被杀
     * @return 剩下的是第几个犯人
     */
    private static int getCountOffResult(
            int numberOf*er, int quitNo) {
        // 入口参数检查
        if (numberOf*er <= 0 || quitNo <= 0) {
            return 0;
        }

        // 定义并生成小孩数组列表，编号从1到numberOfChildren
        List<Integer> *er= new LinkedList<>();
        for (int ii = 1; ii <= numberOf*er; ii++) {
            *er.add(ii);
        }

        Iterator<Integer> *erIterator = *er.iterator();
        while (numberOf*er > 1) {
            Integer *erNo = 0;
            for (int ii = 0; ii < quitNo; ii++) {
                if (!*erIterator.hasNext()) {
                    *erIterator = *er.iterator();
                }
                *erNo = *erIterator.next();
            }
           ;

            *erIterator.remove();
            numberOf*er--;
        }

        *erIterator = *er.iterator();
        return *erIterator.next();
    }
}