LeetCode Ts-2682. Find the Losers of the Circular Game

    AllenLi
    CodingLeetCode Js-Array

    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: 1st friend receives the ball. After that, 1st friend passes it to the friend who is k steps away from them in the clockwise direction. After that, the friend who receives the ball should pass it to the friend who is 2 * k steps away from them in the clockwise direction. After that, the friend who receives the ball should pass it to the friend who is 3 * k steps away from them in the clockwise direction, and so on and so forth. In other words, on the ith turn, the friend holding the ball should pass it to the friend who is i * k steps away from them in the clockwise direction. The game is finished when some friend receives the ball for the second time. The losers of the game are friends who did not receive the ball in the entire game. Given the number of friends, n, and an integer k, return the array answer, which contains the losers of the game in the ascending order. 

    這裡有 n 個朋友們在玩一個遊戲。他們圍成一個圓圈，按照順時針方向從 1 到 n 編號。
更準確的說，從第 i 個朋友順時針移動到第 i + 1 個朋友位置(1 <= i < n)，從第 n 個朋友順時針移動到第 i 個朋友。
遊戲的規則如下：
第 1 位朋友接球。
之後，第 1 位朋友將球傳給順時針方向距離自己 k 步的朋友。
之後，接球的朋友將球傳給順時針方向距離自己 2 * k 步的朋友。
之後，接球的朋友將球傳給順時針方向距離自己 3 * k 步的朋友。
換句話說，在第 i 輪，持球的朋友要將球傳給順時針方向距離自己 i * k 步的朋友。
當某個朋友第二次接球的時候，遊戲結束。
遊戲中沒有接球的朋友即為輸家。
題目給予朋友的數量 n 和一個整數 k，回傳陣列 answer，其中按升序排列所有輸家。

    Example 1:

    Input: n = 5, k = 2
Output: [4,5]
Explanation: The game goes as follows:
1) Start at 1st friend and pass the ball to the friend who is 2 steps away from them - 3rd friend.
2) 3rd friend passes the ball to the friend who is 4 steps away from them - 2nd friend.
3) 2nd friend passes the ball to the friend who is 6 steps away from them  - 3rd friend.
4) The game ends as 3rd friend receives the ball for the second time.

    Example 2:

    Input: n = 4, k = 4
Output: [2,3,4]
Explanation: The game goes as follows:
1) Start at the 1st friend and pass the ball to the friend who is 4 steps away from them - 1st friend.
2) The game ends as 1st friend receives the ball for the second time.

    Solution:
    我們宣告 visited 來存放已經拿到球的玩家，
    接著 current 代表目前拿到球的玩家，且從 1 號玩家開始，
    而 turn 則代表第幾次的傳球。
    我們執行 while 直到玩家重複被選到，
    過程中計算下一個拿球的玩家，
    直到球傳到已經拿過的人為止。
    最後就是找出沒有拿過球的人放到 losers，
    回傳 losers。

    Code 1: BigO(n)

    function circularGameLosers(n: number, k: number): number[] {
    const visited: Set = new Set();
    let current: number = 1;
    let turn: number = 1;

    while(!visited.has(current)) {
        visited.add(current);
        current = (current + turn * k - 1) % n + 1;
        turn++;
    }
    const losers: number[] = [];
    for (let i = 1; i <= n; i++) {
        if (!visited.has(i)) losers.push(i);
    }
    return losers;
};

    FlowChart:
    Example 1

    Input: n = 5, k = 2

Turn 1: player 1
Turn 2: player 3
Turn 3: player 2
Loop ends at player 3
Losers: [4,5]

    Example 2

    Input: n = 4, k = 4

Turn 1: player 1
Loop ends at player 1
Losers: [2,3,4]

    Related Posts