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

原题传送门：

https://leetcode.cn/problems/find-the-winner-of-the-circular-game/

分析

• 面对这道算法题目，二当家的陷入了沉思。

• 直接模拟的时间复杂度比较高。

• 像这种有规律的，通常都可以用递归：下一步操作的是本次操作开始点向后k，这时游戏人数减少一个，所以下一步的游戏就变成k + fn(n - 1, k)。

• 而递归都可以转换为循环。

• 另外这次二当家的知道了这个问题有个名称是 约瑟夫环。

题解

rust

impl Solution {
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        if n == 1 {
           return 1;
        }

        let ans = (Solution::find_the_winner(n - 1, k) + k) % n;

        return if ans == 0 {
            n
        } else {
            ans
        }
    }
}

impl Solution {
    pub fn find_the_winner(n: i32, k: i32) -> i32 {
        let mut pos = 0;

        (2..n + 1).for_each(|i| {
            pos = (pos + k) % i;
        });

        pos + 1
    }
}

go

func findTheWinner(n int, k int) int {
    pos := 0

	for i := 2; i < n+1; i++ {
		pos = (pos + k) % i
	}

	return pos + 1
}

c++

class Solution {
public:
    int findTheWinner(int n, int k) {
        int pos = 0;
        
        for (int i = 2; i < n + 1; ++i) {
            pos = (pos + k) % i;
        }
        
        return pos + 1;
    }
};

java

class Solution {
    public int findTheWinner(int n, int k) {
        int pos = 0;

        for (int i = 2; i < n + 1; ++i) {
            pos = (pos + k) % i;
        }

        return pos + 1;
    }
}

typescript

function findTheWinner(n: number, k: number): number {
    let pos = 0;

	for (let i = 2; i < n + 1; ++i) {
		pos = (pos + k) % i;
	}

	return pos + 1;
};

python

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        pos = 0
        for i in range(2, n + 1):
            pos = (pos + k) % i
        return pos + 1

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~