时间戳

首页 > 解决方案 > 重复序列（优化）

python-3.x - 重复序列（优化）

问题描述

我尝试解决这个问题：initial list = [0, 1, 2, 2] 你得到这个数字序列 [0, 1, 2, 2] 并且你需要每次添加下一个自然数（所以 3, 4 , 5, etc.) n 次，其中 n 是其索引的元素。例如，下一个要添加的数字是 3，而 list[3] 是 2，因此您追加 [3] 2 次。新列表将是：[0, 1, 2, 2, 3, 3]。那么 4 的索引是 3，所以你要追加 4 3 次。该列表将是 [0, 1, 2, 2, 3, 3, 4, 4, 4] 等等。([0, 1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10])

为了解决这个问题，我尝试了各种方法。我使用了递归，但在这种情况下，递归方法非常慢。我也尝试了来自 OEIS (A055086) => a(n) = ceiling(2*sqrt(n+1)) - 2 的数学公式。这个公式的问题是在 2 ** 20 之后它太不精确了。

所以，我的下一个想法是使用记忆：

lst = [0, 1, 2, 2]
from itertools import repeat
def find(n):
    global lst
    print(lst[-1], n, flush = True)
    if len(lst) > n:
        return lst[n]
    for number in range(lst[-1]+1, n+1):
        lst += list(repeat(number, lst[number]))
        if len(lst) > n:
            return lst[n]

现在，这种方法一直有效到 2 ** 37，但在此之后只是超时。我尝试实现我的算法的网站是（https://www.codewars.com/kata/5f134651bc9687000f8022c4/train/python）。我不寻求解决方案，而是寻求有关如何优化我的代码的任何提示。我搜索了一些类似的问题，发现在这种情况下，我可以使用列表的总和，但对我来说不是很清楚，但这对我有什么帮助。

欢迎任何帮助！

标签： python-3.xlistoptimization

解决方案

您可以像这样迭代地回答它：

def find(n):
    lst = [0,1,2,2]
    if n < 4:
        return lst[n]
    to_add = 3
    while n >= len(lst):
        for i in range(lst[to_add]):
            lst.append(to_add)
        to_add += 1
    return lst[n]

您可以通过在循环的早期中断for并单独跟踪列表长度来优化大 n，而不是调用len

推荐阅读