在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
- 如果题目有解，该答案即为唯一答案。
- 输入数组均为非空数组，且长度相同。
- 输入数组中的元素均为非负数。
示例 1:
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
\n
👍 693👎 0
题解
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
private int[] gasDouble;
private int[] costDouble;
private boolean doubled = false;
private int singleLength = 0;
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = -1;
singleLength = gas.length;
for (int i = 0; i < singleLength; i++) {
if (gas[i] < cost[i]){
continue;
}
if (!doubled){
doubled = true;
gasDouble = new int[singleLength*2];
costDouble = new int[singleLength*2];
for (int i1 = 0; i1 < singleLength; i1++) {
gasDouble[i1] = gas[i1];
gasDouble[i1+singleLength] = gas[i1];
costDouble[i1] = cost[i1];
costDouble[i1+singleLength] = cost[i1];
}
}
if (tryDrive(i,i+ gas.length)){
return i;e1d
}
}
return start;
}
private boolean tryDrive(int startIndex, int target){
int gasLeft = 0;
for (int i = startIndex; i < singleLength+startIndex; i++) {
gasLeft += gasDouble[i];
gasLeft -= costDouble[i];
if (gasLeft<0){
return false;
}
}
return true;
}
}
//leetcode submit region end(Prohibit modification and deletion)
这边先找到一个起步点，起步点必定要加气量大于等于到下一个加气站的消耗量。
然后从这个站点的开始往后尝试，挨个求和，这边其实可以考虑下前缀和的作法。判断从 i点能否到i+n的的判断规则是，从i点往后，每个点的加气前缀和要大于对应点的消耗量前缀和。
所以这里尝试一下从i点开始往后，一直再绕一圈回来回到i位置，而对应的破换成链的作法之一，选择了构建一个双倍长度的数组。从i点位置，往后跑原来的环的长度gas.length个位置，及等同于跑了一整圈。
如果能跑成功，那么返回当前位置，如果跑不成功，继续尝试下一个，直到从环上每个位置都尝试过了一遍。
这边其实还有一个点可以，直接抛出结论，如果从i位置开始跑，跑到i+n位置，失败了。那么下一次就直接可以i+n位置开始。要证明起来有点复杂，emmm，不大好描述，不过前面已经说了其实。
就是从 i点能否到i+n的的判断规则是，从i点往后，每个点的加气前缀和要大于对应点的消耗量前缀和。
因为我们是从i点开始的，所以必定有i点的加气量，大于i点的消耗量。但是到了i+n点的时候却跑步过去了，那么在i点之后到i+n点的时候，加气量之和一定是小于消耗量之和的。如果我们把这一段看成是一个点的话，比如是点i_virtual，那么显然i_virtual点的加气量小于消耗量。那么这段就是可以跳过的。
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
private int[] gasDouble;
private int[] costDouble;
private boolean doubled = false;
private int singleLength = 0;
private int startNext = -1;
public int canCompleteCircuit(int[] gas, int[] cost) {
int start = -1;
singleLength = gas.length;
for (int i = 0; i < singleLength; i++) {
if (gas[i] < cost[i]){
continue;
}
if (!doubled){
doubled = true;
gasDouble = new int[singleLength*2];
costDouble = new int[singleLength*2];
for (int i1 = 0; i1 < singleLength; i1++) {
gasDouble[i1] = gas[i1];
gasDouble[i1+singleLength] = gas[i1];
costDouble[i1] = cost[i1];
costDouble[i1+singleLength] = cost[i1];
}
}
if (tryDrive(i,i+ gas.length)){
return i;
}else{
i = startNext;
}
}
return start;
}
private boolean tryDrive(int startIndex, int target){
int gasLeft = 0;
startNext = startIndex+1;
for (int i = startIndex; i < singleLength+startIndex; i++) {
gasLeft += gasDouble[i];
gasLeft -= costDouble[i];
startNext = i;
if (gasLeft<0){
return false;
}
}
return true;
}
}
//leetcode submit region end(Prohibit modification and deletion)
解答成功:
执行耗时:28 ms,击败了34.70% 的Java用户
内存消耗:38.7 MB,击败了37.53% 的Java用户
额，马马虎虎吧
