python - 最长递增子序列，算法工作错误，不知道为什么

Question

我实现了最长递增子序列 (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 系列的向量语言完全不同......

我为此纠结了很长时间。给会发现问题的人喝一大杯啤酒:(

Answer 1

当你声明 L[i] = L[j] 你不复制列表的内容时，你只需复制一个引用:从现在开始 L[i] 和 L[j] 指向同一个列表，通过 L[i] 所做的更改将在您获得 L 时反射(reflect)出来[j].

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

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] = list(L[j])
        L[i].append(D[i])
    print(L)

Now hoever your algorithm does not work anymore (it was not working in the first place nevertheless). When running your (fixed) code, you get:

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

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

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]]

Note: based on your comment you use python-2.7, from python-3.x there is a method called .copy() on lists that you can call.