Re: [閒聊] 每日LeetCode已回收
※ 引述《fxfxxxfxx (愛麗絲)》之銘言：
: 134. Gas Station
給予兩個陣列，陣列gas[i]表示第i個位置的油量，陣列cost[i]表示前往i+1位置所需
的油量，若我們可以從某一個位置i走訪所有的加油站返回i的值，若無法走訪則返回-1。
（題目保證如果可以走完全程則必定只會有一個解）
Example：
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 +
4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to
station 3.
Therefore, return 3 as the starting index.
思路：
1.如果一個車要從某個起點開始走完全程，他必須滿足：總油量 >= 總成本。
2.所以我們只需要把所有油量和成本相加判斷他是否大於等於0即可知道是否可以走完。
3.至於要如何知道要從哪一點開始走呢？
如果從當前點開始走走到某一個點導致 油量 < 下個點的成本時，代表從我們一開始
的點開始走的話必定走不到這個點，所以我們把起點改為當前點的下一個點：
---
if (curSum < 0) {
index = (i + 1) % gas.length ;
curSum = 0;
}
---
如果這個點的成本還是負的那就表示起點是下一個點，不斷移動 index 直到成本為正數
的點。
4.若不存在合法起點：因為totalSum小於0 所以返回 -1。
若存在合法起點：合法起點就是最後 index 停留的位置。
Java Code：
-------------------------------
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int curSum = 0;
int totalSum = 0;
int index = 0;
for (int i = 0; i < gas.length; i++) {
curSum += gas[i] - cost[i];
totalSum += gas[i] - cost[i];
if (curSum < 0) {
index = (i + 1) % gas.length ;
curSum = 0;
}
}
return totalSum < 0 ? -1 : index;
}
}
-------------------------------
--
https://i.imgur.com/CBMFmWk.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1673076464.A.90D.html
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 184 之 719 篇)：