資料結構
網路
關係資料庫管理系統(RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python程式：查詢可作為起點進行旅行的城市數量
假設有n個城市，編號從0到n-1，並且有n條單向道路。我們可以從城市i前往城市(i + 1) % n [0到1到2到……到N-1到0]。我們有一輛車，油箱容量為cap單位。在城市i開始時，我們可以使用fuel[i]單位的燃油，並且從城市i到(i + 1) % n需要消耗cost[i]單位的燃油。我們必須找到有多少個城市可以作為出發點，以便我們可以環遊所有城市並返回到起點？
因此，如果輸入類似於cap = 3 fuel = [3,1,2] costs = [2,2,2]，則輸出為2，因為有兩個可能的解決方案。
我們可以從城市0出發，加滿3單位燃油，然後消耗2單位燃油前往城市1。油箱剩餘1單位。在城市1加油1單位後，汽車有2單位燃油，我們可以消耗2單位燃油前往城市2。現在油箱為空。在城市2加油2單位燃油後，我們可以消耗2單位燃油返回城市0。
我們可以從城市2出發，加滿2單位燃油，然後前往城市0。然後在城市0加油3單位燃油後，前往城市1，剩餘1單位燃油。然後在城市1加油1單位燃油，現在有2單位燃油，可以前往城市2。
但是，我們不能從城市1出發，因為只有1單位燃油，而前往城市2需要2單位燃油。
為了解決這個問題，我們將遵循以下步驟：
- n := fuel陣列的長度
- req := 一個大小為n的陣列，並用0填充
- 對於k從0到1，執行以下操作：
- 對於i從n-1到0遞減，執行以下操作：
- nexti := (i + 1) mod n
- req[i] := 0和req[nexti] + costs[i] - fuel[i]中的最大值
- 如果(req[i] + fuel[i] 和 cap中的最小值) - costs[i] < req[nexti]，則：
- 返回0
- 對於i從n-1到0遞減，執行以下操作：
- 返回r中0的數量
示例
讓我們來看下面的實現以更好地理解：
def solve(cap, fuel, costs):
n = len(fuel)
req = [0] * n
for k in range(2):
for i in range(n-1, -1, -1):
nexti = (i + 1) % n
req[i] = max(0, req[nexti] + costs[i] - fuel[i])
if min(req[i] + fuel[i], cap) - costs[i] < req[nexti]:
return 0
return sum(1 for r in req if r == 0)
cap = 3
fuel = [3,1,2]
costs = [2,2,2]
print(solve(cap, fuel, costs))輸入
3, [3,1,2], [2,2,2]
輸出
2
更新於：2021年10月23日
425 次瀏覽
廣告