题解 | 约瑟夫问题II

class Joseph {
  public:
    int getResult(int n) {
        if (n == 1) return 1;//如果是一个人，直接输出
        queue<int> myqueue;
        for (int i = 1; i <= n; ++i) { //编号入队
            myqueue.push(i);
        }
        int j = 2;
        while (myqueue.size() > 1) {
            int count = myqueue.size(); //count很关键，注意到在队列的时刻变化中，myqueue.size()是一个动态变化的值
            //必须保证接下来的循环次数固定为一开始的队列长度，且每次while循环时都需要更新，因此要放到while里面
            for (int i = 1; i <= count; ++i) {
                if (i % j == 1)
                    myqueue.push(myqueue.front());
                myqueue.pop();
            }
            j++;
            //第二轮再从上一轮最后一个报数的人开始依次报数，因此给队列循环一下，把最后一个放到队首
            //本题中n有奇偶数之差别，奇数状态下每次最后的那位是“最后一人”，但是偶数不是
            //偶数情况下，第一次循环一定是最后一位偶数需要出队，则最后一人实则为倒数第二位
            //这种情况处理比较麻烦，干脆直接让他们完全循环一遍，然后调整位置
            for (int i = 0; i < myqueue.size() - 1; ++i) {
                myqueue.push(myqueue.front());
                myqueue.pop();
            }
        }//while
        return myqueue.front();
    }
};

约瑟夫问题②

用queue实现循环队列，全部出队，符合条件就放到队尾，本期需要注意的是“最后一人”的处理办法。尝试了一会发现用这种循环队列的办法不好处理，写法很复杂，我直接不处理他，干脆再循环一次队列把最后一位放到队首。

具体看代码