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;
    }
};

LeetCode-1363 Largest Multiple of Three