2 个列表的最大路径总和

Question

我的问题是关于Codewars 上的这个型。该函数采用两个具有不同元素的排序列表作为参数。这些列表可能有也可能没有共同的项目。任务是找到最大路径和。在查找总和时，如果有任何常见项目，您可以选择更改到其他列表的路径。

给出的例子是这样的：

list1 = [0, 2, 3, 7, 10, 12]
list2 = [1, 5, 7, 8]
0->2->3->7->10->12 => 34
0->2->3->7->8      => 20
1->5->7->8         => 21
1->5->7->10->12    => 35 (maximum path)

我解决了 kata，但我的代码不符合性能标准，因此执行超时。我能为它做些什么呢？

这是我的解决方案：

def max_sum_path(l1:list, l2:list):
    common_items = list(set(l1).intersection(l2))
    if not common_items:
        return max(sum(l1), sum(l2))
    common_items.sort()
    s = 0
    new_start1 = 0
    new_start2 = 0
    s1 = 0
    s2 = 0
    for item in common_items:
        s1 = sum(itertools.islice(l1, new_start1, l1.index(item)))
        s2 = sum(itertools.islice(l2, new_start2, l2.index(item)))
        new_start1 = l1.index(item)
        new_start2 = l2.index(item)
        s += max(s1, s2)
    s1 = sum(itertools.islice(l1, new_start1, len(l1)))
    s2 = sum(itertools.islice(l2, new_start2, len(l2)))
    s += max(s1, s2)
    return s

Answer 1

你的算法实际上很快，只是你的实现很慢。

\n

总共需要 O(n\xc2\xb2) 时间的两件事：

\n

\n
• l1.index(item)始终从列表的开头进行搜索。应该l1.index(item, new_start1)。
\n
• itertools.islice(l1, new_start1, ...)为第一个元素创建一个迭代器l1并对其进行迭代，然后再到达所需的元素。所以只需使用普通的列表切片即可。new_start1
\n

\n

那么排序的时间复杂度为 O(n log n)，其他所有事情的时间复杂度为 O(n)。并且排序的 O(n log n) 很快，对于任何允许的输入甚至更大的输入，可能很容易比 O(n) 部分花费更少的时间。

\n

这是重写的版本，大约 6 秒后就被接受了，就像其他答案中的解决方案一样。

\n

def max_sum_path(l1:list, l2:list):\n    common_items = list(set(l1).intersection(l2))\n    if not common_items:\n        return max(sum(l1), sum(l2))\n    common_items.sort()\n    s = 0\n    new_start1 = 0\n    new_start2 = 0\n    s1 = 0\n    s2 = 0\n    for item in common_items:\n        next_start1 = l1.index(item, new_start1)  # changed\n        next_start2 = l2.index(item, new_start2)  # changed\n        s1 = sum(l1[new_start1 : next_start1])    # changed\n        s2 = sum(l2[new_start2 : next_start2])    # changed\n        new_start1 = next_start1                  # changed\n        new_start2 = next_start2                  # changed\n        s += max(s1, s2)\n    s1 = sum(l1[new_start1:])                     # changed\n    s2 = sum(l2[new_start2:])                     # changed\n    s += max(s1, s2)\n    return s\n

\n

或者您可以使用迭代器而不是索引。这是您为此重写的解决方案，也在大约 6 秒内被接受：

\n

def max_sum_path(l1:list, l2:list):\n    common_items = sorted(set(l1) & set(l2))\n    s = 0\n    it1 = iter(l1)\n    it2 = iter(l2)\n    for item in common_items:\n        s1 = sum(iter(it1.__next__, item))\n        s2 = sum(iter(it2.__next__, item))\n        s += max(s1, s2) + item\n    s1 = sum(it1)\n    s2 = sum(it2)\n    s += max(s1, s2)\n    return s\n

\n

我会将最后四行合并为一行，就像你一样，这样更容易比较。

\n