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.
解析
- 思路 1:可以穷举每个位置,求和是否大于 0;
- 非常经典的一道题。可以转换成求最大连续和做,但是有更简单的方法。
- 基于一个数学定理:如果一个数组的总和非负,那么一定可以找到一个起始位置,从他开始绕数组一圈,累加和一直都是非负的
- 继续对问题进行抽象,我们肯定希望一开始的路程都是加油 > 消耗的,这样就可以累积油量应付后面的消耗量大的,根据这个思路,就转变成求数组的最大连续子序列的和(并且记录起始下标),这是我们前面接触过的题目。
- 因为是循环数组,我们还得考虑一种情况:就是首尾都是正数,怎么办呢?
- 正因为是循环数组,还有一种类似于快排前后指针的操作。
- class Solution {
- public:
- int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
-
- if (gas.size()==0||cost.size()==0||gas.size()!=cost.size())
- {
- return -1;
- }
- int index = 0;
- int sum_resdual = 0;
-
- for (int j = 0; j < gas.size();j++)
- {
- sum_resdual += (gas[j] - cost[j]);
- }
- if (sum_resdual<0)
- {
- return -1;
- }
-
- sum_resdual = 0;
- for (int i = 0; i < gas.size();i++)
- {
- //index = 0; //bug
- sum_resdual += (gas[i] - cost[i]);
- if (sum_resdual<0)
- {
- index = i + 1;
- sum_resdual = 0;
- }
- }
-
- return index;
- }
- };
- int canCompleteCircuit(vector < int > &gas, vector < int > &cost) {
- int start = 0; // 起始位置
- int remain = 0; // 当前剩余燃料
- int debt = 0; // 前面没能走完的路上欠的债
- for (int i = 0; i < gas.size(); i++) {
- remain += gas[i] - cost[i];
- if (remain < 0) {
- debt += remain;
- start = i + 1;
- remain = 0;
- }
- }
-
- return remain + debt >= 0 ? start: -1; //这句话保证了求和sum<0,返回-1
- }
- 从 start 出发, 如果油量足够, 可以一直向后走 end++; 油量不够的时候,start 向后退 最终 start == end 的时候,如果有解一定是当前 start 所在位置
- class Solution {
- public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
- int start = gas.size() - 1;
- int end = 0;
- int sum = gas[start] - cost[start];
- while(start > end){
- if(sum >= 0){
- sum += gas[end] - cost[end];
- ++end;
- }else{
- --start;
- sum += gas[start] - cost[start];
- }
- }
- return sum >=0 ? start : -1;
-
-
- }
- };
题目来源