Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間2年前 (2023/01/04 10:00)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串176/719 (看更多)

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： ---------------------------------- class Solution { public int minimumRounds(int[] tasks) { int rounds = 0; Map<Integer, Integer> map = new HashMap<>(); for (int task : tasks) { map.put(task, map.getOrDefault(task, 0) + 1); } for (Map.Entry<Integer, Integer> entry : map.entrySet()) { int amount = entry.getValue(); if (amount < 2) { return -1; } else if (amount % 3 == 0) { rounds += amount/3; } else { rounds += amount/3 + 1; } } return rounds; } } ---------------------------------- -- https://i.imgur.com/YPBHGGE.jpg