Re: [閒聊] 每日LeetCode已回收
1535. Find the Winner of an Array Game
給你一個陣列 arr 表示比賽順序
k 表示勝利次數
每次比賽的時候 arr[0] 會跟 arr[1] 比
勝利的數字會跑到 arr[0] 而輸的會跑到陣列尾端
遊戲會進行到有人連續勝利 k 次後結束
例題:
1.
Input: arr = [2,1,3,5,4,6,7], k = 2
Output: 5
回合 | 陣列 | 勝者 | 勝利次數
1 | [2,1,3,5,4,6,7] | 2 | 1
2 | [2,3,5,4,6,7,1] | 3 | 1
3 | [3,5,4,6,7,1,2] | 5 | 1
4 | [5,4,6,7,1,2,3] | 5 | 2
5 連續勝利兩次 比賽結束
2.
Input: arr = [3,2,1], k = 10
Output: 3
First think:
範例題目就展示了這一提的一個特性：
陣列中的最大值不一定是贏家
可能還沒比完就找到贏家了
以一開始覺得陣列順序可能會亂掉
如果會比到第二輪的話
需要對陣列做操作才能知道正確的比賽順序
Approach:
仔細思考就能發現
如果第一輪比完的話
當下的衛冕者就是陣列最大值
所以接下來不管怎麼比結果都不會變
這樣的話我們就不需要考慮第二輪的狀況
也就不需要進行陣列操作
單純記錄勝利次數就好了
TS code:
function getWinner (arr: number[], k: number): number {
let winner = arr[0]
let winCount = 0
const WinnerWin = () => {
winCount++
}
const WinnerLost = (newWinner: number) => {
winner = newWinner
winCount = 1
}
for (let i = 1; i < arr.length; i++) {
if (winner > arr[i]) {
WinnerWin()
} else {
WinnerLost(arr[i])
}
if (winCount === k) return winner
}
return winner
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1699148024.A.27A.html
推
11/05 10:13,
2年前
, 1F
11/05 10:13, 1F
→
11/05 10:14,
2年前
, 2F
11/05 10:14, 2F
→
11/05 10:14,
2年前
, 3F
11/05 10:14, 3F
→
11/05 10:21,
2年前
, 4F
11/05 10:21, 4F
→
11/05 10:22,
2年前
, 5F
11/05 10:22, 5F
※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/05/2023 10:23:19
→
11/05 10:24,
2年前
, 6F
11/05 10:24, 6F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 491 之 719 篇)：