每日算法系列【LeetCode 1363】形成三的最大倍数

每日算法系列【LeetCode 1363】形成三的最大倍数

题目描述

给你一个整数数组 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^40 <= digits[i] <= 9返回的结果不应包含不必要的前导零。

题解

代码

c++

class Solution {public: int del(vector& cnt, int q) { for (int i = 0; i <= 9; ++i) { if (i%3 == q && cnt[i]) { return --cnt[i]; } } return -1; } string largestMultipleOfThree(vector& digits) { vector 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; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。