成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[Leetcode] Gas Station 加油站

lovXin / 2518人閱讀

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

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.
貪心法 復(fù)雜度

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

思路

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

代碼 
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];
            // 如果油箱為負(fù)，說明走不到下一個加油站
            if(tank < 0){
                res = idx + 1;
                tank = 0;
            }
        }
        // 如果起點在最后一個加油站之后，說明無解
        return res >= gas.length ? -1 : res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/64649.html

相關(guān)文章

  • [LintCode/LeetCode] Gas Station

    摘要：看到這個題目，怎樣可以不把它當(dāng)成一個環(huán)路來分析，以及減少多余的空間呢例如，我們引入單次剩余油量，剩余油量和，總剩余油量和，以及可行起點四個參數(shù)。大體上說，只要，一定有解。所以跳過這個耗油量很大的油站，然后將下一個油站作為起點繼續(xù)判斷即可。 Problem There are N gas stations along a circular route, where the amount ...

    hedge_hog 評論0 收藏0

  • ＜LeetCode天梯＞Day028 回文鏈表（雙指針+遞歸+棧+數(shù)組） | 初級算法 | Pyth

    摘要：先實現(xiàn)棧操作遍歷鏈表，把每個節(jié)點都進中然后再遍歷鏈表，同時節(jié)點依次出棧，二者進行比較。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個人主頁：應(yīng)無...

    miguel.jiang 評論0 收藏0

  • ＜LeetCode天梯＞Day026 反轉(zhuǎn)鏈表（遞歸法+（迭代法）雙鏈表法） | 初級算法 | Py

    摘要：關(guān)于遞歸這里提一兩點遞歸基本有這幾步遞歸的模板，終止條件，遞歸調(diào)用，邏輯處理。 ?作者簡介：大家好，我是車神哥，府學(xué)路18號的車神? ?個人主頁：應(yīng)無所住而生...

    imingyu 評論0 收藏0

  • ＜LeetCode天梯＞Day031 驗證二叉搜索樹（遞歸+中序遍歷） | 初級算法 | Pytho

    摘要：有效二叉搜索樹定義如下節(jié)點的左子樹只包含小于當(dāng)前節(jié)點的數(shù)。所有左子樹和右子樹自身必須也是二叉搜索樹。而我們二叉搜索樹保證了左子樹的節(jié)點的值均小于根節(jié)點的值，根節(jié)點的值均小于右子樹的值，因此中序遍歷以后得到的序列一定是升序序列。 ...

    Genng 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<