JAVA解决约瑟夫环编程题

JAVA解决约瑟夫环编程题 1、题目

给定一个包含n个数的序列[0, n - 1]，每次删除第m个数，直到只剩下一个数，求最后剩下的数

2、分析

               1、设求解规模为n的问题函数为f(n, m)，由于f(1, m)的结果固定为0，考虑从f(1)开始递推后续结果，首先需要找出f(n, m)与f(n - 1, m)之间的对应关系

                2、对f(n, m)问题求解时，先删去第一个数字，得到以k = m % n为起点，数量为n - 1的数字环，令这个数字环的求解结果为f '(n - 1, m) = y，令以0为起点，n-1个数字的求解结果为f(n - 1, m) = x，观察他们的这两个序列数字的对应关系：

x        0        1        2      ...     n - 1 - k        n - k        n - k + 1        ...        

y        k      k+1      k+2   ...     n - 1            0             1                   ...

易得：

        y = (x + k) % n = (x + m % n) % n = (x + m) % n

也即

        f '(n - 1, m) = [f(n - 1, m) + m] % n

       3、 f '(n - 1, m)的结果与f(n, m)的结果等同，题目得解，递推代码如下：

        

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