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

大家好，我是小庄，一个专心于互联网技术的深漂打工人。

今天，补上周末忘发的算法～

Leetcode的算法题安排上～保持算法思维，靠近大厂多一点点。

一、题目地址

https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/

二、具体代码

/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
/*
    1、思路：使用数学方法推导，再进行反推导得到动态规划方程
        （注意：该例子的最后结果是3，带着结果去看问题）

        第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
        (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
        第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
        第三次，【1, 3, 4】，本轮要踢出4                                        看1
        第四次，【1, 3】 本轮要踢出1                                            看3
        第五次，【3】
        最后返回3

        我们要使用的数学方法，就是从结果0号位置，反推导最开始在哪
        你从第二次，向上看第一次
        你会发现，原来3在0的位置
                现在，3在(0 + 3) % 5
                        => +3 回到上次的位置
                        => %5 防止数组溢出，并且数组本来就是循环数组

        也就是，f(n) = ( f(n - 1) + m ) % n
        解释意思：
            f(n) 表示上一次
            f(n - 1) 表示这次，因为我们要从这次回推上一次
            m 表示隔几个
            n表示上一次的数组长度

    2、复杂度：
    （1）时间复杂度：O(N)
    （2）空间复杂度：O(1)
*/
var lastRemaining = function(n, m) {
    // 1、注意：当n为1时，无论m是多少,结果肯定还是为0
    let res = 0;
    for(let i=2; i<=n; i++) {
        /*
            2、本质是：f(n)=(f(n-1)+m) % n,只不过当前f(n)
               可用变量保存结果，节省了空间复杂度而已哈
         */
        res = (res + m) % i;
    }
    return res;
};

三、参考链接

https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/javajie-jue-yue-se-fu-huan-wen-ti-gao-su-ni-wei-sh/
https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/solution/jian-zhi-offer-62-yuan-quan-zhong-zui-ho-dcow/

四、补充部分

关注公zhong号：【深漂程序员小庄】：
内含丰富的学习资源和面试经验（不限前端、java、算法），还有学习交流群可加，并且还有各大厂大佬可一起交流学习，一起进步～添加小庄微信，回复【加群】，可加入互联网技术交流群。