【错题集-编程题】孩子们的游戏(圆圈中最后剩下的数)（约瑟夫环）

题目链接：孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网 (nowcoder.com)

一、分析题目

解法⼀：模拟。这⾥不多赘述，⽤数组或者链表模拟均可。数组：用一个 bool 数组来记录 i%n 的位置是否被喊到；链表：通过不断删除删除节点并更改指针指向来进行模拟。

解法⼆：迭代 / 递归 / 动态规划（数学规律）。

（1）递归：

n 个数向后去掉第 m 个数，还剩下 n−1 个数，依然要继续去掉第 m 个数。由此，从 (n, m) 的问题变成了 (n−1, m) 的子问题，其中若是 (n−1, m) 的子问题返回的最后一个数是 x，则 (n, m) 返回的结果就是 (m+x)%n，因此用递归解决。

• 终止条件：当 n=1 时就只剩下了最后一个孩子，应该返回 0。
• 返回值：子问题的结果加上 m 再对 n 取模，就是上一级删除的元素。
• 本级任务：递归进入子问题获取子问题删除的元素，再推算自己这一级删除的元素。

具体做法：

• step 1：首先判断没有小朋友的特殊情况。
• step 2：然后递归计算子问题，并将子问题的结果 x 运算 (m+x)%n 得到父问题的结果。

（2）迭代

也可以用迭代来代替递归，递归是自顶向下找子问题，根据子问题再自顶向上返回给父问题，来推算父问题的结果。我们可以直接从小的子问题，往上推，还是根据公式 (m+x)%n，只是这里的 n 变成了每一级子问题的长度。

for (int i = 2; i <= n; i++)
    x = (m + x) % i;

具体做法：

• step 1：首先判断没有小朋友的特殊情况。
• step 2：假设最后剩余 1 个的时候，结果肯定为 0。
• step 3：从最后剩余 1 个小朋友推断 2 个，再不断根据公式推断到 n 个。

（3）动态规划：

• 状态表示：dp[i] 表示：当有 i 个孩子围成一圈时，最终获胜的孩子的编号是多少。
• 初始化：dp[1] = 0（这个很好理解：只有一个孩子，那么获胜编号就是 0）
• 递推关系：dp[i] = (dp[i-1] + m) % i

通过画图，可以找到相邻两次删除坐标的规律。通过递推关系，求出剩下的最后⼀个数是哪个。

二、代码

1、解法一

//使用容器vector
class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        vector<int> circle;
        for(int i=0; i<n; i++)
            circle.push_back(i);
 
        int start = 0;
        while(n > 1)
        {
            start = (start + m - 1) % n;
            circle.erase(circle.begin() + start);
            n--;
        }
        return circle[0];
    }
};

2、解法二

//递归
class Solution {
public:
    int f(int n, int m) {
        if (n == 1)  
            return 0;
        int x = f(n - 1, m);
        return (m + x) % n;  
    }
    int LastRemaining_Solution(int n, int m) {
        return f(n, m);
    }
};
 
//迭代
class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        int x = 0;
        for(int i = 2; i <= n; i++)
            x = (m + x) % i;
        return x;
    }
};
 
//动态规划
class Solution
{
public:
    int LastRemaining_Solution(int n, int m) 
    {
        vector<int> dp(n+1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++) dp[i] = (dp[i-1] + m) % i;
        return dp[n];
    }
};
 
//动态规划-优化：滚动数组
class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        int f = 0;
        for(int i = 2; i <= n; i++) f = (f + m) % i;
        return f;
    }
};

三、反思与改进

拿到这道题的时候，真是感觉陌生又熟悉，因为之前有接触过，不过已经把其中的数学规律给忘记了。第一想法是递归，但没什么思路，然后尝试用数组模拟，有很多细节没考虑到，结果只能通过一些样例，其实这时候应该把特殊情况考虑上，就可以多拿一点分。接着后面想过要不用链表来写，但不知道为什么这个想法很快就被自己否决了，估计是知道这题是找规律所以懒得用链表做吧，其实链表需要考虑的细节没有那么多，或许用链表写一遍，思路可以更加清晰，下次不要轻易否决一个 idea。看了一下题解，果然自己还是考虑的太少了，应该多模拟几个样例，寻找其中的规律。