题目：https://leetcode-cn.com/contest/weekly-contest-177/problems/largest-multiple-of-three/ 题意：给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。 思路： 首先证明一个很常见的一个应用定理：对于一个长度为 n n n的十进制数 s s s，如果其所有的位数相加后模3为0，那么这个数本身模3也为0。 证明：设n个位数为 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an，由已知得 ( a 1 + a 2 + . . . + a n ) m o d 3 = = 0 (a_1+a_2+...+a_n)mod3==0 (a1+a2+...+an)mod3==0,该十进制数为 a 1 ∗ 1 0 n − 1 + a 2 ∗ 1 0 n − 2 + . . . + a n ∗ 1 0 0 a_1*10^{n-1}+a_2*10^{n-2}+...+a_n*10^{0} a1∗10n−1+a2∗10n−2+...+an∗100 = a 1 ∗ ( 1 0 n − 1 − 1 ) + a 2 ∗ ( 1 0 n − 2 − 1 ) + . . . + a n ∗ ( 1 0 0 − 1 ) + a 1 + a 2 + . . . + a n =a_1*(10^{n-1}-1)+a_2*(10^{n-2}-1)+...+a_n*(10^{0}-1)+a_1+a_2+...+a_n =a1∗(10n−1−1)+a2∗(10n−2−1)+...+an∗(100−1)+a1+a2+...+an 其中 ( 1 0 i − 1 ) m o d 3 = = 0 ( i > = 0 ) (10^i-1)mod3==0(i>=0) (10i−1)mod3==0(i>=0) 故 [ a 1 ∗ ( 1 0 n − 1 − 1 ) + a 2 ∗ ( 1 0 n − 2 − 1 ) + . . . + a n ∗ ( 1 0 0 − 1 ) ] m o d 3 = = 0 [a_1*(10^{n-1}-1)+a_2*(10^{n-2}-1)+...+a_n*(10^{0}-1)]mod3==0 [a1∗(10n−1−1)+a2∗(10n−2−1)+...+an∗(100−1)]mod3==0又 ( a 1 + a 2 + . . . + a n ) m o d 3 = = 0 (a_1+a_2+...+a_n)mod3==0 (a1+a2+...+an)mod3==0所以 [ a 1 ∗ ( 1 0 n − 1 − 1 ) + a 2 ∗ ( 1 0 n − 2 − 1 ) + . . . + a n ∗ ( 1 0 0 − 1 ) + a 1 + a 2 + . . . + a n ] m o d 3 = = 0 [a_1*(10^{n-1}-1)+a_2*(10^{n-2}-1)+...+a_n*(10^{0}-1)+a_1+a_2+...+a_n]mod3==0 [a1∗(10n−1−1)+a2∗(10n−2−1)+...+an∗(100−1)+a1+a2+...+an]mod3==0证毕。 在以上这个结论的基础上，再来思考这个题，要使得到的数最大，那么首先优先长度，即选的数越多越好，其次再考虑大小，这只要将数从大到小排序即可。 再应用上述结论，我们需要贪心地选数，使得选择的数数量尽量多，同时满足选的数相加模3为0。我们把数分为3类，模3为0，模3为1，和模3为2的。模3为0的数全部选去即可，模3为1的数，和模3为2的数可以匹配着选取，在有剩余时，再使剩下的数3个3个凑一对。 但这里要注意剩下的余数刚好剩2个的情况，这时这2个数如果和他之前同类的数相凑，可以凑3个，多了一个数位，如2,1,1,1的情况，选择2和1匹配只能得21，而3个1匹配就可以得到更大的数111。 最后，需要特判0的情况。
class Solution {
public:
string largestMultipleOfThree(vector& digits) {
int n = digits.size();
vector a[3],res;
for(int i = 0;i = 0;i--)
str+=char(res[i]+'0');
if(n && str[0] == '0') str = "0";//特判“0”的情况
return str;
}
};
