我最近在一家公司（以 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 回圈。但是，我知道有更好的方法，但我無法理解它。我相信我們想要創建某種臨時陣列，到目前為止最小或類似的......
謝謝閱讀。
uj5u.com熱心網友回復：
我對@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))which returns (1, 3, 6, 10, 15)，但 usingmin使結果成為迄今為止看到的最小元素。既然你想要從這里到最后的最小元素，你必須將串列反向，累加，然后再次反向。
由于這是在其他答案之一的討論中提出的，因此可以將其重寫為 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所有回傳迭代器而不是串列或元組。
uj5u.com熱心網友回復：
創建一個單色佇列/堆疊中的回傳陣列的價格出來R，那么您可以在解決這O(n)其中n的長度D。
R = [5, 12, 9, 10, 12] => [5, 9, 9, 10, 12]
正如您在每個步驟中所看到的，我們都可以訪問 indexi及以上可能的最便宜的返程航班。
現在，迭代 D 的元素并查看 中的索引monoQ。由于該索引 atmonoQ是Rfori和 above 中可能的最小索引，因此您現在無法做得更好。
在代碼中：
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)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359111.html
下一篇：移零邏輯分解Javascript