leecode 解题总结：134. Gas Station

#include <iostream>#include <stdio.h>#include <vector>#include <string>using namespace std;/*问题: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.分析:这是环形的部分。可以直接求出diff[i]=gas[i] - cost[i]，这就是第i栈可以实际获得的的油量。可以先求出diff数组，将数组全部累加求和，如果和<0，肯定不可以diff数组和>=0，肯定可以，题目说了解只有唯一一个，那么唯一的解会有什么特点？必须从diff[i]中为正值的地方开始行使，如果存在多个正值的地方，最简单的方式就是遍历所有diff数组中为正值的地方。但是这样时间复杂度就是O(n^2)了。举例:gas: 5 3 6 1(补充的汽油量)cost:3 4 3 5(每一站消耗的汽油量)diff:2 -1 3 -4diff每个元素和该元素相邻的前一个的元素累加求和记为数组sumsum: 2 1 4 0,发现了就是累加求和后值最小的元素的下一个元素sum的真实意义是从第0个车站开始后，开到当前站依次剩余的汽油量。找到一个最小值sum[k]，表示到达第k站剩余的汽油量最少，也就是从第0个站到达第k个站累计消耗的汽油最多，那么从第k+1个站到第0个站消耗的汽油量最少，显然应该从第k+1个站开始。证明假设不从第k+1个站开始，比如从第j(j!=k+1)个站开始出发，如果选择从第k+1个站开始，可以成功输入:4(元素个数)5 3 6 1(补充的汽油量)3 4 3 5(每一站消耗的汽油量)45 3 6 13 4 3 645 3 6 44 5 7 121 22 1输出:0-131关键:1 diff每个元素和该元素相邻的前一个的元素累加求和记为数组sumsum: 2 1 4 0,发现了就是累加求和后值最小的元素的下一个元素sum的真实意义是从第0个车站开始后，开到当前站依次剩余的汽油量。找到一个最小值sum[k]，表示到达第k站剩余的汽油量最少，也就是从第0个站到达第k个站累计消耗的汽油最多，那么从第k+1个站到第0个站消耗的汽油量最少，显然应该从第k+1个站开始。*/class Solution {public:    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {		if(gas.empty() || cost.empty() || gas.size() != cost.size())		{			return -1;		}		int size = gas.size();        vector<int> diff(size , 0);		int total = 0;		for(int i = 0 ; i < size ; i++)		{			diff.at(i) = gas.at(i) - cost.at(i);			total += diff.at(i);		}		//总的汽油剩余量为0，肯定不可能		if(total < 0)		{			return -1;		}		int minSum = diff.at(0);//最小值从第一个元素开始		int minIndex = 0;		int tempSum = diff.at(0);		for(int i = 1 ; i < size ; i++)		{			tempSum = diff.at(i) + tempSum;//计算开到第i个站时，累计剩余的汽油量			if(tempSum < minSum)//计算累计剩余汽油量最少的站			{				minSum = tempSum;				minIndex = i;			}		}		//因为只有一个解，出发的栈必定是从累计剩余汽油量最少的站的下一个站出发		if(minIndex == size - 1)		{			return 0;		}		else		{			return (minIndex + 1);		}    }};void PRint(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> gas;	 vector<int> cost;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 gas.clear();		 cost.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 gas.push_back(value);		 }		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 cost.push_back(value);		 }		 int index = solution.canCompleteCircuit(gas , cost);		 cout << index << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}