526互联

1363. 形成三的最大倍数

发布时间 2023-04-10 18:00:57作者: zhangk1988

题目描述

给一个整数数组
问怎么选数字，可以让能得到的结果最大，同时这个接结果需要是3的倍数？

f1 分类讨论+ 贪心

基本分析

  1. 怎么判断能不能被3整除？和 % 3 == 0
  2. 怎么判断该从数组中删掉哪些数字？（1）和%3==1, 删最小的余1的数字，不行删俩最小的余2的数字；（2）和% 3 == 2，删最小的余2的数字或者俩最小的余1的数字
  3. 怎么构造出ans？从小到大枚举出现过的数字，如果该删就删，否则构造为结果

代码

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        cnt, modulu = [0] * 10, [0] * 3
        s = 0
        for d in digits:
            cnt[d] += 1
            modulu[d % 3] += 1
            s += d
        
        del_d, del_q = 0, 0
        if s % 3 == 1:
            del_d, del_q = (1, 1) if modulu[1] >= 1 else (2, 2)
        if s % 3 == 2:
            del_d, del_q = (2, 1) if modulu[2] >= 1 else (1, 2)
        
        ans = ""
        for i in range(10):
            for j in range(cnt[i]):
                if i % 3 == del_d and del_q > 0:
                    del_q -= 1
                else:
                    ans += str(i)
        
        if len(ans) > 0 and ans[-1] == '0':
            return '0'
        else:
            return ans[::-1]

总结

  1. 根据和的%3的结果分类讨论
  2. 结果需要考虑是"0"的特殊情况