901
技術社區[雲棲]
[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
* 來源：https://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;
}
最後更新：2017-04-03 12:54:47