形成三的最大倍数 - Leetcode 1363
给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。
由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。
如果无法得到答案，请返回一个空字符串。
示例 1：
输入：digits = [8,1,9]
输出："981"
示例 2：
输入：digits = [8,6,7,1,0]
输出："8760"
示例 3：
输入：digits = [1]
输出：""
示例 4：
输入：digits = [0,0,0,0,0,0]
输出："0"
提示：
- 1 ≤ ≤ 104
- 0 ≤ digits[i] ≤ 9
- 返回的结果不应包含不必要的前导零。
分析：
不要考虑选择哪些数，反过来，考虑不取哪些数。
原因如下：
当我们考虑一个大整数（位数比较多）能否被 3 整除时，比较容易的方式是对这个数的各位进行求和 sum，然后看 sum 是否能够整除 3。
重点： 在任何情况下，当我们对 3 取模时，若余数不为 0，那我们至多再删去两个数，就能够使得剩下的数求和能够整除 3。
因此，考虑不取哪些数更加容易。
下面我们分情况讨论：
- 若 sum % 3 = 1，那么我们可以删除一个模 3 余 1 的数，或者删除两个模 3 余 2 的数。又因为要满足数尽量大，所以我们可以优先考虑删除一个数，若不存在，则再考虑删除两个最小的的数。
- 若 sum % 3 = 2，同理。
代码：
class Solution {
public:
int cnt[10], cnt_3[4];
string largestMultipleOfThree(vector<int>& digits)
{
int n = digits.size();
int sum = 0;
for(int i = 0; i < n; i ++)
++ cnt[digits[i]],
++ cnt_3[digits[i] % 3],
sum += digits[i];
if(sum % 3 == 1)
{
if(cnt_3[1])
{
for(int i = 1; i <= 7; i ++)
if(i % 3 == 1 && cnt[i])
{
-- cnt[i];
break;
}
}
else
{
int k = 0;
for(int i = 2; i <= 8; i ++)
if(i % 3 == 2 && cnt[i] && k < 2)
{
if(cnt[i] >= 2)
{
cnt[i] -= 2;
break;
}
else
{
-- cnt[i];
++ k;
}
}
}
}
if(sum % 3 == 2)
{
if(cnt_3[2])
{
for(int i = 2; i <= 8; i ++)
if(i % 3 == 2 && cnt[i])
{
-- cnt[i];
break;
}
}
else
{
int k = 0;
for(int i = 1; i <= 7; i ++)
if(i % 3 == 1 && cnt[i] && k < 2)
{
if(cnt[i] >= 2)
{
cnt[i] -= 2;
break;
}
else
{
-- cnt[i];
++ k;
}
}
}
}
string res = "";
for(int i = 9; i >= 0; i --)
if(cnt[i])
{
for(int j = 0; j < cnt[i]; j ++)
res += '0' + i;
}
if(res[0] == '0') res = "0";
return res;
}
};