剑指 Offer 62. 圆圈中最后剩下的数字 ＜约瑟夫环＞

看了诸多大神的解题还是有点不明白，故记录一下。
如题：
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

方法一：递归

//数学 + 递归
class Solution {
    public int lastRemaining(int n, int m) {
        return f(n, m);
    }
    public int f(int n, int m) {
        if (n == 1) {
            return 0;
        }
        int x = f(n - 1, m);
        return (x + m) % n;
    }
}

当 n==1时，最后留下数字的编号一定是0。
当知道f( n - 1)的值时，便可以通过计算得到f(n)的值，已知f(1) = 0;
故可以通过递归的办法。
令f( n - 1)的值为 x，当知道f(n-1,m)的值为x时，f(n, m)的编号即为x往后数(m%n)个的数。

方法二：迭代

[5,3]问题---------[i,3] 每一轮i都在变化 ,结合上面递归所得公式 (x + m) % n可以推出;
[1,3] 剩下一个数3-----------------故下标为0
[2,3] 第四轮删除1------------------1 3
[3,3] 第三轮删除4------------------1 3 4
[4,3] 第二轮删除0------------------ 3 4 0 1
[5,3] 第一轮删除2------------------0 1 2 3 4
反向推出3在之前每个轮次的位置
下标为 (0 + 3) % 2 = 1
下标为 (1 + 3) % 3 = 1
下标为 (1 + 3) % 4 = 0
下标为 (0 + 3) % 5 = 3
最终剩下的数字的下标就是3。因为数组是从0开始的，所以最终的答案就是3

class Solution {
    public int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x + m) % i;
        }
        return x;
    }
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

参考：
https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/