Leetcode 1363:形成三的最大倍数(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1363:形成三的最大倍数(超详细的解法!!!)

in leetcode with 0 comment

给你一个整数数组 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"

提示:

解题思路

首先要知道一个定理:能被3整除的数,其各位数之和也能被3整除。

对于任意正整数b,其十进制表示为$a_n...a_1a_0$,即:

  • $b=\sum_{n-1}^Na_n10^n$

由于

  • $10^n\ mod\ 3=[9*10^{n-1}+10^{n-1}]\ mod\ 3=10^{n-1}\ mod\ 3=...=10\ mod\ 3=1$

因此,得证。

那么剩下的问题就和Leetcode 1262:可被三整除的最大和一模一样了。

遍历整个数组然后将数分成三个部分,%3==0%3==1%3==2

然后整个数组的和sum_all3等于0,那么将这些数从大到小排序后合成的数就是最大值了。

如果等于1,那么我们需要从%3==1的数(只有1、4、7)中选一个最小的数t1,然后再从%3==2(只有2、5、8)中选两个最小的数并计算和t2,比较t1t2选择最小的,然后从数组中去掉这些数,最后将剩余的数从大到小排序。

如果等于2,那么我们需要从%3==2的数中选一个最小的数t1,然后再从%3==1中选两个最小的数并计算和t2,比较t1t2选择最小的,然后从数组中去掉这些数,最后将剩余的数从大到小排序。

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits.sort()
        b1, b2, n = [], [], len(digits)
        for i in range(n):
            if digits[i] % 3 == 1 and len(b1) < 2: b1.append(i)
            if digits[i] % 3 == 2 and len(b2) < 2: b2.append(i)
        
        def get_result(x, y):
            res = ""
            for i in range(n - 1, -1, -1):
                if i == x or i == y: continue
                res += str(digits[i])
            
            if res and res[0] == "0": return "0"
            return res
        
        t = sum(digits) % 3
        if t == 1:
            if len(b1) >= 1:
                return get_result(b1[0], -1)
            return get_result(b2[0], b2[1])
        elif t == 2:
            if len(b2) >= 1:
                return get_result(b2[0], -1)
            return get_result(b1[0], b1[1])
        return get_result(-1, -1)

评论区大佬提出了一种更加优秀的解法,就是通过基数排序可以实现O(n)的时间复杂。具体做法如下:

分别通过所有数字出现的次数cnt,那么%3==1的个数就等于b1 = cnt[1] + cnt[4] + cnt[7]%3==2的个数就等于b2 = cnt[2] + cnt[5] + cnt[8],注意此时b1b2是数值而不是数组。接着可以推测出t=sum(digits)%3=(b1 + b2*2)%3。然后就是上述的算法判断t值大小,根据大小判断b1b2减少多少。最后遍历整个cnt将结果输出,注意遍历的过程中除了考虑cnt中对应元素的变化还需考虑b1b2的变化。

最后就是边界情况的考虑,也就是排除"0"开始的情况。

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        cnt = [0] * 10
        for i in digits: cnt[i] += 1
            
        b1, b2 = cnt[1] + cnt[4] + cnt[7], cnt[2] + cnt[5] + cnt[8]
        t = (b1 + b2 * 2) % 3
        
        if t == 1:
            if b1 >= 1: b1 -= 1
            else: b2 -= 2
        elif t == 2:
            if b2 >= 1: b2 -= 1
            else: b1 -= 2
                
        res = ""
        for i in range(9, -1, -1):
            if i % 3 == 0:
                while cnt[i]:
                    res += str(i)
                    cnt[i] -= 1
            elif i % 3 == 1 and b1:
                while cnt[i] and b1:
                    res += str(i)
                    cnt[i] -= 1
                    b1 -= 1
            else:
                while cnt[i] and b2:
                    res += str(i)
                    cnt[i] -= 1
                    b2 -= 1
        
        if res and res[0] == "0": return "0"
        return res

reference:

https://leetcode-cn.com/problems/largest-multiple-of-three/solution/fen-lei-tao-lun-by-zhu-zhen-yu-ajz34/

https://leetcode.com/problems/largest-multiple-of-three/discuss/517704/Java-Basic-Multiple-of-3-Clean-code-O(N)-~-2ms

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses