1363. Largest Multiple of Three

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

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:

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

Example 2:

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

Example 3:

Input: digits = [1]
Output: ""

Example 4:

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的倍数，最大能组成的数可能是多少。这里要利用到一个性质，三的倍数满足每个位上的数字相加也是三的倍数，同时当余数不为0时，去掉会导致余数为1或2的数也就能生成3的倍数。分为两种情况，单个数导致的余数为1或2，和两个数相加除3导致的余数为1或2。不用考虑三个数的情况，因为（不考虑0）三个数和一定大于等于3，以被前面两种情况包括。因此在从大到小排序后满足数尽量大后，对以上Ⅴ种情况分类讨论。

class Solution {
public:
    string largestMultipleOfThree(vector<int>& digits) {
        sort(digits.begin(), digits.end(), greater<int>());
        int sum = accumulate(digits.begin(), digits.end(), 0);
        if (sum == 0) return "0";
        const int N = digits.size();
        const auto print = [&]() {
            if (digits[0] == '0') return to_string(0);
            stringstream ss;
            for (const auto d : digits) {
                if (d == -1) continue;
                ss << d;
            }
            return ss.str();
        };
        if (sum % 3 == 0) return print();
        if (sum % 3 == 1) {
            for (int i = N - 1; i >= 0; --i) {
                if (digits[i] == 1 or digits[i] == 4 or digits[i] == 7) {
                    digits[i] = -1;
                    return print();
                }
            }
            for (int i = N - 1, cnt = 0; i >= 0; --i) {
                if (digits[i] == 2 or digits[i] == 5 or digits[i] == 8) {
                    digits[i] = -1;
                    if (cnt == 1) {
                        return print();
                    }
                    ++cnt;
                }
            }
        }
        if (sum % 3 == 2) {
            for (int i = N - 1; i >= 0; --i) {
                if (digits[i] == 2 or digits[i] == 5 or digits[i] == 8) {
                    digits[i] = -1;
                    return print();
                }
            }
            for (int i = N - 1, cnt = 0; i >= 0; --i) {
                if (digits[i] == 1 or digits[i] == 4 or digits[i] == 7) {
                    digits[i] = -1;
                    if (cnt == 1) {
                        return print();
                    }
                    ++cnt;
                }
            }
        }
        return "";
    }
};