題目出處

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。

Reference

• [Java/C++/Python] Sum up (freq + 2) / 3