134. 加油站

貪心思想： 因為本題用到了貪心算法所以先來了解一下「貪心算法」的問題需要滿足的條件：

• 最優(yōu)子結(jié)構(gòu)：規(guī)模較大的問題的解由規(guī)模較小的子問題的解組成，規(guī)模較大的問題的解只由其中一個規(guī)模較小的子問題的解決定；
• 無后效性：后面階段的求解不會修改前面階段已經(jīng)計算好的結(jié)果；
• 貪心選擇性質(zhì)：從局部最優(yōu)解可以得到全局最優(yōu)解。

綜上可得：貪心算法就是做出當前狀態(tài)下的最優(yōu)選擇認為就可以解決問題。

在本題中，要找到一個位置能夠繞行一周回來。

“假設從x加油站出發(fā)經(jīng)過z加油站最遠能到達y加油站，那么從z加油站直接出發(fā)，不可能到達y下一個加油站。因為從x出發(fā)到z加油站時肯定 有存儲的油 或者 到z的時候油已經(jīng)沒了，加上z加油站能夠加上的油，這都到不了y的下一站。而直接從z出發(fā)剛開始是沒有存儲的油的，所以更不可能到達y的下一站?！?mark hidden color="red">文章來源：http://www.zghlxwxcb.cn/news/detail-663531.html

也就是說，我們首先檢查第 0 個加油站，并試圖判斷能否環(huán)繞一周；如果不能，就從第一個無法到達的加油站開始繼續(xù)檢查。文章來源地址http://www.zghlxwxcb.cn/news/detail-663531.html

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int length = gas.length;
        int index = 0;
        // 這里不用for循環(huán)是因為，我們會使用跳過一些下標。所以，使用while是最好的
        // 從頭到尾遍歷每個加油站，并且檢查以該加油站為起點，能否行駛一周
        while (index < length) {
            // 當前index加油站的總汽油
            int sumOfGas = 0;
            // 當前index加油站的總花費汽油
            int sumOfCost = 0;
            // 當前index加油站最遠能夠走的最遠步數(shù)
            int count = 0;
            // 判斷從當前index下標出發(fā)能否環(huán)形一周
            while (count < length) {
                // 當前index加油站組成環(huán)形加油站
                // 環(huán)形加油站下標
                int currentIndex = (index + count) % length;
                sumOfCost += cost[currentIndex];
                sumOfGas += gas[currentIndex];
                // 如果這個環(huán)形下標站點發(fā)現(xiàn)油不夠了
                if (sumOfCost > sumOfGas) {
                	// 當前index加油站組成環(huán)形加油站肯定是不滿足題意的，跳出循環(huán)
                    break;
                }
                // 最遠的步數(shù)+1
                count++;
            }
            // 當前index能夠環(huán)形一周
            if (count == length) {
                // 返回
                return index;
            } else {
                // 就從無法到達的加油站開始繼續(xù)檢查。
                index = index + count + 1;
            }
        }
        // 所有加油站作為起點都不滿足
        return -1;
    }
}

到了這里，關于【LeetCode】134. 加油站 - 貪心算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！