我得到了一个数字数组，其中元素的范围是0-9，我需要使用这些数字构造最大的数字，以使形成的数字可以被5和6整除。如何使用更好的算法有效地解决此问题。它不需要使用提供的所有数字，但是形成的数字应该最大并且可以被5和6整除。
tl; dr从本质上讲，该问题可以简化为找到总和可被三整除的最大数字子集。这可以在数字位数呈线性的时间内完成。
6的素数分解为2 * 3。假设您还需要除以5，这意味着您要形成一个可以被2、3和5整除的数字。
我们可以像这样将三个除数重新组合：2 * 5和3。换句话说，数字必须被10和3整除：
只有以零结尾的数字才能被10整除。这意味着，从数字数组中，您需要预留一个零以满足此除数要求。
只有数字总和为3的数字才能被3整除。这意味着，从数组的其余数字中，您正在寻找其总和可以被3整除的最长子集（通过选择较大的位数而不是较小的位数来打破长度限制） ）。
一旦有了数字，就可以通过将数字从最大到最小排序（最后出现零）来形成数字。
因此，我们将问题简化为寻找总和可被三整除的子集。我们首先要注意的是，所有可以被三整除的数字（即零，3、6和9）可以并且应该始终被选择。
至于其余的数字（1s，2s，4s，5s，7s和8s），您正在寻找可以被3整除的组（例如1 + 2、2 + 5 + 8等）。如果我们将等于1 mod 3的数字表示为①，将等于2 mod 3的数字表示为②，则形成这样的组的唯一可能性是①+①+①，①+②和②+②+②。
以下Python解决方案将所有这些想法融合在一起：
def get_n_mod_3(digits, n):
return sorted(d for d in digits if d % 3 == n)
def solve(digits):
# select all (0 mod 3)
selected = get_n_mod_3(digits, 0)
if not selected or selected[0] != 0:
# not divisible by both 2 and 5
return None
# select all (1 mod 3) and (2 mod 3)
set1 = get_n_mod_3(digits, 1)
set2 = get_n_mod_3(digits, 2)
while True:
# to simplify what follows, store the longer set in set1
# and the shorter in set2
if len(set1) < len(set2):
set1, set2 = set2, set1
if len(set1) == 3 and len(set2) < 2:
selected.extend(set1)
break
elif set1 and set2:
selected.append(set1.pop())
selected.append(set2.pop())
elif len(set1) < 3:
break
return ''.join(map(str, sorted(selected, reverse=True)))
print solve([1, 4, 2, 2, 9, 0, 2, 1, 5, 5, 7, 2, 0, 8, 1, 1, 8])
（要将其变成线性时间解决方案，我们要做的就是sorted()用计数sort代替O（n logn）调用。）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句