hello 大家好!今天開寫一個新章節,每一天一道算法題。讓我們一起來學習算法思維吧!
function canCompleteCircuit(gas, cost) {// 加油站的總數const n = gas.length;// 記錄總剩余油量,若總剩余油量小于 0,說明無法繞環路行駛一周let totalSurplus = 0;// 記錄當前從起始點出發累計的剩余油量let currentSurplus = 0;// 記錄可能的起始加油站編號,初始設為 0let start = 0;// 遍歷每一個加油站for (let i = 0; i < n; i++) {// 計算從當前加油站出發到下一個加油站的剩余油量const surplus = gas[i] - cost[i];// 累加每一個加油站的剩余油量到總剩余油量中totalSurplus += surplus;// 累加從當前起始點出發到當前加油站的剩余油量currentSurplus += surplus;// 如果當前從起始點出發累計的剩余油量小于 0,說明從當前 start 出發無法繼續行駛if (currentSurplus < 0) {// 則更新起始點為下一個加油站start = i + 1;// 并將當前累計的剩余油量重置為 0,準備從新的起始點開始計算currentSurplus = 0;}}// 如果總剩余油量小于 0,說明整體的汽油量不足以支持繞環路行駛一周if (totalSurplus < 0) {return -1;}// 否則,返回記錄的起始加油站編號return start;
}// 示例測試
const gas = [1, 2, 3, 4, 5];
const cost = [3, 4, 5, 1, 2];
console.log(canCompleteCircuit(gas, cost));
代碼思路解釋
初始化部分:
n:獲取加油站的總數,用于后續的循環遍歷。
totalSurplus:用來統計所有加油站的汽油量減去行駛消耗后的總剩余油量。如果這個值小于 0,說明無論從哪個加油站出發,都無法繞環路行駛一周。
currentSurplus:記錄從當前假設的起始加油站出發,到當前遍歷到的加油站時累計的剩余油量。
start:表示可能的起始加油站編號,初始從 0 號加油站開始嘗試。
遍歷加油站:
在循環中,對于每一個加油站,計算從該加油站出發到下一個加油站的剩余油量 surplus,即 gas[i] - cost[i]。
將這個剩余油量累加到 totalSurplus 中,以統計總的剩余油量情況。
同時也將其累加到 currentSurplus 中,以跟蹤從當前假設的起始點出發的剩余油量變化。
若 currentSurplus 小于 0,意味著從當前假設的 start 出發無法到達下一個加油站,所以更新 start 為下一個加油站的編號 i + 1,并將 currentSurplus 重置為 0,重新開始從新的起始點計算剩余油量。
結果判斷:
循環結束后,檢查 totalSurplus 的值。如果它小于 0,說明整體汽油量不夠繞環路行駛,返回 -1。
若 totalSurplus 大于等于 0,說明存在一個起始點可以繞環路行駛一周,返回記錄的 start 編號。