每日算法系列【LeetCode 1363】形成三的最大倍数

输入：
digits = [8,1,9]
输出：
"981"

输入：
digits = [8,6,7,1,0]
输出：
"8760"

输入：
digits = [1]
输出：
""

输入：
digits = [0,0,0,0,0,0]
输出：
"0"

class Solution {
public:
    int del(vector<int>& cnt, int q) {
        for (int i = 0; i <= 9; ++i) {
            if (i%3 == q && cnt[i]) {
                return --cnt[i];
            }
        }
        return -1;
    }

    string largestMultipleOfThree(vector<int>& digits) {
        vector<int> cnt(10, 0);
        int sum = 0;
        for (auto x : digits) {
            cnt[x]++;
            sum += x;
        }
        int q = sum % 3;
        if (q && del(cnt, q) < 0) {
            del(cnt, 3-q);
            del(cnt, 3-q);
        }
        string res = "";
        for (int i = 9; i >= 0; --i) {
            while (cnt[i]--) {
                res += i+'0';
            }
        }
        if (res.size() && res[0] == '0') return "0";
        return res;
    }
};