leetcode 1363

问题

Given an integer array of digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order.

Since the answer may not fit in an integer data type, return the answer as a string.

If there is no answer return an empty string.

Example 1:

1
2
Input: digits = [8,1,9]
Output: "981"

Example 2:

1
2
Input: digits = [8,6,7,1,0]
Output: "8760"

Example 3:

1
2
Input: digits = [1]
Output: ""

Example 4:

1
2
Input: digits = [0,0,0,0,0,0]
Output: "0"

Constraints:

  • 1 <= digits.length <= 10^4
  • 0 <= digits[i] <= 9
  • The returning answer must not contain unnecessary leading zeros.

分析

首先有“一个数如果其每一位相加之和可以被3整除，那么这个数就可以被3整除“。于是，最好的情况就是输入的数组中，所有数之和可以被3整除，这样整个数组所有的数都可以被用到，位数最多，然后令其从大到小进行排列，即可得出最终的答案。若所有数之和除以3余1，则从0-9中除以3余1的数（1、4、7）中，删除1个，或者从从0-9中除以3余2的数（2、5、8）中删除2个。若所有数之和除以3余2，则从0-9中除以3余2的数（2、5、8）中，删除1个，或者从从0-9中除以3余1的数（1、4、7）中删除2个。若不满足删除条件则返回空，否则将剩余的数从大到小进行排列输出最终的答案。

代码

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 getString(int t[]) {
        string ret;
        for (int i = 9; i >= 0; --i) {
            ret.append(t[i], '0' + i);
        }
        if (ret.size() != 0 && ret[0] == '0')
            return "0";
        return ret;
    }
    bool reduceOneOne(int t[]) {
        if (t[1] == 0 && t[4] == 0 && t[7] == 0)
            return false;
        
        if      (t[1] != 0) t[1]--;
        else if (t[4] != 0) t[4]--;
        else                t[7]--;
        return true;
    }
    bool reduceOneTwo(int t[]) {
        if (t[2] == 0 && t[5] == 0 && t[8] == 0)
            return false;
        if      (t[2] != 0) t[2]--;
        else if (t[5] != 0) t[5]--;
        else                t[8]--;
        return true;
    }
    bool reduceTwoOne(int t[]) {
        int OneSum = t[1] + t[4] + t[7];
        if (OneSum < 2)
            return false;
        reduceOneOne(t);
        reduceOneOne(t);
        return true;
    }
    bool reduceTwoTwo(int t[]) {
        int OneSum = t[2] + t[5] + t[8];
        if (OneSum < 2)
            return false;
        reduceOneTwo(t);
        reduceOneTwo(t);
        return true;
    }
    string largestMultipleOfThree(vector<int>& digits) {
        int t[10] = {0};
        int sum = 0;
        string ans;
        for (auto d: digits) {
            t[d]++;
            sum += d;
        }

        int x = sum%3;        
        if (x == 1) {
            if (reduceOneOne(t) || reduceTwoTwo(t))
                return getString(t);
        } else if (x == 2) {
            if (reduceOneTwo(t) || reduceTwoOne(t))
                return getString(t);
        } else {
            return getString(t);
        }

        return "";
    }
};