JZX轻语：简
LeetCode 2244 - 完成所有任务需要的最少轮数
发表于2024年05月14日
本质思路就是遍历所有的任务，累加完成每一任务的最少轮数就行。而对于如果计算单个任务完成的最少轮数，一开始使用了动态规划，即完成i个相同任务的时间未MinRounds[i] = (MinRounds[i - 3], MinRounds[i - 2]) + 1；后面发现使用贪心即可：如果任务个数i满足被3整除，则最少轮数为i // 3；若i % 3 == 2，则先完成两个，然后再三个三个完成，即最少轮数为i // 3 + 1；若i % 3 == 1，则先完成两次-2，再三个三个完成，即2 + (i - 4) // 3 = i // 3 + 1。
一开始使用动态规划的做法：
class Solution:
def minimumRounds(self, tasks: List[int]) -> int:
cnt_map = {}
max_cnt = 0
for task in tasks:
cnt_map[task] = cnt_map.get(task, 0) + 1
max_cnt = max(max_cnt, cnt_map[task])
dp = [0] * (max_cnt + 1)
dp[0], dp[1] = 0, math.inf
for i in range(2, max_cnt + 1):
dp[i] = dp[i - 2]
if i - 3 >= 0:
dp[i] = min(dp[i - 2], dp[i - 3])
dp[i] += 1
ans = 0
for cnt in cnt_map.values():
if dp[cnt] == math.inf:
return -1
ans += dp[cnt]
return ans改进为贪心的做法：
class Solution:
def minimumRounds(self, tasks: List[int]) -> int:
cnt_map = {}
for task in tasks:
cnt_map[task] = cnt_map.get(task, 0) + 1
ans = 0
for cnt in cnt_map.values():
if cnt == 1:
return -1
if cnt % 3 == 0:
ans += cnt // 3
else:
ans += 1 + (cnt // 3)
return ans