Simulation volume leetcode [general] 1823 Find the winner of the game

1823. Find the winner of the game

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 Where are the famous friends Start .
Count clockwise k A little friend , Counting requires contain The little friend at the beginning . 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 Next clockwise buddy Start , 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 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 .

Tips ：

1 <= k <= n <= 500

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/find-the-winner-of-the-circular-game
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def __init__(self):
        """  Think in reverse , Each interval k Insert a person in position , His number is actually the distance from the first person  """
        pass

    def findTheWinner(self, n: int, k: int) -> int:
        next = 1
        for time in range(1,n+1):
            next = (next + k -1) % time +1
        return next


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.findTheWinner(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [5,2],
        # [10,3],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions _ Paper blog -CSDN Blog

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！