加油站

題目描述：在一條環(huán)路上有 N 個(gè)加油站，其中第 i 個(gè)加油站有汽油 gas[i] 升。

你有一輛油箱容量無限的的汽車，從第 i 個(gè)加油站開往第 i+1 個(gè)加油站需要消耗汽油 cost[i] 升。你從其中的一個(gè)加油站出發(fā)，開始時(shí)油箱為空。

如果你可以繞環(huán)路行駛一周，則返回出發(fā)時(shí)加油站的編號，否則返回 -1。

說明:

• 如果題目有解，該答案即為唯一答案。

• 輸入數(shù)組均為非空數(shù)組，且長度相同。

• 輸入數(shù)組中的元素均為非負(fù)數(shù)。

示例說明請見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/gas-station/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解法一：窮舉法

從第一個(gè)加油站開始，判斷從當(dāng)前加油站開始作為起點(diǎn)是否可以環(huán)行一周回到起點(diǎn)，如果可以，則返回當(dāng)前加油站的位置，如果不可以則將下一個(gè)加油站作為起點(diǎn)判斷。具體判斷某一個(gè)加油站作為起點(diǎn)是否可以環(huán)行的過程如下：

• 如果當(dāng)前油量加上當(dāng)前加油站的汽油量少于當(dāng)前加油站的消耗，說明無法走到下一站，跳過這種可能性；

• 如果可以走到下一站，記錄當(dāng)前剩余油量和已經(jīng)走過的加油站的數(shù)量，然后走到下一站，繼續(xù)判斷；

• 知道走到最后，如果走過所有加油站，說明以當(dāng)前的起始加油站作為起點(diǎn)是可以環(huán)行一周的，返回起始加油站的位置。

【每日寄語】 世上無難事，只怕有心人。一個(gè)人在實(shí)現(xiàn)理想的過程中，會遇到很多的困難，這不要緊，只要自己有那份心，堅(jiān)持做下去，你就會成功。