[数据结构与算法]【Leetcode·每日一题】找出游戏的获胜者（约瑟夫环问题）

总之先开始吧，哪怕只是最简单粗暴的思路。

题目

Leetcode · 找出游戏的获胜者

解法一：队列，模拟游戏

核心问题

找到k指向的元素，并将下一次开始的指针指向k+1位。

解决思路

找到k指向的元素后，把k前面的元素整体挪到数组最后。指针始终从第一位开始寻找。

示例：
假设 n=5 k = 3，则有：

1. 生成数组 arr = [1, 2, 3, 4, 5]
2. 拿出目标元素前的所有元素 [1,2]，此时 arr = [3, 4, 5]
3. arr.shift()移除目标元素，此时 arr = [4, 5]
4. 把 [1, 2] 重新拼接到 arr 尾部，此时 arr = [4, 5, 1, 2]
5. 重复2开始的步骤

注意：
对于目标元素的查找，注意考虑 k 和 len 的大小比较，及 k % len = 0 时的情况

代码

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findTheWinner = function (n, k) {
    let arr = [],
        len = n
    for (let i = 0; i < n; i++) {
        arr[i] = i + 1
    }
    for (;len > 1; len--){
        let tarIdx = k;
        if (k > len) tarIdx = k % len
        const headArr = arr.splice(0, tarIdx - 1)
        tarIdx == 0 ? arr.pop() : arr.shift()
        arr.push(...headArr)
    }
    return arr[0]
};

解法二

参考链接：
约瑟夫环——公式法（递推公式）

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖