给你一个整数数组 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"
提示
首先要知道一个小学生都知道的定理:如果一个数可以被 整除,那么它的每一位上的数之和也可以被 整除,反之也成立。
那么问题就转化为了挑选出最多的数,使得和是 的倍数。我们可以先求出所有数之和,记为 ,然后有如下三种情况:
最终将剩下的数按照从小到大顺序排序,拼接在一起就行了。
注意如果有前导 ,就说明答案就是 。
时间复杂度为 。
class Solution {
public:
int del(vector<int>& cnt, int q) {
for (int i = 0; i <= 9; ++i) {
if (i%3 == q && cnt[i]) {
return --cnt[i];
}
}
return -1;
}
string largestMultipleOfThree(vector<int>& digits) {
vector<int> cnt(10, 0);
int sum = 0;
for (auto x : digits) {
cnt[x]++;
sum += x;
}
int q = sum % 3;
if (q && del(cnt, q) < 0) {
del(cnt, 3-q);
del(cnt, 3-q);
}
string res = "";
for (int i = 9; i >= 0; --i) {
while (cnt[i]--) {
res += i+'0';
}
}
if (res.size() && res[0] == '0') return "0";
return res;
}
};
作者简介:godweiyang,知乎同名,华东师范大学计算机系硕士在读,方向自然语言处理与深度学习。喜欢与人分享技术与知识,期待与你的进一步交流~