done[223]击鼓传花游戏（循环队列）

击鼓传花

击鼓传花的规则:
几个朋友一起玩一个游戏, 围成一圈, 开始数数（数数时数字都是挨着的，第一个人数1，之后的人数2）, 数到某个数字的人自动淘汰。汰的人后面再从1开始数，重复上面的游戏，直到就剩下一个人，请问剩下了谁？

// 测试例子
var names = ["John", "Jack", "Camila", "Ingrid", "Carl"];
var endName = passGame(names, 8); // 数到 8 的人淘汰
console.log("最终留下:" + endName); // 'john'

实现

function passGame (names, n) {
    let count = 1;
    while (names.length > 1) {
        let cur = names.shift();
        if (count != 0) {
            names.push(cur);
        }
        count++;
        count %= n;
    }
    return names[0];
}

console.log(passGame(["John", "Jack", "Camila", "Ingrid", "Carl"], 8)) // John

约瑟夫问题

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

循环队列， 超时

var lastRemaining = function(n, m) {
    let arr = Array.from({length: n}, (v, i) => i);
    let count=1;
    while (arr.length > 1) {
        let cur = arr.shift();
        if (count % m != 0) {
            arr.push(cur)
        }
        count++;
    }
    return arr.pop();
};

递归实现

var lastRemaining = function(n, m) {
    return helper(n, m);
};

function helper(n, m) {
    if (n == 1) return 0;
    return (helper(n-1, m) + m) % n;
}

85+35

非递归实现

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

40+83