題目出處
2244. Minimum Rounds to Complete All Tasks
難度
medium
個人範例程式碼
class Solution:
def minimumRounds(self, tasks: List[int]) -> int:
# 1: -1 round
# 2: 1 round
# 3: 2 rounds
# 3k: k rounds
# 3k+1: 4=3(k-1)+2+2, k+1 times
# 3k+2: 5=3(1)+2, k+1 times
counters = Counter(tasks)
ans = 0
for num_of_task in counters.values():
if num_of_task <= 1:
return -1
else:
# 3 = 1
# 4 = 2
# 5 = 2
# 6 = 2
ans += (num_of_task+2)//3
return ans
算法說明
這題考的是數學歸納法的概念，比較是數學的範圍
我們推論：
- 1: -1 round
- 2: 1 round
- 3: 2 rounds
- 3k: k rounds
- 3k+1: 4=3(k-1)+2+2, k+1 times
- 3k+2: 5=3(1)+2, k+1 times
而為了計算方便，我們可以做一些使計算上方便的技巧。
- 3 = 1
- 4 = 2
- 5 = 2
- 6 = 2
我們透過移動 k+2 使得 // 3 後能夠直接得到我們要的數字。
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
x
Boundary conditions
只要發現其中一個任務不可能執行完成，提早 return -1。