【LeetCode每日一题】——1823.找出游戏的获胜者

一【题目类别】

• 队列

二【题目难度】

• 中等

三【题目编号】

• 1823.找出游戏的获胜者

四【题目描述】

• 共有 n 名小伙伴一起做游戏。小伙伴们围成一圈，按 顺时针顺序 从 1 到 n 编号。确切地说，从第 i 名小伙伴顺时针移动一位会到达第 (i+1) 名小伙伴的位置，其中 1 <= i < n ，从第 n 名小伙伴顺时针移动一位会回到第 1 名小伙伴的位置。
• 游戏遵循如下规则：
  • 从第 1 名小伙伴所在位置 开始 。
  • 沿着顺时针方向数 k 名小伙伴，计数时需要 包含 起始时的那位小伙伴。逐个绕圈进行计数，一些小伙伴可能会被数过不止一次。
  • 你数到的最后一名小伙伴需要离开圈子，并视作输掉游戏。
  • 如果圈子中仍然有不止一名小伙伴，从刚刚输掉的小伙伴的 顺时针下一位 小伙伴 开始，回到步骤 2 继续执行。
  • 否则，圈子中最后一名小伙伴赢得游戏。
  • 给你参与游戏的小伙伴总数 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 是游戏的获胜者。

六【解题思路】

• 本题提供了两种解题思路，时空复杂度均不同，可见Java和C的代码
  • Java
    • 本题可以直接使用队列模拟，但是使用队列模拟带来的问题就是我们如何删掉队列里面的元素
    • 为了解决这个问题，我们可以将待删除元素前面的所有元素都放到队列的尾部，然后再删除掉待删除元素
    • 这样就形成了一个环，就可以逐一删除了
    • 最后返回剩下的最后一个元素即可
  • C
    • 但是上一种方法的时空复杂度太高了，为了减低时空复杂度，我们采用数学方法：约瑟夫环。这应该属于组合数学中的递推关系
    • 我们做如下假设：
      • $f(n,k)$表示，n个人报数，报到k时删除对应元素，最终胜利者的编号
      • $f(n-1,k)$表示，n-1个人报数，报到k时删除对应元素，最终胜利者的编号
    • 可以想到，当我们删除第k个位置的元素后，相当于整个数组向前移动了k位，因为下一次要从k+1开始
    • 那如果我们已经知道$f(n-1,k)$，也就是已知$n-1$个元素，胜利者的下标，那么求$n$个元素，胜利者的下标，就是数组向后移动$k$位
    • 我们还需要注意有可能数组越界，超过的部分要转回来，有点像方法一中的环，所以要对当前长度取模
    • 这样我们就能得到递推关系式：$f(n,k)=(f(n-1,k)+k)$，初始条件为只有一个人的情况，即：$f(1,k)=1$
    • 最后根据递推关系式返回结果即可

七【题目提示】

• 1 <= k <= n <= 500

八【题目进阶】

• 你能否使用线性时间复杂度和常数空间复杂度解决此问题？

九【时间频度】

• Java
  • 时间复杂度：$O(nk)$，其中$n$为人数，$k$为移动的个数
  • 空间复杂度：$O(n)$，其中 $n$ 为人数
• C
  • 时间复杂度：$O(n)$，其中 $n$ 为人数
  • 空间复杂度：$O(1)$

十【代码实现】

1. Java语言版

package Queue;

import java.util.LinkedList;
import java.util.Queue;

public class p1823_FindTheWinnerOfTheCircularGame {

    public static void main(String[] args) {
        int res = findTheWinner(5, 2);
        System.out.println("res = " + res);
    }

    public static int findTheWinner(int n, int k) {
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            queue.offer(i);
        }
        while (queue.size() > 1) {
            for (int i = 1; i < k; i++) {
                queue.offer(queue.poll());
            }
            queue.poll();
        }
        return queue.poll();
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

2. C语言版

#include

int findTheWinner(int n, int k)
{
	int res = 0;
	for (int i = 2; i <= n; i++)
	{
		res = (res + k) % i;
	}
	return res + 1;
}

/*主函数省略*/
1
2
3
4
5
6
7
8
9
10
11
12
13

十一【提交结果】

1. Java语言版
   

2. C语言版