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