LeetCode 筆記 - 1535. Find the Winner of an Array Game

Posted on

題目在此 1535. Find the Winner of an Array Game

給訂一個數列 arr 跟一個數字 k，遊戲是固定將 arr[0] 跟 arr[1] 比較，較小的數字會移動到 arr 的最後面。

請問第一個可以連贏 k 次的數字是誰？

解題思維

第一個我們要注意的是，如果 k 大於等於 len(arr)，那麼答案就是 max(arr)。
那剩下來就是實作出遊戲邏輯就可以了。image 106

其中有一個小技巧是可以 index 來模擬移動的過程，這樣就不用真的移動數字，這樣會快很多。

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def getWinner(self, arr: List[int], k: int) -> int:
        
        if (size := len(arr)) == 2:
            return max(arr)
        if size <= k:
            return max(arr)

        winner = arr[0]
        last_winner = None
        win_count = 0

        for r in range(1, size):
            winner = max(winner, arr[r])

            if winner == last_winner:
                win_count += 1
            else:
                win_count = 1
            last_winner = winner

            if win_count == k:
                return winner

        return winner
image 106

也許你也會想看看