1823.找出游戏的获胜者

1823.找出游戏的获胜者

题解

题目：n个位围成一个环，每次删除第k个人，求最后一个人是谁

思路：约瑟夫环

1.在最后一轮中，只剩一个人，下标pos1=(0+k)%1
2.该人既然是最后一个人，说明他在每一轮都是安全的
3.倒数第二轮：pos2=(pos1+k)%2
4.倒数第三轮：pos3=(pos2+k)%3
5.倒数第n轮：posN=(pos[N-1]+k)%n
6.得到递推公式，posN=(pos[N-1]+k) % n
7.已知 pos1=(0+k) % 1 = 0，依次计算pos2，pos3...即可

posN=(pos[N-1]+k) % n
1.既然递推公式出来了，也可以递归

代码

func findTheWinner(n int, k int) int {pos := 0for i := 2; i <= n; i++ {pos = (pos + k) % i}return pos + 1
}
func findTheWinner(n int, k int) int {if n == 1 {return 1}return (findTheWinner(n-1, k)-1+k)%n + 1
}