一 前言
昨天開始了算法系列的第一篇留瞳，是有關(guān)樹的一個(gè)問題拒迅，今天給大家繼續(xù)帶來有關(guān)貪心策略的一個(gè)問題~現(xiàn)在就開始吧~
二 題目
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]這么多的汽油她倘，你最開始有一個(gè)沒有汽油的坦克璧微，你從第i個(gè)加油站走到它的下一個(gè)i+1個(gè)加油站消耗汽油cost[i]這么多，問你是否可以找到一個(gè)站帝牡，從該站出發(fā)可以繞著該路徑兜風(fēng)一圈往毡，有的話返回該站的標(biāo)號(hào)，沒有的話返回-1靶溜。
三 思路分析及代碼
我們假設(shè)坦克從N-1這站出發(fā)（也就是0后面那個(gè)开瞭，因?yàn)樗麄兪莻€(gè)環(huán)形所以首尾相接），末尾位置我們設(shè)為0罩息，也就是start = N-1嗤详，end = 0，從start開始往end的方向走瓷炮，這個(gè)時(shí)候我們設(shè)置一個(gè)變量sum用來記錄坦克油箱中還剩多少油葱色。那么開始時(shí)sum = gas[i] - cost[i]，接下來是關(guān)鍵娘香，如果現(xiàn)在這個(gè)sum大于0證明坦克現(xiàn)在還有油苍狰，就可以嘗試向下一站走，也就是end++烘绽。如果sum小于0證明坦克從start開往他的下一站（針對(duì)當(dāng)前狀態(tài)就是從N-1開到0）沒有足夠的油了淋昭，那么就嘗試把start往前一站挪，也就是變?yōu)閺腘-2開始嘗試安接。不斷進(jìn)行這樣的操作翔忽，知道start <= end證明真?zhèn)€過程結(jié)束了，這時(shí)如果sum >= 0證明可以支撐坦克走完一圈，返回對(duì)應(yīng)的start位置就是結(jié)果歇式。如果sum < 0證明坦克無法走完一圈驶悟，返回-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è)題目吧
