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

二、具体代码

/**
* @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;
};