How do I simulate the elimination process efficiently?

Use a queue to manage the friends and simulate the process of eliminating every k-th person. This allows you to easily update the game state after each elimination.

What is the Josephus problem and how is it related?

The Josephus problem is a well-known theoretical problem where people are arranged in a circle and eliminated every k-th person. This problem is directly related, as it uses similar elimination logic.

Can I solve this problem without using recursion?

Yes, the problem can be solved using an iterative approach, such as by using a queue to simulate the eliminations step-by-step.

What if the starting position of elimination is different?

If the starting position changes, you can adjust the queue initialization to account for this new starting point. This will affect the sequence of eliminations.

What other optimizations can I apply to the solution?

In addition to using a queue, you can apply mathematical optimizations based on the Josephus problem to compute the winner directly without simulating each elimination step.

#1823

Medium

auto_awesome队列·driven·状态·processing

LeetCode 题解工作台

找出游戏的获胜者

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

数组数学递归队列模拟

题目描述

共有 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 是游戏的获胜者。

提示：

1 <= k <= n <= 500

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

lightbulb

解题思路

方法一

1

2

3

4

5

6

7

class Solution:
    def findTheWinner(self, n: int, k: int) -> int:
        if n == 1:
            return 1
        ans = (k + self.findTheWinner(n - 1, k)) % n
        return n if ans == 0 else ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Evaluating knowledge of simulating circular structures with queues.
question_mark
Tests familiarity with mathematical pattern recognition (e.g., Josephus problem).
question_mark
Assesses understanding of recursion and iterative approaches for optimization.

warning

常见陷阱

外企场景

error
Misunderstanding the circular nature and treating the game as linear.
error
Using excessive space for simulating the elimination process.
error
Forgetting to correctly account for the changing start position after each elimination.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the game by changing the starting position of the first elimination.
arrow_right_alt
Extend the problem to handle a varying step size (k) for each round of elimination.
arrow_right_alt
Alter the elimination rule to skip multiple friends at once or apply different conditions for elimination.

help

常见问题

外企场景

继续练习

#1799 N 次操作后的最大分数和 #1878 矩阵中最大的三个菱形和 #1728 猫和老鼠 II