240103-把数组变空的最少操作次数

题目要求

给定由正整数组成的0索引数组nums，可以对数组进行以下两种操作：

• 选择两个数值相等的元素，并将它们从数组删除。
• 选择三个数值相等的元素并从数组中删除。

返回使数组为空所需要的最少操作次数，如果不可能则返回-1。

思路

我的第一反应是，查找相同的元素并删除。直觉上让我想到用哈希表来解决，把元素对应的值变成字符出现的次数。然后2和3的最小公倍数是6，也就是说只有1，7，13...这个数列无法被2和3组合出来，除此之外的所有正整数都可以被2和3组合出来。因此我们在得到哈希表之后只需要用数值mod 6即可，如果出现余数是1则返回-1。如果可以变空，则需要返回最少操作次数，可以用除以6的值和余数来判断。显而易见尽可能多用3可以节省次数，因此假设除以6的值是a，余数是b，分情况讨论：

1. b = 0，这时当前的最优解是2a
2. b = 1，如上文讨论，直接返回-1并跳出循环。
3. b = 2，2a+1
4. b = 3，2a+1
5. b = 4，2a+2
6. b = 5，2a+2

综上，逻辑判断结束，只需要累加每次的最优解个数即可。然后发现并不是这样的，因为7也可以用2*2+3...，那么如果不用6，用3来讨论又会怎样？（发现不过的时候我觉得会不会是背包问题？）

1. b = 0，最优解是a
2. b = 1，最优解是(a-1)+2=a+1需要判断一下a是否大于0。
3. b = 2，最优解是a+1

再试一下！果断AC！

代码

class Solution {
public:
    int minOperations(vector<int>& nums) {
        unordered_map<int, int> map;
        for (int num : nums) {
            map[num] = 0;
        }
        for (int num : nums) {
            map[num] += 1;
        }
        int res = 0;
        for (const auto &kv : map) {
            // printf("%d, %d\n", kv.first, kv.second);
            int a = kv.second / 3;
            switch(kv.second % 3) {
                case 0:
                    res += a;
                    // printf("case 0: res = %d\n", res);
                    break;
                case 1:
                    if (a > 0) {
                        res += a + 1;
                    } else {
                        return -1;
                    }
                    // printf("case 1: res = %d\n", res);
                    break;
                case 2:
                    res += a + 1;
                    // printf("case 2: res = %d\n", res);
                    break;
            }
        }
        return res;
    }
};