LCOF-62圆圈中最后剩下的数字

开始采用暴力法，run time error

var lastRemaining = function(n, m) {
    let nums=[];
    for(let i=0; i<n; ++i) nums.push(i);
    let start = 0;
    while(nums.length>1) {
        let i=start;
        for(let j=0; j<m-1;j++, i=(i+1)%nums.length) {
        }
        nums.splice(i,1);
        if(i===nums.length) start=0;
        else start = i;
    }
    return nums[0];
};

1. n个人编号0, 1, …, n-1, 每数m次删掉一个人
2. 假设有函数f(n)表示n个人最终剩下的人的编号
3. n个人删掉一个人后，可以看作是n-1的状态，不过有自己的编号
4. n个人删掉第一个人的编号是(m-1)%n, 那么在被删除这个人后面的编号m%n，对应的是n-1个人时，编号为0的那个人。所以n时编号为m%n的那个人，n-1个人时编号为i的人就是n个人时(m+i)%n
5. 所以f(n)=(m+f(n-1))%n
6. f(1) = 0

在JavaScript语言中会爆栈，因此改写为迭代

var lastRemaining = function (n, m) {
  let ans = 0;
  for (let i = 2; i <= n; i++) {
    ans = (ans + m) % i;
  }
  return ans;
};