天天看点

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;      
    }
}