天天看點

leetcode 134.加油站原題如下:方法一

原題如下:

leetcode 134.加油站原題如下:方法一

方法一

從第一個加油站開始,視為開始的時候郵箱裡沒有油,每到一個加油站,都要計算在這個加油站得到的油以及減去到下一個加油站需要的油量,凡是遇到油量小于0了,那麼就以下一個加油站作為起始點,進行下一輪判斷。遇到可以堅持越站一圈的時候,傳回這一輪的其實加油站的坐标。

本方法的java代碼示例:

/*
 *作者@v7fgg
 *執行用時 :184 ms, 在所有 Java 送出中擊敗了10.94%的使用者
 *記憶體消耗 :39.9 MB, 在所有 Java 送出中擊敗了5.88%的使用者
 *2020年6月2日 15:46
 */
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int l=gas.length;
        for(int i=0;i<l;i++){
            int j=i;//i用來表示起始坐标不宜變化,是以為了表示走一圈過程中的坐标變化,多賦一個值
            int caozuo=0;
            int money=0;
            while(caozuo<l){
                money+=gas[j]-cost[j];//走一站後的汽油餘量
                caozuo++;//用于記錄操作的次數
                j=(j+1)%l;//每走一個加油站,坐标加1,到最後一個加油站傳回到第一個            
                if(money<0){break;}                
                if(caozuo==l){return i;}//操作數可以堅持到l說明一圈跑下來沒問題
            }
        }return -1;      
    }
}