时间戳

首页 > 解决方案 > 最长公共子序列，python，贪心

python - 最长公共子序列，python，贪心

问题描述

我已经提交了两个序列的 LCS 问题的代码草案。我在尝试贪心时犯了严重错误，现在我已经实现了我相信一个稳定的贪心算法来解决这个问题。虽然我有两个问题，在线课程的这一部分，当我提交它时，它说序列 [1,2,3] 和 [3,2,1] 正确的输出是 1，我相信为什么？所以，我去了正确的版本并进行了测试，它工作正常，即输出为 0，并针对正确的版本测试了许多好的测试用例，它工作正常。现在，我有三个问题：为什么 [1,2,3] 和 [3,2,1] 应该输出 1 而不是 0？如果我的代码无效，请帮助我处理一些使其无效的测试用例？谢谢！我的代码：

def lcs2(a, b):
    lst, tag= [], False
    if len(set(a).intersection(set(b))) != 0: tag = True 
    if len(a) <= len(b): x = a; y = b    
    else: x = b; y = a
    for i in y:
        if i in x:
            lst.append(x.index(i))
            x[x.index(i)] = None
        else:
            y[i] = None
    cnt = 0
    for i in range(1 ,len(lst)):
        if lst[i] > lst[i-1]: cnt += 1
    if cnt == 0 and not tag: return 0
    return cnt + 1

现在，我把这个放在这里，一些提议似乎实现了一个很好的：Python: Length of most common subsequence of lists

但是在测试它时a = [-1, 1, -1, -1, 4] b = [0, -1, 0, 4, 4]对我来说只是失败了，这给出了正确的答案 2 而不是 1。

标签： pythonalgorithm

解决方案

lcs2([1, 2, 3], [3, 2, 1])正确返回1, 因为[1],[2]和[3]都是在两次运行中都存在的长度为 1 的序列的示例。

你的算法有一些问题，似乎遗漏了一些情况。一方面，它只查找 in 的某个元素的第一次出现y，x但它不会回溯以查找更长的序列。

此外，不清楚为什么您使用tag它的唯一功能似乎是检测两组的交集是否为空（在这种情况下，结果只是 0，算法应该找到 1 或以上的运行）。

一些不适用于您的算法的运行示例：（print(lcs2([1, 2, 3], [1, 3, 2, 3]))答案是 2，但应该是 3） - 这是因为缺少回溯；print(lcs2([], [1]))这会因 IndexError 而失败，因为您尝试使用 访问空列表的元素y[i] = None。

我不会提供一个可行的实现，因为https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Code_for_the_dynamic_programming_solution有很好的解决方案，不需要在这里复制。

通常，不要试图通过考虑随机示例来尝试破坏它来证明您的代码，而是尝试考虑具有所有类型变化的示例集合并针对该集合进行测试。此外，请尝试完全了解您自己的算法，以便您可以找出缺陷并可能对其进行优化。

推荐阅读