推 sustainer123: 大師 01/04 12:42
※ 編輯: Rushia (122.100.73.13 臺灣), 01/04/2024 12:43:34
https://leetcode.com/problems/minimum-number-of-operations-to-make-array-empty/description
2870. Minimum Number of Operations to Make Array Empty
給你一個整數陣列nums我們可以對裡面的數字做兩種操作：
1.刪除兩個相同數字
2.刪除三個相同數字
求出最少需要幾次操作可以讓陣列為空，如果不能則返回-1。
思路：
1.先計算出每個數字的出現次數。
2.對每個數字的最小刪除次數作判斷，如果次數為1表示不可能刪除所以返回-1。
3.因為2和3可以組成任何大於1的數字，且用3去刪除的操作次數一定比用2少，對這一點
做貪婪：
case1 => 若可被3整除，返回 n/3
case2 => 否則若 n-2 可以被3整除，返回 1 + (n-2)/3
case3 => 否則返回2 + (n-4)/3
(n-6) 回到case1
4.把所有結果加總即可。
Java Code:
------------------------------------------
class Solution {
public int minOperations(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.compute(num, (k, v) -> v == null ? 1 : v + 1);
}
int res = 0;
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
int cnt = entry.getValue();
if (cnt == 1) {
return -1;
} else if (cnt % 3 == 0) {
res += cnt/3;
} else if ((cnt - 2) % 3 == 0) {
res += 1 + (cnt - 2)/3;
} else {
res += 2 + (cnt - 4)/3;
}
}
return res;
}
}
------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1704343274.A.8A6.html