Last Updated on 2024-01-04 by Clay
題目
You are given a 0-indexed array nums consisting of positive integers.
There are two types of operations that you can apply on the array any number of times:
- Choose two elements with equal values and delete them from the array.
- Choose three elements with equal values and delete them from the array.
Return the minimum number of operations required to make the array empty, or -1 if it is not possible.
Example 1:Input: nums = [2,3,3,2,2,4,2,3,4] Output: 4 Explanation: We can apply the following operations to make the array empty: – Apply the first operation on the elements at indices 0 and 3. The resulting array is nums = [3,3,2,4,2,3,4]. – Apply the first operation on the elements at indices 2 and 4. The resulting array is nums = [3,3,4,3,4]. – Apply the second operation on the elements at indices 0, 1, and 3. The resulting array is nums = [4,4]. – Apply the first operation on the elements at indices 0 and 1. The resulting array is nums = []. It can be shown that we cannot make the array empty in less than 4 operations.
Example 2:Input: nums = [2,1,2,2,3,3] Output: -1 Explanation: It is impossible to empty the array.
Constraints:
2 <= nums.length <= 1051 <= nums[i] <= 106
解題思路
這題目本質上考的是，如果有一連串的數值可以選擇減 3 或減 2，那要將其全部歸零，使用的最小減去步數是多少？—— 當然，如果無法將數值歸零，則直接回傳 -1。
那該如何選擇最小步數？那自然是優先選擇減 3 了。唯一數值大於 3 卻不該減 3 的例外，就是當數值為 4 的情況，我們若減去 3 則剛好無法被 2 減去。
C++ 範例程式碼
class Solution {
public:
int minOperations(vector<int>& nums) {
// Init
int steps = 0;
unordered_map<int, int> counter;
// Count
for (int& num: nums) {
++counter[num];
}
// Check steps
for (auto& it: counter) {
int value = it.second;
if (value == 1) {
return -1;
}
else if (value % 3 == 1) {
steps += value / 3 - 1; // value / 3 = step...1, and 1 + 3 = 4, step -= 1,
steps += 2; // 4 / 2 = 2
}
else {
steps += value / 3;
steps += value % 3 / 2;
}
}
return steps;
}
};Python 範例程式碼
class Solution:
def minOperations(self, nums: List[int]) -> int:
# Init
steps = 0
counter = {}
# Count
for num in nums:
counter[num] = counter.get(num, 0) + 1
# Check steps
for value in counter.values():
if value == 1:
return -1
elif value % 3 == 1:
steps += value // 3 + 1 # value / 3 = step...1, and 1 + 3 = 4, step -= 1, 4 / 2 = 2, step += 2 => steps += value // 3 + 1
else:
steps += value // 3
steps += value % 3 // 2
return steps