算法问题：查找最便宜的航班

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

会使结果成为迄今为止看到的最小元素。 由于您想要从这里到末尾的最小元素，因此您必须反转列表，累加，然后再次反转。

---

由于这是在其他答案之一的讨论中出现的，因此可以将其重写为 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

都返回迭代器而不是列表或元组。

Answer 2

从返回价格数组

R

中创建一个单声道队列/堆栈，然后您可以在

O(n)

中解决它，其中

n

是

D

的长度。

R = [5, 12, 9, 10, 12] => [5, 9, 9, 10, 12]

正如您在每一步中看到的那样，我们可以获得索引

i

及以上的最便宜的返程航班。

现在，迭代 D 的元素并查看

monoQ

中的索引。由于

monoQ

处的索引是

R

及以上的

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)

Answer 3

O(n) 运行时间，O(1) javascript 空间解决方案：

var getCheapestFlights = function(D, R) {
    let minResult = Number.MAX_VALUE

    let minReturn = Number.MAX_VALUE
    for (let i= D.length-1; i>=0; i--) {
        minReturn = Math.min(R[i], minReturn)
        minResult = Math.min(D[i]+minReturn, minResult)
    }

    return minResult    
}