Re: [閒聊] 每日LeetCode

[ZooseWu (動物園 公告)]

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
推 SecondRun: https://i.imgur.com/8yyJS4n.png
→ SecondRun: 為什麼我拿到這結果 25怎麼贏的
→ SecondRun: 還是不在arr[0]贏的也算
→ ZooseWu: 25贏了1 結束
→ ZooseWu: 打敗衛冕者也算贏了一次
※ 編輯: ZooseWu (114.32.229.33 臺灣), 11/05/2023 10:23:19
→ ZooseWu: 我一開始送出也有在這邊弄錯