原题链接:Leetcode 1823. There are n friends that are playing a game.
The friends are sitting in a circle and are numbered from 1 to n in clockwise order. More formally, moving clockwise from the ith
friend brings you to the (i+1)th
friend for 1 <= i < n, and moving clockwise from the nth friend brings you to the 1st friend.
The rules of the game are as follows:
- Start at the 1st friend.
- Count the next
k
friends in the clockwise direction including the friend you started at. The counting wraps around the circle and may count some friends more than once. - The last friend you counted leaves the circle and loses the game.
- If there is still more than one friend in the circle, go back to step 2 starting from the friend immediately clockwise of the friend who just lost and repeat.
- Else, the last friend in the circle wins the game.
Given the number of friends,n
, and an integerk
, return the winner of the game.
Example 1:
Input: n = 5, k = 2
Output: 3
Explanation: Here are the steps of the game:
1) Start at friend 1.
2) Count 2 friends clockwise, which are friends 1 and 2.
3) Friend 2 leaves the circle. Next start is friend 3.
4) Count 2 friends clockwise, which are friends 3 and 4.
5) Friend 4 leaves the circle. Next start is friend 5.
6) Count 2 friends clockwise, which are friends 5 and 1.
7) Friend 1 leaves the circle. Next start is friend 3.
8) Count 2 friends clockwise, which are friends 3 and 5.
9) Friend 5 leaves the circle. Only friend 3 is left, so they are the winner.
Example 2:
Input: n = 6, k = 5
Output: 1
Explanation: The friends leave in this order: 5, 4, 6, 2, 3. The winner is friend 1.
Constraints:
- 1 <= k <= n <= 500
方法一:队列+模拟
思路:
模拟游戏的过程:
首先将玩家加入到一个队列当中,对于给定的K,执行K-1次将队头移动到队尾的操作,此时就是要淘汰的人。将他出队。最后队列中剩下的唯一元素就是胜者,输出即可。
c++代码:
class Solution {
public:int findTheWinner(int n, int k) {queue<int> Q;for(int i = 1; i <= n; i++ ){Q.push(i);}while(Q.size() > 1){// k-1轮 将元素从队头放到队尾for(int i = 1; i < k; i++ ){Q.push(Q.front());Q.pop();}// 队头出队 表示淘汰Q.pop();}return Q.front();}
};
复杂度分析:
- 时间复杂度:O(nk),需要淘汰n-1个人,淘汰每个人需要循环k-1次
- 空间复杂度:O(n),用一个队列来存储元素