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

raylan.chen大约 2 分钟

class Solution {
    public int iceBreakingGame(int num, int target) {
        // 初始化 dp[1] = 0
        int x = 0;
        // i代表数字个数
        // dp[i] = (dp[i - 1] + target) % i
        for (int i = 2; i <= num; i++) {
            x = (x + target) % i;
        }
        return x;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solutions/607638/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

个人理解：

f(n, target) ==> n 个数字删除第 m 个数字最后剩下的数字

n 个数删除第 target 个数（设其为 k - 1）后的序列为：0, 1, ..., k - 2, k, k + 1, ..., n - 1

将其转换成另一种表示方法，即为：k, k + 1, ..., n - 1, 0, 1, ..., k - 2 ==> f'(n - 1, target)

将 k 映射为 0，

k == > 0,

k + 1 ==> 1,

k + 2 ==> 2,

...,

n - 1 ==> n - 1 - k,

0 ==> n - k,

...,

k - 2 ==> n - 2,

原数字 k <== (0 + k) % n

原数字 k + 1 <== (1 + k) % n

...

原数字 <== (映射后数字 + k) % n

f(n, target) = f'(n - 1, target) （? 这个等式不太能理解）

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

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

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

f(1, target) = 0

提示

参考：

LCR 187. 破冰游戏 - 力扣（LeetCode）

zhedahht/CodingInterviewChinese2: 《剑指Offer：名企面试官精讲典型编程面试题》第二版源代码

以上个人理解可能有误！

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

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

参考链接

优秀题解