python - 算法题: Finding the cheapest flight

Question

最近去一家公司面试(M开头，A结尾)问了我这个问题。仍在练习我的算法，所以我希望有人能帮助我理解如何解决这个问题，以及这些类型的问题。

问题:

给你 2 个数组。例如:

D = [10,7,13,12,4]
R = [5,12,7,10,12]

D 表示从城市 A 到城市 B 的航类出发价格。 R 表示从城市 B 到城市 A 的航类的返程价格。找出城市 A 和城市 B 之间往返航类的最低费用。例如，示例中的最小值是 D[1] + R[2]。

(只能乘坐与出发航类相同或更高指数的返程航类)

棘手的部分是，显然，您必须在返回之前离开。

朴素的方法只是结合了所有可能性的双重 for 循环。但是，我知道有更好的方法，但我无法理解它。我相信我们想要创建某种具有最小值的临时数组或类似的东西...

感谢阅读。

Answer 1

我对@user1984 的解决方案非常满意。但如果你真的想打动他们:

from itertools import accumulate

monoQ = list(accumulate(reversed(R), min))
monoQ.reverse()

best = min(d + r for d, r in zip(D, monoQ))

大多数人都熟悉 list(accumulate((1, 2, 3, 4 5), operator.add)) 返回 (1, 3, 6, 10, 15 )，但使用 min 可使结果成为迄今为止看到的最小元素。既然要从这里到最后的最小元素，就得把list倒过来，累加起来，然后再倒过来。

---

由于这是在讨论其他答案之一时出现的，因此可以将其重写为 O(1) 空间。

best = min(d + r for d, r in zip(reversed(D), accumulate(reversed(R), min)))

这有点 hacky，除非您特别要求 O(1) 空间解决方案，否则我不会推荐它。

不幸的是，你必须使用 reverse(D) 并从列表的末尾开始工作，而不是 reverse(accumulate(...)) 因为你不能将 reverse 应用于累加。 zip、reversed 和 accumulate 都返回迭代器而不是列表或元组。