哈希表、队列、递归、迭代，用约瑟夫环的递推公式，求解《1823. 找出游戏的获胜者》和《剑指 Offer 62. 圆圈中最后剩下的数字》
约瑟夫环的递推公式
例题
1823. 找出游戏的获胜者
剑指 Offer 62. 圆圈中最后剩下的数字
共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
游戏遵循如下规则：
从第 1 名小伙伴所在位置 开始 。
沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
否则，圈子中最后一名小伙伴赢得游戏。
给你参与游戏的小伙伴总数 n ，和一个整数 k ，返回游戏的获胜者。
示例：n = 5, k = 2，过程如上图所示
答案
哈希表
var findTheWinner = function(n, k) {
const visited = new Uint8Array(n + 1)
let r = 0
for (let i = 1; i <= n; i++) {
for (let j = 0; j < k; j++) {
if (++r > n) r = 1
if (visited[r] === 1) j--
}
visited[r] = 1
}
return r
};func findTheWinner(n int, k int) int {
visited, r := make([]int, n + 1), 0
for i := 1; i <= n; i++ {
for j := 1; j <= k; j++ {
r++
if r > n {
r = 1
}
if visited[r] == 1 {
j--
}
}
visited[r] = 1
}
return r
}class Solution {
function findTheWinner($n, $k) {
$visited = array_fill(0, $n + 1, 0);
$r = 0;
for ($i = 0; $i < $n; $i++) {
for ($j = 0; $j < $k; $j++) {
if (++$r > $n) $r = 1;
if ($visited[$r] === 1) $j--;
}
$visited[$r] = 1;
}
return $r;
}
}
<br>队列
var findTheWinner = function(n, k) {
const q = Array.from({length: n}, (_, i) => i + 1)
while (q.length > 1) {
for (let j = 1; j < k; j++) q.push(q.shift())
q.shift()
}
return q[0]
};func findTheWinner(n int, k int) int {
q := make([]int, n)
for i := 0; i < n; i++ {
q[i] = i + 1
}
for len(q) > 1 {
for i := 1; i < k; i++ {
head := q[0]
q = q[1:]
q = append(q, head)
}
q = q[1:]
}
return q[0]
}class Solution {
function findTheWinner($n, $k) {
$q = range(1, $n);
while (count($q) > 1) {
for ($i = 1; $i < $k; $i++) $q []= array_shift($q);
array_shift($q);
}
return $q[0];
}
}class Solution(object):
def findTheWinner(self, n, k):
q = deque(range(1, n + 1))
while (len(q) > 1):
for _ in range(k - 1):
q.append(q.popleft())
q.popleft()
return q[0]class Solution {
public int findTheWinner(int n, int k) {
Queue<Integer> q = new ArrayDeque<Integer>();
for (int i = 1; i <= n; i++) {
q.offer(i);
}
while (q.size() > 1) {
for (int i = 1; i < k; i++) {
q.offer(q.poll());
}
q.poll();
}
return q.peek();
}
}递归
var findTheWinner = function(n, k) {
return n === 1 ? 1 : (findTheWinner(n - 1, k) + k - 1) % n + 1
};func findTheWinner(n int, k int) int {
if n == 1 {
return 1
}
return (findTheWinner(n - 1, k) + k - 1) % n + 1
}class Solution {
function findTheWinner($n, $k) {
return $n === 1 ? 1 : ($this->findTheWinner($n - 1, $k) + $k - 1) % $n + 1;
}
}class Solution(object):
def findTheWinner(self, n, k):
return 1 if n == 1 else (self.findTheWinner(n - 1, k) + k - 1) % n + 1class Solution {
public int findTheWinner(int n, int k) {
return n == 1 ? 1 : (findTheWinner(n - 1, k) + k - 1) % n + 1;
}
}动态规划
var findTheWinner = function(n, k) {
const dp = new Uint16Array(n + 1)
dp[1] = 1
for (let i = 2; i <= n; i++) {
dp[i] = (dp[i - 1] + k - 1) % i + 1
}
return dp[n]
};func findTheWinner(n int, k int) int {
dp := make([]int, n + 1)
dp[1] = 1
for i := 2; i <= n; i++ {
dp[i] = (dp[i - 1] + k - 1) % i + 1
}
return dp[n]
}class Solution {
function findTheWinner($n, $k) {
$dp = array_fill(0, $n, 0);
$dp[1] = 1;
for ($i = 2; $i <= $n; $i++) {
$dp[$i] = ($dp[$i - 1] + $k - 1) % $i + 1;
}
return $dp[$n];
}
}迭代
var findTheWinner = function(n, k) {
let r = i = 1
while (i++ < n) r = (r + k - 1) % i + 1
return r
};
func findTheWinner(n int, k int) int {
r := 1
for i := 2; i <= n; i++ {
r = (r + k - 1) % i + 1
}
return r
}
class Solution {
function findTheWinner($n, $k) {
$r = $i = 1;
while ($i++ < $n) {
$r = ($r + $k - 1) % $i + 1;
}
return $r;
}
}class Solution(object):
def findTheWinner(self, n, k):
r = 1
for i in range(2, n + 1):
r = (r + k - 1) % i + 1
return rclass Solution {
public int findTheWinner(int n, int k) {
int r = 1;
int i = 1;
while (i++ < n) {
r = (r + k - 1) % i + 1;
}
return r;
}
}