在一條環路上有?N?個加油站，其中第?i?個加油站有汽油?gas[i]?升。

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

如果你可以繞環路行駛一周，則返回出發時加油站的編號，否則返回 -1。

說明:?

如果題目有解，該答案即為唯一答案。
輸入數組均為非空數組，且長度相同。
輸入數組中的元素均為非負數。
示例?1:

輸入:?
gas ?= [1,2,3,4,5]
cost = [3,4,5,1,2]

輸出: 3

解釋:
從 3 號加油站(索引為 3 處)出發，可獲得 4 升汽油。此時油箱有 = 0 + 4 = 4 升汽油
開往 4 號加油站，此時油箱有 4 - 1 + 5 = 8 升汽油
開往 0 號加油站，此時油箱有 8 - 2 + 1 = 7 升汽油
開往 1 號加油站，此時油箱有 7 - 3 + 2 = 6 升汽油
開往 2 號加油站，此時油箱有 6 - 4 + 3 = 5 升汽油
開往 3 號加油站，你需要消耗 5 升汽油，正好足夠你返回到 3 號加油站。
因此，3 可為起始索引。
示例 2:

輸入:?
gas ?= [2,3,4]
cost = [3,4,3]

輸出: -1

解釋:
你不能從 0 號或 1 號加油站出發，因為沒有足夠的汽油可以讓你行駛到下一個加油站。
我們從 2 號加油站出發，可以獲得 4 升汽油。 此時油箱有 = 0 + 4 = 4 升汽油
開往 0 號加油站，此時油箱有 4 - 3 + 2 = 3 升汽油
開往 1 號加油站，此時油箱有 3 - 3 + 3 = 3 升汽油
你無法返回 2 號加油站，因為返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，無論怎樣，你都不可能繞環路行駛一周。

思路：

如果總的油量大于消耗量，那么一定有一個點出發可以跑完全程

從頭開始，如果到某一點無法繼續跑下去，那就把這一點設為起點繼續跑

提交的代碼：

class Solution {
? ? public int canCompleteCircuit(int[] gas, int[] cost) {
? ? ? ? int result = 0;
? ? int sum = 0;
? ? int hasResult = 0;//用于判斷是否有跑完全程所需的油
? ? for (int i = 0; i < gas.length; i++) {
? ? ? ? hasResult +=gas[i]-cost[i];
? ? ? ? if(sum > 0) {
? ? ? ? ? ? sum += gas[i]-cost[i];
? ? ? ? } else {
? ? ? ? ? ? sum = gas[i]-cost[i];
? ? ? ? ? ? result = i;
? ? ? ? }
? ? }
? ? if(hasResult>=0)
? ? {
? ? ?? ?return result;
? ? }
? ? return -1;
? ? }
}

完整的代碼：

public class Solution134 {
public static int canCompleteCircuit(int[] gas, int[] cost) {
?? ?int result = 0;
? ? int sum = 0;
? ? int hasResult = 0;//用于判斷是否有跑完全程所需的油
? ? for (int i = 0; i < gas.length; i++) {
? ? ? ? hasResult +=gas[i]-cost[i];
? ? ? ? if(sum > 0) {
? ? ? ? ? ? sum += gas[i]-cost[i];
? ? ? ? } else {
? ? ? ? ? ? sum = gas[i]-cost[i];
? ? ? ? ? ? result = i;
? ? ? ? }
? ? }
? ? if(hasResult>=0)
? ? {
? ? ?? ?return result;
? ? }
? ? return -1;
? ? }
public static void main(String[] args)
{
?? ?int gas[] = {5,8,2,8};
?? ?int cost[] = {6,5,6,6};
?? ?System.out.println(canCompleteCircuit(gas,cost));
}
}
?

總結

以上是生活随笔為你收集整理的Leetcode--134. 加油站的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。