Brute Force. Time = O(n^2)
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
for (int startIndex = 0; startIndex < gas.length; startIndex++) {
if (canTravel(gas, cost, gas.length, startIndex)) {
return startIndex;
}
}
return -1;
}
private boolean canTravel(int[] gas, int[] cost, int nums, int startIndex) {
int index = startIndex;
int curGas = 0;
while (index < nums) {
curGas += gas[index] - cost[index];
if (curGas < 0) {
return false;
}
index ++;
}
index = 0;
while (index < startIndex) {
curGas += gas[index] - cost[index];
if (curGas < 0) {
return false;
}
index ++;
}
return true;
}
}
思想:link
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int nums = gas.length;
int curTank = 0;
int totalTank = 0;
int startingStation = 0;
for (int i = 0; i < nums; i++) {
curTank += gas[i] - cost[i];
totalTank += gas[i] - cost[i];
if (curTank < 0) {
curTank = 0;
startingStation = i + 1;
}
}
return totalTank >= 0 ? startingStation : -1;
}
}