题目描述
给你一个整数数组 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
- 返回的结果不应包含不必要的前导零。
题解
代码
c++
classSolution { public: intdel(vector<int>&cnt, intq) { for (inti=0; i<=9; ++i) { if (i%3==q&&cnt[i]) { return--cnt[i]; } } return-1; } stringlargestMultipleOfThree(vector<int>&digits) { vector<int>cnt(10, 0); intsum=0; for (autox : digits) { cnt[x]++; sum+=x; } intq=sum%3; if (q&&del(cnt, q) <0) { del(cnt, 3-q); del(cnt, 3-q); } stringres=""; for (inti=9; i>=0; --i) { while (cnt[i]--) { res+=i+'0'; } } if (res.size() &&res[0] =='0') return"0"; returnres; } };
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
