LeetCode-1363 Largest Multiple of Three

Description

给出\(digits[]\)数组，每个元素范围\([1, 9]\)，让它拼接出最长的能被3整除的字符串

Constraints

\(digits[]\)长度不超过\(10^4\)

Solution

首先，一个非负整数被3整除的性质是数位之和也被3整除；其次，可以用桶按\(%3\)进行分类讨论，这里筛除最小的无法拼凑的数位，剩下的只需按从大到小排列即可

Code

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        int bucket[10] {};
        long sum = 0;
        for(auto d : digits) sum += d, bucket[d]++;
        
        auto consumeOne = [&](int startDigit) {
            for(int i = startDigit; i <= 9; i += 3) {
                if(bucket[i] > 0) {
                    bucket[i]--;
                    return true;
                }
            }
            return false;
        };
        
        if(sum % 3 == 1) {
            // 优先从1找，只要砍1个数就好了，找字面最小的
            if(!consumeOne(1)) {
                // 桶1不够用，从2里找，（2+2） % 3 == 1
                consumeOne(2);
                consumeOne(2);
            }
            // 如果还是不行？怎么可能嘛

        } else if(sum % 3 == 2) {
            // 先从2开始吧，一个就够了
            if(!consumeOne(2)) {
                consumeOne(1);
                consumeOne(1);
            }
        }
        std::string ans;
        for(int i = 9; ~i; --i) {
            while(bucket[i]--) ans += char('0'+i);
        }
        if(ans.size() > 0 && ans[0] == '0') ans = "0";
        return ans;
    }
};

Link

LeetCode-1363 Largest Multiple of Three