算法问题:找到最便宜的航班
最近，我在一家公司接受了面试(从M开始，以A结尾)，它问了我这个问题。我仍然在练习我的算法，所以我希望有人能帮助我理解如何解决这个问题，以及这些类型的问题。
问题：
您将得到两个数组。例如：
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循环。然而，我知道有一个更好的方法，但我不能把我的头围绕它。我相信我们想用目前为止的最小值来创建某种临时数组，或者类似的.
感谢您的阅读。
回答 2
Stack Overflow用户
发布于 2021-11-16 12:03:24
从返回价格数组R中创建一个单队列/堆栈，然后可以在O(n)中求解，其中n是D的长度。
R = [5, 12, 9, 10, 12] => [5, 9, 9, 10, 12]正如您在每一步都可以看到的那样，我们可以使用索引i及以上的最便宜的返程航班。
现在，迭代D的元素，并查看monoQ中的索引。由于monoQ的索引在R for i和更高版本中是最小的，所以现在您不能在这一点上做得更好了。
代码：
D = [10,7,15,12,4]
R = [5,12,9,10,12]
monoQ = [0]*len(R)
monoQ[-1] = R[-1]
for i in range(len(R)-2, -1, -1):
monoQ[i] = min(monoQ[i+1], R[i])
best = R[0]+D[0]
for i, el in enumerate(D):
best = min(best, D[i]+monoQ[i])
print(best)Stack Overflow用户
发布于 2021-11-16 12:22:43
我对@user1984 1984的解决方案非常满意。但如果你真的想给他们留下深刻印象
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使结果成为迄今所见的最小元素。由于您想要从这里到末尾的最小元素，您必须反转列表，积累，然后再反转它。
由于这是在一个讨论中提出的，其他答案之一，这可以重写为O(1)空间。
best = min(d + r for d, r in zip(reversed(D), accumulate(reversed(R), min)))这有点麻烦，我不会推荐它，除非您被特别要求一个O(1)空间解决方案。
不幸的是，您必须使用reverse(D)并从列表的末尾开始工作，而不是reverse(accumulate(...))，因为不能将reverse应用于积累。zip、reversed和accumulate都返回迭代器，而不是列表或元组。
https://stackoverflow.com/questions/69995292
复制相似问题
腾讯云开发者
