国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Gas Station 加油站

lovXin / 2461人閱讀

摘要：這樣我們開始遍歷數組，如果是負數，說明開出該加油站后無法到達下一個加油站，這樣旅程的起點更新為下一個加油站。

Gas Station 
There are N gas stations along a circular route, where the amount of gas at station i is gas[i].


You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.


Return the starting gas station"s index if you can travel around the circuit once, otherwise return -1.
貪心法 復雜度

時間 O(N) 空間 O(K)

思路

我們把將gas中每個值都減去cost中對應的值，這樣gas就成為了開出該加油站到下一個加油站時，該加油站加的油用剩到多少。這樣我們用一個tank變量記錄汽車每開到一個加油站后油箱里累計剩下多少油，每到一個加油站就更新。這樣我們開始遍歷gas數組，如果tank是負數，說明開出該加油站后無法到達下一個加油站，這樣旅程的起點更新為下一個加油站。因為旅程是環狀的我們遍歷的加油站數組應為2*gas.length-1，這樣能保證我們以最后一個加油站為起點時也能繼續驗證。

代碼 
public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        // gas減去cost，得到凈油值
        for(int i = 0; i < cost.length; i++){
            gas[i] -= cost[i];
        }
        int tank = 0, res = -1;
        for(int i = 0; i < gas.length * 2 - 1; i++){
            int idx = i % gas.length;
            // 更新油箱
            tank += gas[idx];
            // 如果油箱為負，說明走不到下一個加油站
            if(tank < 0){
                res = idx + 1;
                tank = 0;
            }
        }
        // 如果起點在最后一個加油站之后，說明無解
        return res >= gas.length ? -1 : res;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64649.html

相關文章

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<