前往
大廳
主題

LeetCode - 1688. Count of Matches in Tournament 解題心得

Not In My Back Yard | 2023-03-12 12:00:03 | 巴幣 0 | 人氣 199

題目連結:


題目意譯:
你被給定一整數 n,代表一個錦標賽中的隊伍數量,其有著以下奇妙規則:
如果當前隊伍數量為偶數,則每隊都會與另一隊配對。總共會有 n / 2 場比賽會舉行,且 n / 2 個隊伍會晉級到下一輪。
如果當前隊伍數量為奇數,會隨機地挑某一隊直接晉級,而剩下的隊伍彼此配對。總共會有 (n - 1) / 2 場比賽會舉行,且 (n - 1) / 2 + 1 個隊伍會晉級到下一輪。

回傳在錦標賽中直到贏家被決定出來前最少需要舉行多少場比賽。

限制:
1 ≦ n ≦ 200



範例測資:
範例 1:
輸入: n = 7
輸出: 6
解釋: 錦標賽的細節:
- 第 1 輪:隊伍數 = 7,比賽場數 = 3,且有 4 隊晉級。
- 第 2 輪:隊伍數 = 4,比賽場數 = 2,且有 2 隊晉級。
- 第 3 輪:隊伍數 = 2,比賽場數 = 1,且有 1 隊被宣布為贏家。
總共比賽數 = 3 + 2 + 1 = 6。

範例 2:
輸入: n = 14
輸出: 13
解釋: 錦標賽的細節:
- 第 1 輪:隊伍數 = 14,比賽場數 = 7,且有 7 隊晉級。
- 第 2 輪:隊伍數 = 7,比賽場數 = 3,且有 4 隊晉級。
- 第 3 輪:隊伍數 = 4,比賽場數 = 2,且有 2 隊晉級。
- 第 4 輪:隊伍數 = 2,比賽場數 = 1,且有 1 隊被宣布為贏家。
總共比賽數 = 7 + 3 + 2 + 1 = 6。


解題思維:
參見這題(儘管本題錦標賽有自己的規則,但本質上一樣)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作