leetCode解题报告之Gas Station-蒲公英云

leetCode解题报告之Gas Station

题目：

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;
    }
}