题解 | 孩子们的游戏(圆圈中最后剩下的数)

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @return int整型
     */
    int LastRemaining_Solution(int n, int m) {
        // write code here
        int x = 0;
        for(int i = 2; i <= n; ++i){
            x = (x+m)%i;
        }
        return x;
    }
};

首先得理解递归法，然后发现了一个巧合，每次往更深的地方走，但是反向迭代。

我们可以直接心算得到最深的地方的值，然后反向迭代，因为每次使用的参量和公式是一致的，只需要改变一个和迭代有关的变量（链表长度），因此可以使用迭代。