LeerCode:(Python)(Array) Gas Station

題目連結: https://leetcode.com/problems/gas-station/description/?envType=study-plan-v2&envId=top-interview-150

題意說明:

• 給定兩個 Array，代表每個位置的加油站油量，以及到達下一個地點的油耗
• 找出要從哪一個位置開始旅行才能走一圈回到原點
• 只會有唯一一個解答

初始想法

逐一把每個點當作起始點，重新拼裝 Array -> 感覺就會很慢

起始點的油量，至少要比起始點到下一點的油耗多，否則根本無法移動

偷看了別人的解答

實作程式碼一

# 解題邏輯: 分離兩個計算
# 1. 尋找起始點
# 2. 確認是否有解答

# 建立三個變數
# 起始位置，由零開始的累積油量，由起始點開始的累積油量
start_position = 0
Cumulated_Gas_From_Zero_Position = 0
Cumulated_Gas_From_Start = 0

# 解題邏輯，假設第一個位置就是正確起始位置，如果後續有足夠證據就推翻
# 將正確起始位置持續往後移動，直到找到
# 如果後續一直沒有找到可以推翻正確起始位置的情況，那最後一個暫定的起始位置就是解答

# 持續累加由零開始的累積油量，最後用來判斷是否有解
# 如果現在的位置，獲取的汽油 + 起始點至今累積的汽油，比消耗的油多，這樣根本到不了下個點
# 換句話說，目前的起始點就不是正確的起始點
for i in range(len(gas)):
    Cumulated_Gas_From_Zero_Position = Cumulated_Gas_From_Zero_Position + gas[i] - cost[i]
    if (gas[i]+Cumulated_Gas_From_Start) < cost[i]:
        start_position = i + 1
        Cumulated_Gas_From_Start = 0
    else:
        Cumulated_Gas_From_Start = Cumulated_Gas_From_Start + gas[i] - cost[i]

# 如果累積的油量小於0，那就根本無解，回傳 -1
# 否則回傳正確的起始位置
if Cumulated_Gas_From_Zero_Position < 0:
    return -1
else:
    return start_position

能正確解題但表現普通

後續來一一反思

反思一

不需要逐步加總油量和油耗，可以直接 Sum起來

可以一次算完就不要一步一步來，可以判斷出無解就不要浪費時間運算

if sum(gas) - sum(cost) <0:
    return -1

start_position = 0
Cumulated_Gas_From_Start = 0

for i in range(len(gas)):
    if (gas[i]+Cumulated_Gas_From_Start) < cost[i]:
        start_position = i + 1
        Cumulated_Gas_From_Start = 0
    else:
        Cumulated_Gas_From_Start = Cumulated_Gas_From_Start + gas[i] - cost[i]

return start_position

再進一步拿掉多餘計算

# 不要用 a - b <0，直接用 a < b
if sum(gas) < sum(cost):
    return -1

start_position = 0
Cumulated_Gas_From_Start = 0

for i in range(len(gas)):
    if (gas[i]+Cumulated_Gas_From_Start) < cost[i]:
        start_position = i + 1
        Cumulated_Gas_From_Start = 0
    else:
        Cumulated_Gas_From_Start = Cumulated_Gas_From_Start + gas[i] - cost[i]

return start_position

反思二

看到 Memory贏過這麼多人，打算多花費一些空間來換運算時間

發現有兩行 Code重複計算: 累積剩下的油 + 加油站的油 - 油耗，將這段拉出來成為變數

if sum(gas) < sum(cost):
    return -1

start_position = 0
Cumulated_Gas_From_Start = 0
current_status = 0

for i in range(len(gas)):
    current_status = Cumulated_Gas_From_Start + gas[i] - cost[i]
    if current_status <0:
        start_position = i + 1
        Cumulated_Gas_From_Start = 0
    else:
        Cumulated_Gas_From_Start = current_status

return start_position