1823. 找出游戏的获胜者

1823. 找出游戏的获胜者

共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
游戏遵循如下规则：

1. 从第 1 名小伙伴所在位置 开始 。
2. 沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
3. 你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
4. 如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
5. 否则，圈子中最后一名小伙伴赢得游戏。

给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。

示例 1：
输入：n = 5, k = 2 输出：3 解释：游戏运行步骤如下： 1) 从小伙伴 1 开始。 2) 顺时针数 2 名小伙伴，也就是小伙伴 1 和 2 。 3) 小伙伴 2 离开圈子。下一次从小伙伴 3 开始。 4) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 4 。 5) 小伙伴 4 离开圈子。下一次从小伙伴 5 开始。 6) 顺时针数 2 名小伙伴，也就是小伙伴 5 和 1 。 7) 小伙伴 1 离开圈子。下一次从小伙伴 3 开始。 8) 顺时针数 2 名小伙伴，也就是小伙伴 3 和 5 。 9) 小伙伴 5 离开圈子。只剩下小伙伴 3 。所以小伙伴 3 是游戏的获胜者。
示例 2：
输入：n = 6, k = 5 输出：1 解释：小伙伴离开圈子的顺序：5、4、6、2、3 。小伙伴 1 是游戏的获胜者。

提示：

• 1 <= k <= n <= 500

思路

模拟队列

使用队列特性模拟圆圈，将报数的前几个移动到队列末尾，移出第一个。当 n 很大时，造成超时。

数学公式-约瑟夫环

约瑟夫环是一个经典的数学问题，我们不难发现这样的依次报数，似乎有规律可循。为了方便导出递推式，我们重新定义一下题目。
问题： N 个人编号为 1，2，……，N，依次报数，每报到 M 时，杀掉那个人，求最后胜利者的编号。
这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。
递推公式：

• 表示，N 个人报数，每报到 M 时杀掉那个人，最终胜利者的编号
• 表示，N-1 个人报数，每报到 M 时杀掉那个人，最终胜利者的编号

下面我们不用字母表示每一个人，而用数字。
1、2、3、4、5、6、7、8、9、10、11
表示 11 个人，他们先排成一排，假设每报到 3 的人被杀掉。

• 刚开始时，头一个人编号是 1，从他开始报数，第一轮被杀掉的是编号 3 的人。
• 编号 4 的人从 1 开始重新报数，这时候我们可以认为编号 4 这个人是队伍的头。第二轮被杀掉的是编号 6 的人。
• 编号 7 的人开始重新报数，这时候我们可以认为编号 7 这个人是队伍的头。第三轮被杀掉的是编号 9 的人。
• ……
• 第九轮时，编号 2 的人开始重新报数，这时候我们可以认为编号 2 这个人是队伍的头。这轮被杀掉的是编号 8 的人。
• 下一个人还是编号为 2 的人，他从 1 开始报数，不幸的是他在这轮被杀掉了。
• 最后的胜利者是编号为 7 的人。

下图表示这一过程（先忽视绿色的一行）

现在再来看我们递推公式是怎么得到的！
将上面表格的每一行看成数组，这个公式描述的是：幸存者在这一轮的下标位置

• f(1,3)f(1,3))：只有 1 个人了，那个人就是获胜者，他的下标位置是 0
• f(2,3)=(f(1,3)+3)%2=3%2=1f(2,3)=(f(1,3)+3)%2=3%2=1：在有 2 个人的时候，胜利者的下标位置为 1
• f(3,3)=(f(2,3)+3)%3=4%3=1f(3,3)=(f(2,3)+3)%3=4%3=1：在有 3 个人的时候，胜利者的下标位置为 1
• f(4,3)=(f(3,3)+3)%4=4%4=0f(4,3)=(f(3,3)+3)%4=4%4=0：在有 4 个人的时候，胜利者的下标位置为 0
• ……
• f(11,3)=6f(11,3)=6

解答

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findTheWinner = function (n, k) {
  let temp = 0;
  for (let i = 2; i <= n; i++) {
    temp = (temp + k) % i;
  }
  return temp + 1;
};