1823.找出游戏的胜利者

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findTheWinner = function (n, k) {
    // 构造游戏参与者
    let nums = []
    for (let i = 1; i <= n; i++) {
        nums.push(i)
    }

    let hit = 0 // 游戏每轮传递给谁

    // 当游戏人数为1个时，该成员就是胜利者
    while (nums.length > 1) {
        // 开始绕圈，每轮传递k步,自身算一步，所以i从1开始
        for (let i = 1; i < k; i++) {
            hit++
            // 超过了就又从0开始传递
            if (hit > nums.length - 1) {
                hit = 0
            }
        }
        // console.log(hit, nums[hit])
        // 传到谁就把谁删掉
        nums.splice(hit, 1)
        // console.log(nums)

        // 删掉后，新一轮从下一个人开始传递，前面的人删掉了，所以hit不用变
        // 但是如果删的是最后一个元素，下一回合就是从0开始了
        if (hit > nums.length - 1) {
            hit = 0
        }
    }

    // console.log(nums)

    return nums[0]
};

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findTheWinner = function (n, k) {
    // 模拟队列，很巧妙
    // 因为一直绕圈传递，其实就是个环，就是不断从队列头取出元素放入队尾的过程

    let queue = []
    // 构造游戏参与者
    for (let i = 1; i <= n; i++) {
        queue.push(i)
    }

    // 每轮淘汰一人，剩下的最后一人就是胜利者
    while (queue.length > 1) {
        // 传递k步
        for (let i = 0; i < k; i++) {
            // 从队列头取出放入队尾，形成环
            queue.push(queue.shift())
        }
        // 淘汰一人
        queue.pop()
    }

    return queue[0]
}

console.log(findTheWinner(5, 2))
// console.log(findTheWinner(3, 5))