[LeetCode] 1363. Largest Multiple of Three 形成三的最大倍数

Given an array of digits digits, return the largest multiple of three that can be formed by concatenating some of the given digits in any order. If there is no answer return an empty string.

Since the answer may not fit in an integer data type, return the answer as a string. Note that the returning answer must not contain unnecessary leading zeros.

Example 1:

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

Example 2:

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

Example 3:

Input: digits = [1]
Output: ""

Constraints:

• 1 <= digits.length <= 10^4
• 0 <= digits[i] <= 9

这道题说是给了一个只含有数字0到9的数组 digits，现在说是可以在数组取出任意的数字，需要拼成一个3的倍数，返回可以拼出的最大的数字。根据题目中的例子不难理解题意，当然这里我们不能用暴力搜索的方法，比如找出所有的子集，然后判断是否能整除3，这种方法太不高效了，因为数字的个数最多有一万个，子集的个数太多了，不能一一验证。那么只能另辟蹊径，即然是要拼成3的倍数，在小学就应该学过能被3整除的数字的特性，就是每一位上的数字加起来也能被3整除，可以利用这个性质来做。

这里将数组中的每个数字都加起来，判断得到的数字之和对3取余，若能整除，说明每个数字都可以使用上，返回数字中就把大的放到前面就可以了。难点就在于如何处理不能整除的情况，这里的余数只有两种情况，1和2。若余数为1的话，最理想的情况就是直接去除掉一个1，但原数组中不一定有1，或者去掉一个4，或者7，都可以让余数为0。假如 1，4，7 这三个数字都不存在，那么只能考虑去除两个数字，比如2和2，2和5，或者5和8等等。同理，若余数为2的话，最理想的情况就是直接去除掉一个2，但原数组中不一定有2，或者去掉一个5，或者8，都可以让余数为0。假如 2，5，8 这三个数字都不存在，那么只能考虑去除两个数字，比如1和1，1和4，或者4和7等等。

分析到这里，应该就变得容易多了，新建两个数组 rem1 和 rem2，其中 rem1 中按顺序放入 1，4，7，2，5，8，rem2 中按顺序放入 2，5，8，1，4，7。为了快速知道某个数字是否存在，统计 digits 数组中每个数字出现的个数，可以用一个长度为 10 的数组 cnt 来统计0到9每个数字出现的次数，在统计的过程中同时计算出数组和 sum。接下来进行 while 循环，条件是 sum 对3取余不为0，然后用一个 for 循环遍历，按顺序从 rem1 或者 rem2 中取数验证，判断若 sum 对3取余的余数是1，并且此时的 rem1[i] 数字存在的话，则用 sum 减去 rem1[i]，并且对应的在 cnt 中的计数自减1，这样的话就可以按顺序去尽可能的移除较小的数，从而使得余数变为0。同理，若 sum 对3取余的余数是2，并且此时的 rem2[i] 数字存在的话，则用 sum 减去 rem2[i]，并且对应的在 cnt 中的计数自减1，参见代码如下：

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        string res;
        vector<int> rem1{1, 4, 7, 2, 5, 8}, rem2{2, 5, 8, 1, 4, 7}, cnt(10);
        int sum = 0;
        for (int digit : digits) {
            ++cnt[digit];
            sum += digit;
        }
        while (sum % 3 != 0) {
            for (int i = 0; i < 6; ++i) {
                if (sum % 3 == 1 && cnt[rem1[i]]) {
                    sum -= rem1[i];
                    --cnt[rem1[i]];
                    break;
                } else if (sum % 3 == 2 && cnt[rem2[i]]) {
                    sum -= rem2[i];
                    --cnt[rem2[i]];
                }
            }
        }
        for (int i = 9; i >= 0; --i) {
            res += string(cnt[i], '0' + i);
        }
        return res.size() && res[0] == '0' ? "0" : res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1363

参考资料：

https://leetcode.com/problems/largest-multiple-of-three/

https://leetcode.com/problems/largest-multiple-of-three/solutions/532860/simple-solution-with-brief-explanation-time-o-n-space-o-10-constant/

LeetCode All in One 题目讲解汇总(持续更新中...)