class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int[] temp = new int[n];
for(int i = 0; i < n; i++) {
temp[i] = gas[i] - cost[i];
}
for(int i = 0; i < n; i++) {
int ans = 0, flag = 1;
for(int j = 0; j < n; j++) {
ans += temp[(i+j)%n];
if(ans < 0) {
flag = 0;
break;
}
}
if(flag == 1) {
return i;
}
}
return -1;
}
}
稍微优化一下。
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int[] temp = new int[n];
for(int i = 0; i < n; i++) {
temp[i] = gas[i] - cost[i];
}
for(int i = 0; i < n; i++) {
int ans = 0, flag = 1;
for(int j = 0; j < n; j++) {
ans += temp[(i+j)%n];
if(ans < 0) {
// 补一下
i += j;
flag = 0;
break;
}
}
if(flag == 1) {
return i;
}
}
return -1;
}
}
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int i = 0;
while (i < n) {
int sumOfGas = 0, sumOfCost = 0;
int cnt = 0;
while (cnt < n) {
int j = (i + cnt) % n;
sumOfGas += gas[j];
sumOfCost += cost[j];
if (sumOfCost > sumOfGas) {
break;
}
cnt++;
}
if (cnt == n) {
return i;
} else {
i = i + cnt + 1;
}
}
return -1;
}
}