[LeetCode]134.Gas Station

本文主要是介绍[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;
}

这篇关于[LeetCode]134.Gas Station的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---