难度: Hard
给你一个整数数组 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运行时间: 36 ms
内存: 16.4 MB
class Solution:
def largestMultipleOfThree(self, digits: List[int]) -> str:
counter=[0]*10
for d in digits:
counter[d]+=1
s=sum(k*v for k,v in enumerate(counter) if k%3)
no3=[1,2,4,5,7,8]
mod1=[1,4,7]
mod2=[2,5,8]
excess=s%3
if excess==1:
for i in mod1:
if counter[i]>0:
counter[i]-=1
break
else:
k=2
for i in mod2:
dif=min(counter[i],k)
counter[i]-=dif
k-=dif
if k==0:
break
else:
for i in no3:
counter[i]=0
elif excess==2:
for i in mod2:
if counter[i]>0:
counter[i]-=1
break
else:
k=2
for i in mod1:
dif=min(counter[i],k)
counter[i]-=dif
k-=dif
if k==0:
break
else:
for i in no3:
counter[i]=0
ret=[]
for i in range(9,0,-1):
if counter[i]:
ret.append(str(i)*counter[i])
if ret:
ret.append('0'*counter[0])
else:
ret.append('0'*min(counter[0],1))
return ''.join(ret)
首先通过计数排序的思路统计每个数字出现的次数，然后计算所有数字的总和。如果总和是3的倍数，那么就可以直接用这些数字组成最大的数。如果不是3的倍数，需要通过删除几个最小的数字来调整总和使其成为3的倍数。具体来说： 1. 计算总和模3的结果，如果余数为1，尝试先删除一个余数为1的数字，如果没有，再尝试删除两个余数为2的数字；如果余数为2，尝试先删除一个余数为2的数字，如果没有，再尝试删除两个余数为1的数字。 2. 删除数字后，按照从大到小的顺序组合剩余的数字，将结果转化为字符串。如果数字中包含0，则确保0只在最后出现，除非结果只有0。 3. 特别注意处理只有0或结果无法形成3的倍数的情况。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def largestMultipleOfThree(self, digits: List[int]) -> str:
counter = [0] * 10 # 用于统计每个数字的频率
for d in digits: # 统计频率
counter[d] += 1
s = sum(k * v for k, v in enumerate(counter) if k % 3 != 0) # 计算总和模3不为0的部分
mod1 = [1, 4, 7] # 余数为1的数字
mod2 = [2, 5, 8] # 余数为2的数字
excess = s % 3 # 总和模3的结果
if excess == 1: # 如果余数为1
if not any(counter[i] > 0 and counter[i] -= 1 for i in mod1): # 尝试删除一个模1的数字
k = 2
for i in mod2:
dif = min(counter[i], k)
counter[i] -= dif
k -= dif
if k == 0:
break
elif excess == 2: # 如果余数为2
if not any(counter[i] > 0 and counter[i] -= 1 for i in mod2): # 尝试删除一个模2的数字
k = 2
for i in mod1:
dif = min(counter[i], k)
counter[i] -= dif
k -= dif
if k == 0:
break
ret = []
for i in range(9, 0, -1): # 从大到小组合数字
if counter[i]:
ret.append(str(i) * counter[i])
if ret:
ret.append('0' * counter[0]) # 添加所有的0
else:
ret.append('0' * min(counter[0], 1)) # 只有0的情况
return ''.join(ret)
计算总和时主要关注模3不为0的部分是因为模3为0的数字本身就是3的倍数，不会影响总和是否为3的倍数。将这些数字加入总和中，总和的模3的结果不会改变。因此，关键在于如何处理那些模3后余1和余2的数字，通过适当的添加或移除这些数字，来使总和成为3的倍数。
首选删除一个余数为1的数字是因为这样可以最小化对数字总数的影响，从而尽可能保持结果数字的大和长。删除两个余数为2的数字虽然也可以达到使总和成为3的倍数的效果，但这样会损失更多的数字，可能导致结果数字变小。优先删除较少数量的数字有助于最大化最终形成的数字。
如果没有足够的数字可以删除来调整使总和成为3的倍数，那么无法形成有效的3的倍数。在这种情况下，如果输入中还包含其他数字，可以尝试重新组合其他的数字来形成最大的可能数字。如果只有不足以调整的余数1或2的数字，理论上会返回一个尽可能大的非3倍数数字，或者在某些实现中可能会返回空字符串，具体取决于题目要求和实现细节。
正确的实现方式是使用一个循环来遍历需要检查的数字，并在找到第一个可用的数字后立即减少其计数器的值并退出循环。例如，可以使用以下代码片段： found = False for i in mod1: if counter[i] > 0: counter[i] -= 1 found = True break if not found: # 实施其他策略，如删除两个余数为2的数字 这样可以确保只在找到第一个符合条件的数字时进行操作，并且可以在没有符合条件的数字时实施备用策略。