Re: [闲聊] 每日LeetCode

楼主: Rushia (みけねこ的鼻屎)   2023-01-04 10:00:48
2244. Minimum Rounds to Complete All Tasks
给你一个阵列tasks表示一堆任务,task[i]表示第i个任务的难度,我们每一轮可以
完成2~3个同一种难度的任务,求出最少几轮可以完成所有任务,若无法完成所有任
务则返回-1。
Example:
Input: tasks = [2,2,3,3,2,4,4,4,4,4]
Output: 4
Explanation:
第一轮可以做3个难度2的任务
第二轮可以做2个难度3的任务
第三轮可以做3个难度4的任务
第四轮可以做2个难度4的任务
最少需做四轮
Input: tasks = [2,3,3]
Output: -1
Explanation:
第一轮可以做两个难度3的任务
第二轮只剩下一个难度1的任务所以无法做完。
思路:
1.先用一个map统计所有难度的任务的出现次数。
2.遍历每个难度的次数,如果次数为1表示当前难度无法完成直接返回-1。
3.因为我们要求最小轮次,所以我们要尽可能的在每一轮完成最多任务
(换句话说就是尽可能的每轮都完成三次任务),对每轮可以完成的任务
次数进行贪婪,分两个case:
(1)若次数可以被三整除,则每轮都做三个任务会是最小次数。
9 = 3 + 3 + 3
(2)若次数不被三整除,则每一轮都做三个任务且最后一轮改成做两个任务两轮
即是最小次数。
7 = 3 + [3] => 3 + [2 + 2]
4.将每种难度的最小次数累加后返回之。
Java Code:
作者: pandix (面包屌)   2023-01-04 10:01:00
大师
作者: Jaka (Jaka)   2023-01-04 10:04:00
大师

Links booklink

Contact Us: admin [ a t ] ucptt.com