寻找排列时减少运行时间

Question

我正在研究 Google 的 FooBar 挑战之一，只是为了好玩，运行在 Google 的运行中执行时遇到了超出时间限制的错误】时间环境。我的解决方案运行在我的本地开发环境中很好 - 并且很快就可以看到。

这是我的代码：

from itertools import permutations

def answer(l):
    options = []
    for r in range(1, len(l) + 1):
        for p in permutations(l, r=r):
            n = int(''.join(map(str, p)))
            if n % 3 == 0:
                options.append(n)
    numbers = sorted(options, reverse=True)
    return numbers[0]

l = [3, 1, 4, 1, 5, 9]
#l = [3, 1, 4, 1]
print(answer(l))

目标是从传入的数字列表中找到可被 3 整除的最大数字。

两个例子的输出应该是：

[3, 1, 4, 1, 5, 9] => 94311
[3, 1, 4, 1] => 4311

根据生成从最大到最小（而不是从最小到最大）排列然后突破的注释，我修改了代码。反对，它在本地环境中工作，但 Google 运行time 表示已超过时间限制：

def answer(l):
    options = []
    l = sorted(l, reverse=True)
    for r in range(len(l) + 1, 1, -1):
        for p in permutations(l, r=r):
            n = int(''.join(map(str, p)))
            if n % 3 == 0:
                return n
    return 0

我正在根据 permutations docs 对输入列表进行排序，表示如果输入已排序，元组将被排序。然后，因为它应该被排序，所以它第一次找到一个可以被 3 整除的值，这将是最大值

如我所说，我的代码（两个版本）都有效。但是，我似乎运行ning 比 Google 预期的要长。如何减少上述代码的运行时间？

Answer 1

最高数字的位数最多。所以对于一个大小为 n 的列表，搜索应该从 n 开始并继续到 n-1， n-2...
能被3整除的数总是在解中。为了例如 2514 可以被 3 整除，因此 32514 或 35314 也可以被 3 整除。因此你可以减少搜索不能被 3 整除的数字。
对于不能被3整除的n位数字的列表（n>=3），可以通过删除至多 2 位数字来获得可被 3 整除的数字。这是因为求和将有余数 1 或 2。如果它是 1，在最坏的情况下你可以删除 2 位数字和余数 2。如果它是 2，在最坏的情况下你可以删除 2 位数字与1.

现在算法：

您有一个号码列表：

divisible = [i for i in numbers if i % 3 == 0]
candidate_list = [i for i in numbers if i % 3 != 0]

如果 candidate_list 的总和能被 3 整除，那么你就有答案了。如果没有，看余数：

remainder = sum(candidate_list) % 3

如果余数为1，我们将在候选列表中搜索1、4或7。如果是 2，则数字将是 2、5 和 8。如果我们找到一个数字，我们将从列表中删除它，其余数字的总和将被三整除。

if remainder!=0:
    for i in range(3):
        if (remainder + i*3) in candidate_list:
            candidate_list.remove(remainder + i*3)
            return candidate_list

这将从最小的数字开始搜索，并在找到数字时跳出循环。如果不是，我们将搜索两位数而不是 1 位。

counter = 0
for candidate in candidate_list:
    if candidate % 3 + remainder == 3:
        candidate_list.remove(candidate)
        counter += 1
        if counter > 1:
            return candidate_list

总的来说，你会得到这样的结果：

numbers = [3, 1, 4, 1, 5, 9, 0, 2, 4, 7, 9, 1, 3]
divisible = [i for i in numbers if i % 3 == 0]

def search(numbers):
    candidate_list = sorted([i for i in numbers if i % 3 != 0])
    remainder = sum(candidate_list) % 3
    if remainder!=0:
        for i in range(3):
            if (remainder + i*3) in candidate_list:
                candidate_list.remove(remainder + i*3)
                return candidate_list
        counter = 0
        for candidate in candidate_list:
            if candidate % 3 + remainder == 3:
                candidate_list.remove(candidate)
                counter += 1
                if counter > 1:
                    return candidate_list
    else:
        return candidate_list

candidate_list = search(numbers)
fin = int(''.join(map(str, sorted(divisible + candidate_list, reverse=True))))

寻找排列时减少运行时间

Reduce runtime when finding permutations

python

permutation