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个加油站，每个加油站的存储容量为gas[i].你有一辆汽油无限存储的汽车，如果你从加油站i到下一站（i+1），你需要

消耗汽油cost[i] 你从某一个加油站开始你的旅程，但是你的汽车里没有任何的汽油。

如果你能沿着环形路线旅游一遍，返回你开始旅游的加油站的下标否则返回-1

注意：

解决方案唯一

【分析】

首先想到的是 O(N^2)的解法，对每个点进行模拟。
O(N) 的解法是，设置两个变量，sum 判断当前的指针的有效性；total 则判断整个数组是否有
解，有就返回通过 sum 得到的下标，没有则返回 -1

如果total>=0即(gas[0] - cost[0])+........+(gas[n] - cost[n]) >= 0则肯定有一个解。

【代码】

/*********************************
*   日期：2014-01-25
*   作者：SJF0115
*   题号: Gas Station
*   来源：http://oj.leetcode.com/problems/gas-station/
*   结果：AC
*   来源：LeetCode
*   总结：
**********************************/
#include 
  
   
#include 
   
     #include 
    
      using namespace std; // 时间复杂度 O(n)，空间复杂度 O(1) class Solution { public: int canCompleteCircuit(vector
     
       &gas, vector
      
        &cost) { int total = 0; int j = -1; for (int i = 0, sum = 0; i < gas.size(); ++i) { sum += gas[i] - cost[i]; total += gas[i] - cost[i]; if (sum < 0) { j = i; sum = 0; } } return total >= 0   j + 1 : -1; } }; int main() { Solution solution; int result; vector
       
         gas = {0,4,5}; vector
        
          cost = {1,2,6}; result = solution.canCompleteCircuit(gas,cost); printf("Result:%d\n",result); return 0; }