友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
1823. Find the Winner of the Circular Game
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
1stfriend. -
Count the next
kfriends 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
2starting 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 integer k, 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
Follow up:
Could you solve this problem in linear time with constant space?
思路分析
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-19 15:24:45
*/
public int findTheWinner(int n, int k) {
Queue<Integer> queue = new ArrayDeque<>(n);
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();
}