原文链接: https://leetcode-cn.com/problems/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: ""

Example 4:

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

 

Constraints:

• 1 <= digits.length <= 104
• 0 <= digits[i] <= 9

中文题目

给你一个整数数组 digits，你可以通过按任意顺序连接其中某些数字来形成 3 的倍数，请你返回所能得到的最大的 3 的倍数。

由于答案可能不在整数数据类型范围内，请以字符串形式返回答案。

如果无法得到答案，请返回一个空字符串。

 

示例 1：

输入：digits = [8,1,9]
输出："981"

示例 2：

输入：digits = [8,6,7,1,0]
输出："8760"

示例 3：

输入：digits = [1]
输出：""

示例 4：

输入：digits = [0,0,0,0,0,0]
输出："0"

 

提示：

• 1 <= digits.length <= 10^4
• 0 <= digits[i] <= 9
• 返回的结果不应包含不必要的前导零。

通过代码

高赞题解

如果取模3等于0，那其实可以都要，如果是1，那就得去掉一个1或者两个2，如果是2那就得去掉一个2或者两个1.
而这些删掉一个数的函数其实是类似的，可以反复调用。
注意在如果全是0输出0而不是00000. 删完数之后判断答案的最高位是不是0即可。
学习一下JOHNKRAM的压行操作

class Solution {
    int cnt[10],sum;
    string ans = "";
    int del(int m)
    {
        for(int i=m;i<=9;i+=3)if(cnt[i]){cnt[i]--;return 1;}
        return 0;
    }
public:
    string largestMultipleOfThree(vector<int>& d) {
        for(auto x:d)cnt[x]++,sum+=x;
        if(sum%3==1)if(!del(1))del(2),del(2);
        if(sum%3==2)if(!del(2))del(1),del(1);
        for(int i=9;i>=0;i--)while(cnt[i]--)ans+=i+'0';
        if(ans.size() && ans[0] == '0') return "0";
        return ans;
    }
};

(去掉了set变成4ms)

统计信息

通过次数	提交次数	AC比率
5297	14430	36.7%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言