3

我实现了最长递增子序列（LIS）算法，我认为它会起作用，但结果完全是一团糟。

def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))]
    L[0].append(D[0])
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = L[j]
        L[i].append(D[i])
    print L

返回结果：

[[3], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [2, 6, 4, 5], [1]]

它应该是什么：

[[3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

正如我在调试器中看到的那样：

L[i] = L[j]

不仅L[i]获得新值，而且列表中的其他main (L)列表也...

我不知道如何避免它。看起来 Python 中的列表与 C 系列的向量语言完全不同......

我和这个斗争了很长时间。巨大的啤酒给那些会发现问题的人:(

4

2 回答 2

5

当您声明L[i] = L[j] 您不复制列表的内容时，您只需复制一个引用：从现在开始L[i]并L[j]指向同一个列表，并且所做的更改L[i]将在您获得时反映出来L[j]。

一个简单的解决方法就是复制列表：

定义利斯（）：
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))]
    L[0].append(D[0])
    对于我在范围内（len（D））：
        对于范围内的 j (0,i)：
            如果 D[i] > D[j]：
                L[i] =列表（ L[j] ）
        L[i].append(D[i])
    打印(L)

现在，无论您的算法不再起作用（尽管如此，它一开始就不起作用）。运行您的（固定）代码时，您会得到：

>>> lis()
[[3, 3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

在第3一个列表中出现两次，您可以通过删除循环.append之前的来解决这个问题。for所以最终版本是：

def lis():
    #D = map(int, raw_input().split())
    D = [3, 2, 6, 4, 5, 1]
    L = [[] for i in range(len(D))] #removed the next line
    for i in range(len(D)):
        for j in range(0,i):
            if D[i] > D[j]:
                L[i] = list(L[j])
        L[i].append(D[i])
    print(L)

产生：

>>> lis()
[[3], [2], [2, 6], [2, 4], [2, 4, 5], [1]]

注意：根据您的评论，您使用，从开始，您可以调用一个.copy()在列表上调用的方法。

于 2017-01-18T12:43:08.710 回答
0

重要的提示

上面的解决方案是正确的，但如果你尝试一下，在某些情况下结果可能是错误的。例如 - 数字的最长递增子序列：

5 1 4 2 3 1 2 9 1

是

1 2 3 9

但是这个解决方案不会出现在算法返回的L列表中。将有：

1 2 9

需要 L 列表中的最大元素。然后可以附加 D 中的另一个元素，所以我们必须再添加一个条件，这里你可以找到正确的代码：

def lis():
#D = map(int, raw_input().split())
D = [5, 1, 4, 2, 3, 1, 2, 9, 1]
L = [[] for i in range(len(D))]
for i in range(len(D)):
    for j in range(0,i):
        if D[i] > D[j] and len(L[i]) < len(L[j])+1: #added condition
            L[i] = list(L[j])
    L[i].append(D[i])
print(L)

>>lis()
[[5], [1], [1, 4], [1, 2], [1, 2, 3], [1], [1, 2], [1, 2, 3, 9], [1]]
于 2017-01-18T14:32:20.450 回答