给你一个整数数组 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
返回的结果不应包含不必要的前导零。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/largest-multiple-of-three 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
容易错的数据:
[9,8,6,8,6]
[2,2,1,1,1]
[1,1,1,2]
[5,8]
1 or 4 or 7
,没有的话,删除2,5,8
中最小的2个2 or 5 or 8
,没有的话,删除1,4,7
中最小的2个class Solution {
public:
string largestMultipleOfThree(vector<int>& digits) {
int count[10] = {0}, i, sum = 0, time;
string ans;
for(i = 0; i < digits.size(); ++i)
{
count[digits[i]]++;//计数
sum += digits[i];//总和
ans += digits[i]+'0';//字符串
}
sort(ans.begin(), ans.end(),[](char& a, char& b){return a > b;});
if(sum%3 == 1)
{
i = ans.size()-1;
if(count[1]!=0||count[4]!=0||count[7]!=0)
{
for( ; i>=0; --i)
{
if(ans[i]=='1'||ans[i]=='4'||ans[i]=='7')
{
ans.erase(ans.begin()+i);
break;
}
}
}
else
{
time = 2;
for( ; i>=0; --i)
{
if(ans[i]=='2'||ans[i]=='5'||ans[i]=='8')
{
ans.erase(ans.begin()+i);
time--;
if(time == 0)
break;
}
}
}
}
else if(sum%3 == 2)
{
i = ans.size()-1;
if(count[2]!=0||count[5]!=0||count[8]!=0)
{
for( ; i>=0; --i)
{
if(ans[i]=='2'||ans[i]=='5'||ans[i]=='8')
{
ans.erase(ans.begin()+i);
break;
}
}
}
else
{
time = 2;
for( ; i>=0; --i)
{
if(ans[i]=='1'||ans[i]=='4'||ans[i]=='7')
{
ans.erase(ans.begin()+i);
time--;
if(time == 0)
break;
}
}
}
}
if(ans != "" && ans[0]=='0')
return "0";
return ans;
}
};
大佬优美解:
class Solution {
int cnt[10], sum;
string ans = "";
set<int> s;
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', s.insert(i);
if(s.size()==1 && s.count(0))
return "0";// [1,0,0] -> "0"
return ans;
}
};
作者:YusenZhang_chatc
链接:https://leetcode-cn.com/problems/largest-multiple-of-three/solution/c-qu-diao-zui-xiao-zhi-8ms-by-yusenzhang_chatc/