Posted on 2023-01-04 18:19
Uriel 閱讀(47)
評論(0) 編輯 收藏 引用 所屬分類:
貪心 、
閑來無事重切Leet Code
給定一堆task的難度值，每次可以完成2個或者3個難度一樣的task，問一共多少次可以完成所有task，貪心
先統計每一種難度值的出現次數，分以下幾種情況
1. 只出現一次，那么這個task無法被單獨完成，直接return -1
2. 出現mod 3=0次，那么每次完成3個此類task
3. 出現mod 3=1次，那么每次完成3個此類task，最后剩4個此類task每次完成2個
4. 出現mod 3=2次，那么每次完成3個此類task，最后剩2個此類task一次完成
1 #944
2 #Runtime: 2137 ms (Beats 43.75%)
3 #Memory: 26.8 MB (Beats 39.58%)
4
5 class Solution(object):
6 def minimumRounds(self, tasks):
7 """
8 :type tasks: List[int]
9 :rtype: int
10 """
11 cnt = Counter(tasks)
12 ans = 0
13 for i in cnt:
14 if cnt[i] == 1:
15 return -1
16 if cnt[i] % 3 == 0:
17 ans += cnt[i] / 3
18 elif cnt[i] % 3 == 1:
19 ans += 2 + (cnt[i] - 4) / 3
20 elif cnt[i] % 3 == 2:
21 ans += 1 + (cnt[i] - 2) / 3
22 return ans