目录

1363:形成三的最大倍数(1822 分)

力扣第 177 场周赛第 4 题

题目

给你一个整数数组 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余1
    • 首先考虑 1、4、7,若存在,去掉 1 个即可
    • 否则要去掉 2、5、8 中的两个
  • 假如总和模3余2
    • 首先考虑 2、5、8,若存在,去掉 1 个
    • 否则要去掉 1、4、7 中的两个
  • 最后输出时,注意不能有前导 0

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        ct = Counter(digits)
        r = sum(digits)%3
        for x in ([1,4,7,2,5,8] if r==1 else [2,5,8,1,4,7]):
            while ct[x] and r:
                ct[x] -= 1
                r = (r-x)%3
        res = ''.join(str(x)*ct[x] for x in sorted(ct)[::-1])
        return res and (res.lstrip('0') or '0')

3 ms