题目链接：孩子们的游戏(圆圈中最后剩下的数)_牛客题霸_牛客网 (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。看了一下题解，果然自己还是考虑的太少了，应该多模拟几个样例，寻找其中的规律。
