[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

【题意】

在环形路线上一共有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 <iostream>
#include <stdio.h>
#include <vector>
using namespace std;

// 时间复杂度 O(n)，空间复杂度 O(1)
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &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<int> gas =  {0,4,5};
    vector<int> cost = {1,2,6};
    result = solution.canCompleteCircuit(gas,cost);
    printf("Result:%d\n",result);
    return 0;
}