leetCode解题报告之Gas Station

偏执的太偏执、 2022-08-26 04:45 113阅读 0赞

**题目：**

There are N gas stations along a circular route, where the amount of gas at station i is `gas[i]`.

You have a car with an unlimited gas tank and it costs `cost[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.

**分析：**

题意大概是说，你有一辆车，这辆车有一个可以无限装油的油箱，然后有个圆环，圆环上有N个加油点，加油点 i 所能加油的量用gas\[i\] 来表示，而你从 加油点 i  开车到 加油点 i+1 中间这段路途，你要消耗的油量 用 cost\[i\] 来表示。

最后你要绕圆圈从起点开始，最后再转回到起点，让你求出起点的位置，并返回起点的下标，如果找不到这样的起点，那么返回-1

**解题思路：**

这种题目的话，我能想到的就是简单的解法，你for循环，每个加油点都做起点。

如： 加油点 i 作为起点

1、初始化：油箱 tank = 0;

2、从加油点 i  到 加油点 gas.length -1 ，判断其中是否有 tank < cost\[i\] 的情况，如果有的话，表示这车油已经不足以支撑你从 加油点 i  到 加油点 i+1 这段路途了

3、如果前面第2步 顺利走到了加油点 gas.length -1, 那么要走到起点（加油点 i），就和第2步一样了，从 加油点 0 到加油点 i，判断其中是否有 tank < cost\[i\] 的情况，如果有的话，表示这车油已经不足以支撑你从 加油点 i  到 加油点 i+1 这段路途了

4、如果最后 回到了起点 则这个 i 便是题目要求的 满足条件的起点，返回它， 否则继续找下一个 加油点 作为起点的情况

5、全部加油点找完还没有满足条件的加油点时，返回-1

**图解：**

![SouthEast][]

**AC代码：**

public class Solution {
        public int canCompleteCircuit(int[] gas, int[] cost) {
            int gasLen = gas.length;
            int costLen = cost.length;
            if (gasLen == 0 || costLen == 0)
                return -1;
            
            int k, j;
            for (int i=0; i<gasLen; ++i){
                int tank = 0;
                
                for (k=i; k<gasLen; ++k){
                    tank += gas[k];
                    if (cost[k] > tank){
                        break;  
                    }
                    tank -= cost[k];
                }
                //如果前面的没走到加油点 gasLen-1, 那么证明这个起点 i 不满足条件
                if (k != gasLen)
                    continue;
                for (j=0; j<i; ++j){
                    tank += gas[j];
                    if (cost[j] > tank){
                        break;  
                    }
                    tank -= cost[j];
                }
                
                //如果回到了起点 i 那么这个起点 i 便满足条件了，否则继续下一个起点的判断
                if (j == i)
                    return i;
            }
            return -1;
        }
    }

[SouthEast]: /images/20220824/7182768a90ca4c0992d0359f2f6f827c.png