最近去一家公司面试(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 循环。但是,我知道有更好的方法,但我无法理解它。我相信我们想要创建某种具有最小值的临时数组或类似的东西...
感谢阅读。
最佳答案
我对@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
都返回迭代器而不是列表或元组。
https://stackoverflow.com/questions/69995292/