【题解】力扣1363形成三的最大倍数

更新于 分类于 ， 阅读次数： 本文字数： 2.1k 阅读时长 ≈ 2 分钟

一道数学有关的贪心题

题意

给一个数组，任意连接其中的数，使得这个数是三的倍数且最大，以字符串输出最大的数，如果有前导00 需要去掉

数据范围

数组长度1e41e4 ，数组里的数都是[0,9][0,9]

分析

这题我上来就想反了，先说说错误的而且反了的贪心思路。

错误思路

三的倍数显然每位数的和是三的倍数，所以每个能被三整除的数都可以直接放入序列，于是需要合理选择3k+1,3k+23k+1,3k+2 的数，最后字符串排个序就好了。

合理选择的话，直接贪了余11 余22 尽可能匹配，剩下的三个一组，模拟很好写，成功WA了，反例[1,1,1,2][1,1,1,2] 。

于是考虑剩下的数里，余11 有xx 个，余22 有yy 个，不妨设x<yx<y ，那么如果2x+(y−x)/3∗3>x/3∗3+y/3∗32x+(y-x)/3*3>x/3*3+y/3*3 就按之前的思路，否则就直接将剩下的全部33 个一组匹配，代码也很好写。

这个时候突然意识到，如果两组数合理的构造一下，很有可能出现两种情况的构造长度相同但都不是最大的数，可能是在某一个特定位置开始二者自己匹配，但反正之前的代码都是复制粘贴就没管，果然被数据卡了。

正确思路

看到解析说删除而不是构造，恍然大悟。

因为在构造过程中很难判定“最大”，而删除的工作量要小的多。

如果原数组和本身就是33 的倍数，显然排序去00 就结束了；

考虑原数组和模33 余11 ，那么解决方法最好的显然是删除11 个3k+13k+1 ；如果没有3k+13k+1 ，说明一定可以删22 个3k+23k+2 （一定有3n−13n-1 个3k+23k+2 才能形成模33 余11 ，删更多不值）。

考虑原数组和模33 余11 ，那么解决方法最好的显然是删除11 个3k+23k+2 ；如果没有3k+23k+2 ，说明一定可以删22 个3k+13k+1 （一定有3n−13n-1 个3k+13k+1 才能形成模33 余22 ，删更多不值）。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        string ans;
        int cnt[10]={0,0,0,0,0,0,0,0,0,0}; // 计数[0,9]的出现次数
        int sum=0;	// 每位求和
        for(auto it:digits)
        {
            sum+=it;
            cnt[it]++;
        }
        if(sum%3==1) {
            bool flag=false;
            for(int i=1;i<9;i+=3)
                if(cnt[i]) {
                    flag=true;
                    cnt[i]--;	// 删除一个3k+1
                    break;
                }
            if(!flag) { // 如果没有删除掉3k+1，需要删两个3k+2
                for(int i=2;i<9;i+=3) {
                    if(cnt[i])	// 这里写的有点抽象
                    {
                        if(--cnt[i]&&!flag) { 
                        // 有数一定先删掉，如果能删第二个/需要删第二个，就去删
                            --cnt[i];
                            flag=true; // 标记已经删掉两个了
                        }
                        if(flag)	// 如果已经删掉两个了就退出
                            break; 
                        flag=true;	
                        // 下一轮一定会删掉一个（if那里），相当于已经删掉了，只要别再进一次if就行，所以把flag置1
                    }
                }
            }
        }
        if(sum%3==2) {
            bool flag=false;
            for(int i=2;i<9;i+=3)
                if(cnt[i]) {
                    flag=true;
                    cnt[i]--;
                    break;
                }
            if(!flag) {
                for(int i=1;i<9;i+=3) {
                    if(cnt[i])
                    {
                        if(--cnt[i]&&!flag) {
                            --cnt[i];
                            flag=true;
                        }
                        if(flag)
                            break;
                        flag=true;
                    }
                }
            }
        }
        for(int i=9;i>=0;i--)
            while(cnt[i]--)
                ans+=i+'0';
        if(ans.length()&&ans[0]=='0')
            ans="0";
        return ans;
    }
};