Leetcode-1823: find the winner of the game

Title Description

share n We play games together . All the guys in a circle , Press Clockwise order from 1 To n Number . To be precise , From i If you move one person clockwise, you will arrive at the (i+1) The location of famous friends , among 1 <= i < n , From n If you move one person clockwise, you will go back to the first 1 The location of famous friends .
The game follows the following rules ：
From 1 Start at the location of the first child partner .
Count clockwise k A little friend , When counting, you need to include the starting partner . Count in circles one by one , Some buddies may be counted more than once .
The last one you count needs to leave the circle , And it's like losing the game .
If there is still more than one partner in the circle , From the little friend who just lost Clockwise, the next little friend starts , Back to step 2 Carry on .
otherwise , The last one in the circle wins the game .
Give you the total number of players in the game n , And an integer k , Back to the winner of the game .

Example

Example 1：

Input ：n = 5, k = 2
Output ：3
explain ： The operation steps of the game are as follows ：

1. Little friends 1 Start .
2. Number of punctures in time 2 A little friend , That's my little friend 1 and 2 .
3. buddy 2 Get out of the loop . Next time I'm a kid 3 Start .
4. Number of punctures in time 2 A little friend , That's my little friend 3 and 4 .
5. buddy 4 Get out of the loop . Next time I'm a kid 5 Start .
6. Number of punctures in time 2 A little friend , That's my little friend 5 and 1 .
7. buddy 1 Get out of the loop . Next time I'm a kid 3 Start .
8. Number of punctures in time 2 A little friend , That's my little friend 3 and 5 .
9. buddy 5 Get out of the loop . All that's left is little friends 3 . So my little friend 3 It's the winner of the game .

Example 2：
Input ：n = 6, k = 5
Output ：1
explain ： The order in which little friends leave the circle ：5、4、6、2、3 . buddy 1 It's the winner of the game .

The problem solving process

Ideas and steps

（1） The typical Joseph Ring problem , It can be considered as a closed loop queue ;
（2） First the  n  A little friend follows  1 --> n  In the order of , The team leader element is  1, The element at the end of the team is  5;
（3） Loop through the queue , First take the team leader element out of the team , Determine whether the current counter is equal to  0, If not equal to  0, It indicates that the small partner in this position needs to participate in the next count , Then join the small partner in the team , That is, insert it at the end of the team ; If the counter is equal to  0, It means that the small partner in this position has lost , Need to leave the circle , At the same time, reset the counter to  k;
（4） Each cycle requires the counter to be decremented  1, And it should be noted that the counter must be decremented first  1  operation , That is, the preceding  --;
（5） Stop the loop when there is only one element left in the queue , Return the current team header element .

Code display

public class FindTheWinner {
    

    public int findTheWinner(int n, int k) {
    
        //  Initialize queue 
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 1; i <= n; ++i) {
    
            queue.add(i);
        }
        //  Counter 
        int tmp = k;
        //  The remaining 1 A small partner stops the cycle 
        while (queue.size() > 1) {
    
            int num = queue.poll();
            if (--tmp != 0){
    
                //  Not the loser , Join the team again 
                queue.add(num);
            } else {
    
                //  Reset counter 
                tmp = k;
            }
        }
        return queue.peek();
    }

    public static void main(String[] args) {
    
        FindTheWinner findTheWinner = new FindTheWinner();
        System.out.println(findTheWinner.findTheWinner(5, 2));
    }

}