LeetCode 134. 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.

• 思路
  这道题目最为简单的解法即是模拟汽车在每一个节点跑一次，看是否在某个节点能跑完全部的路程，若能跑通，则说明存在了一条路径，若全部不能跑通，则说明不存在。代码见下
• 代码（c#）

 public int CanCompleteCircuit(int[] gas, int[] cost)
        {
            for (int i = 0; i < gas.Length; i++)
            {
                if (CanCompleteCircuit(gas, cost, i))//汽车从I节点出发，尝试是否可以跑通
                {
                    return i;
                }
            }
            return -1;
        }
        public bool CanCompleteCircuit(int[] gas, int[] cost, int start)
        {
            int now = gas[start];
            int count = 0;
            while (count < gas.Length)
            {
                now -= cost[start];//减油
                if (now < 0) return false;//汽油不能到达下一个节点
                count++;
                start++;
                if (start >= gas.Length)
                    start = 0;
                now += gas[start];//加油
            }
            return true;//全部的节点已经跑通，回到原节点
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

• 总结
  该算法几乎可以肯定不是最优的算法，但胜在容易理解。