Skip to content

LeetCode: 2870-Minimum Number of Operations to Make Array Empty 解題紀錄

題目

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 <= 105
  • 1 <= 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

References

Read More

Tags:

Leave a Reply