一 前言

    昨天開(kāi)始了算法系列的第一篇，是有關(guān)樹(shù)的一個(gè)問(wèn)題，今天給大家繼續(xù)帶來(lái)有關(guān)貪心策略的一個(gè)問(wèn)題~現(xiàn)在就開(kāi)始吧~

二 題目

There are N gas stations along a circular route, where the amount of gas at station i isgas[i].
You have a car with an unlimited gas tank and it costscost[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.
Note:
The solution is guaranteed to be unique.

題目的大致意思就是：有一個(gè)由N個(gè)加油站組成的環(huán)形路徑，第i個(gè)加油站儲(chǔ)存了gas[i]這么多的汽油，你最開(kāi)始有一個(gè)沒(méi)有汽油的坦克，你從第i個(gè)加油站走到它的下一個(gè)i+1個(gè)加油站消耗汽油cost[i]這么多，問(wèn)你是否可以找到一個(gè)站，從該站出發(fā)可以繞著該路徑兜風(fēng)一圈，有的話返回該站的標(biāo)號(hào)，沒(méi)有的話返回-1。

三 思路分析及代碼

我們假設(shè)坦克從N-1這站出發(fā)（也就是0后面那個(gè)，因?yàn)樗麄兪莻€(gè)環(huán)形所以首尾相接），末尾位置我們?cè)O(shè)為0，也就是start = N-1，end = 0，從start開(kāi)始往end的方向走，這個(gè)時(shí)候我們?cè)O(shè)置一個(gè)變量sum用來(lái)記錄坦克油箱中還剩多少油。那么開(kāi)始時(shí)sum = gas[i] - cost[i]，接下來(lái)是關(guān)鍵，如果現(xiàn)在這個(gè)sum大于0證明坦克現(xiàn)在還有油，就可以嘗試向下一站走，也就是end++。如果sum小于0證明坦克從start開(kāi)往他的下一站（針對(duì)當(dāng)前狀態(tài)就是從N-1開(kāi)到0）沒(méi)有足夠的油了，那么就嘗試把start往前一站挪，也就是變?yōu)閺腘-2開(kāi)始嘗試。不斷進(jìn)行這樣的操作，知道start <= end證明真?zhèn)€過(guò)程結(jié)束了，這時(shí)如果sum >= 0證明可以支撐坦克走完一圈，返回對(duì)應(yīng)的start位置就是結(jié)果。如果sum < 0證明坦克無(wú)法走完一圈，返回-1。分析完畢，我們上代碼：

public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int start = lens-1, end = 0;
        int sum = gas[start] - cost[start];
        while(start>end){
            if(sum>=0){
                sum += gas[end] - cost[end];
                ++end;
            }
            else{
                --start;
                sum += gas[start] - cost[start];
            }
        }
        return sum >=0 ? start: -1;
    }
};

四 后記

期待我們的下一個(gè)題目吧