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.
---------------------------------------------------------
O(n) time, in space
if gas[i] < cost[i], skip to i + 1, reset everything
else, add the difference to the gas[i + 1] station, repeat
until all stations have been checked.
Note that count < size + 1 since this is supposed to be a loop
class Solution { public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { // Note: The Solution object is instantiated only once and is reused by each test case. int startPoint = -1, gasLeft = 0; int size = gas.size(); for (int i = 0, count = 0; i < size && count < size + 1; i++, count++) { if (i == startPoint) return i; // found a start point gasLeft += gas[i]; if (gasLeft >= cost[i]) { if (startPoint == -1) { startPoint = i; } gasLeft -= cost[i]; if (i == size - 1) { i = -1; } }else { // reset gasLeft = 0; startPoint = -1; } } return startPoint; } };----------------------------
Neat version, from internet
int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int sum = 0; int total = 0; int j = -1; for(int i = 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; }Update on Oct-29-2014
If car starts at A and can not reach B. Any station between A and B can not reach B.(B is the first station that A can not reach.
The solution below is not completely correct, it cannot pass the case where total cost is larger than gas, for instance: gas = {5,5,1,2,4} cost = {4,4,4,4,4}. Although OJ accepts it
public: int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int leftGas = 0; int index = -1; for (int i = 0; i < gas.size(); i++) { if (index == -1) index = i; leftGas += gas[i] - cost[i]; if (leftGas < 0) { index = -1; leftGas = 0; } } if (leftGas + gas[0] - cost[0] < 0) return -1; return index; } };
No comments:
Post a Comment