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

import java.util.*;


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

    public int find(int n, int m){
        if(n == 1){
            return 0;
        }
        return (find(n - 1, m) + m)%n;
    }
}

约瑟夫环问题，关键是理解公式

1、定义函数f(n, m) 的结果返回最后剩余孩子的下标。所以当n == 1， 则剩下的孩子下标就是0。f(1,m) = 0。

2、找到 f(n,m) 和 f(n-1, m) 之间的关系。

f(n,m) 移除一个小孩之后，问题其实就变成了n-1个孩子，每m个孩子减少一个的问题也就是f(n-1,m)，唯一的区别是f(n-1,m)返回的下标不是我们的原f(n,m)所对应的下标。可以认为不是原数组对应的下标。那其实这个下标差值就是m，既假设f(n-1,m)返回的下标是1，其实是原下标的m+1，所以下标要加m。