1363. 形成三的最大倍数（Rating 1822）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

1363. 形成三的最大倍数

Rating 1822

思路

一个比较常用的结论：如果一个数字所有位加起来是3的倍数，那么这个数就是3的倍数。

另外一个常用的结论：a % c = x, b % c = y, 那么 (a + b) % c = (x + y) % c

那么digits里所有的数字可以转换成3类

• 除3余0
• 除3余1
• 除3余2

那么这个问题就可以转化为：

找到尽可能多的数字，让这些数字对3的余数的和最终对3取余是0

正难则反

我们可以先把所有数字都用起来，看看这个数对3余几（所有数字对3的余数的和对3取余）

• 如果对3余0，那么这个数就满足要求了
• 如果对3余1，那么去掉1个最小的对3余1的数，或者去掉2个最小的对3余2的数，就可以满足要求
• 如果对3余2，那么去掉1个最小的对3余2的数，或者去掉2个最小的对3余1的数，就可以满足要求

最终记得再处理一下前导0

代码

class Solution:
    def largestMultipleOfThree(self, digits: List[int]) -> str:
        digits.sort(key=lambda x: -x) # 从大到小排序
        mod = 0 # 所有数字对3的余数
        last_mod1a, last_mod1b, last_mod2a, last_mod2b = -1, -1, -1, -1 # 记录最小的两个对3余1和2的数
        for idx, d in enumerate(digits):
            if d % 3 == 0:
                continue
            elif d % 3 == 1:
                mod = (mod + 1) % 3
                last_mod1a = last_mod1b
                last_mod1b = idx
            else: # d % 3 == 2
                mod = (mod + 2) % 3
                last_mod2a = last_mod2b
                last_mod2b = idx
        idx_rm = set()
        if mod == 0:
            pass
        elif mod == 1:
            if last_mod1b != -1:
                idx_rm.add(last_mod1b) # 去掉1个最小的对3余1的数
            else:
                idx_rm.add(last_mod2a) # 去掉2个最小的对3余2的数
                idx_rm.add(last_mod2b)
        else: # mod == 2
            if last_mod2b != -1:
                idx_rm.add(last_mod2b) # 去掉1个最小的对3余2的数
            else:
                idx_rm.add(last_mod1a) # 去掉2个最小的对3余1的数
                idx_rm.add(last_mod1b)
        ret = ''
        for idx, d in enumerate(digits):
            if idx in idx_rm:
                continue
            ret += str(d)
        idx = 0
        while len(ret) > 1 and ret[idx] == '0': # 去掉前导0
            ret = ret[1:]
        return ret