【贪心】个人练习-Leetcode-1363. Largest Multiple of Three

题目链接：https://leetcode.cn/problems/largest-multiple-of-three/

题目大意：给出一系列digit(从0到9)，求它们能够组成的【最大的】【能被3整除的】整数，以string形式返回。

思路：初始的想法是，从高位9到低位0，往空string中逐个添加digit，遇到合法的就保存，如果是非法的就先暂存，因为可能遇到之后的digit就合法了。然而这样会有一个问题，即它默认从高位到低位添加digit并且默认前面的digit都会被添加。看起来似乎因为是从高位开始的，因为不合法被舍弃的digit也是最小的，好像满足，实际上会有问题。例如[1, 1, 1, 2]，构成的合法最大数应该是111，然而，如果默认添加高位，则会变成21。

可以看出，并非取的位数高的数字就好，而是取的位数多的同时尽量让位数高。因此应该重新分析。

假设所有digit之和是tot，如果tot % 3 == 0，那么所有digit都添加并且从高到低添加即可。如果不是，实际上应该分别考虑tot % 3 == 1和tot % 3 == 2的情况，这两种情况应该分别从1, 4, 7和2, 5, 8这些数字中做删减，这样才能使得减少的位数最少，并且减少的digit也是最小的。

注意，0, 3, 6, 9这些数字是无论如何都可以添加的。即使其他数字无法构成【能被3整除的数列】（对应代码中flag == false的情况），如果有上述这些数字，也是可以构成合法的数列的。

最后考虑特殊情况，如果全为0，那么只返回一个"0"

完整代码

class Solution {
public:string largestMultipleOfThree(vector<int>& digits) {int cnt[10] = {};int tot = 0;for (auto x : digits) {cnt[x]++;tot += x;}string num = "";bool flag = false;if (tot % 3 == 0) {flag = true;}else if (tot % 3 == 1) {for (int x = 1; x < 10; x+=3) {while (cnt[x] && tot % 3 != 0) {tot -= x;cnt[x]--;}if (tot % 3 == 0) {flag = true;break;}}}else {for (int x = 2; x < 10; x+=3) {while (cnt[x] && tot % 3 != 0) {tot -= x;cnt[x]--;}if (tot % 3 == 0) {flag = true;break;}}}if (flag) {for (int dg = 9; dg >= 0; dg--) {if (cnt[dg]) {string str(cnt[dg], '0'+dg);num += str;}}}else {for (int dg = 9; dg >= 0; dg-=3) {if (cnt[dg]) {string str(cnt[dg], '0'+dg);num += str;}}}if (num.size() && num[0] == '0')return "0";return num;}
};