剑指 Offer 62. 圆圈中最后剩下的数字

0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。

例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。

此题关键在于推导出以下函数
image.png
推导出该函数的关键在于理解,f(n)与f(n-1)得结果是一样的,即最后所剩的数相同。所以可以对 x=(x+m)%n做代换
故可得的最终代码

class Solution {
    public int lastRemaining(int n, int m) {
        //一开始理解错题意了。。。
        int x = 0;
        for(int i = 2 ; i <= n ; i++){
            x = (x + m)%i;
	    //这个加i也要注意。
        }
        return x;
    }
}

Q.E.D.