本文共 2072 字,大约阅读时间需要 6 分钟。
(注意题目给出的条件)
如果对于起点 index
有 gas[index] - cost[index] < 0
,则 index
肯定无法作为起点。因此肯定是从 start = x && gas[x] - cost[x] >= 0
的点开始,该点才有可能是答案。
为什么说是有可能,因为还要计算该点之后的所有点是否符合要求。否则就要再换一个起点继续去计算,看是否符合题意。
public int canCompleteCircuit(int[] gas, int[] cost) { if (gas == null || cost == null || gas.length == 0 || cost.length == 0) { return -1; } int len = gas.length; for (int i = 0; i < len; i++) { // 如果最开始可以从起点到下一个点 if (gas[i] >= cost[i]) { if (isValid(i, gas, cost)) { return i; } } } return -1;}private boolean isValid(int start, int[] gas, int[] cost) { int len = gas.length; int gasSum = gas[start] - cost[start]; // 避免从 len-1 的位置过渡到卫位置 0 时出现数组越界 int p = (start + 1) % len; while (p != start) { gasSum += (gas[p] - cost[p]); if (gasSum < 0) { return false; } p = (p + 1) % len; } return true;}
要注意的就是 index 从末尾向位置 0 的过渡。
首先需要明确的一点是,如果整个路程总的油量 gasSum 小于总的耗油量 costSum,则无论从哪个点触发,都铁定无法绕行一周。
然后试想,有两个点 i1
、i2
,且是从 i1
驶向 i2
,有 sum
表示从 i1
到达 i2
时油箱剩余的油量,此时有 sum ∈ [0, +∞]
,然后要从 i2
到下一个点(即 i2 + 1
),此时有 sum + gas[i2] - cost[i2]
,假设结果为 tmp
。
此时有两种情况,tmp < 0
和 tmp >= 0
。如果小于 0,则表示从 i2
到下一个点的耗油量太大,根本无法达到。因此,在 [i1, i2]
中的任意一点出发,都无法达到 i2 + 1
这个位置点。
划重点,因为从 i1
至 i2-1
的任意一点,要去 i2+1
都必须先到达 i2
,而从 i2
到 i2+1
需要的油量 cost[i2]
,是 gas[i2] + 之前剩余的油量 sum
都无法满足的,即使 sum
是无限大,依然无法摆脱现实。因此在 [i1, i2]
中的任意一点出发,都无法达到 i2 + 1
这个位置点。
因此,i1
至 i2
的点都被排除在外了,可能的情况也只能是从 i2+1
开始。
public int canCompleteCircuit(int[] gas, int[] cost) { if (gas == null || cost == null || gas.length == 0 || cost.length == 0) { return -1; } int sum = 0; // 用于记录总的油量减去耗油量的剩余值 int total = 0; int index = -1; for (int i = 0; i < gas.length; i++) { sum += gas[i] - cost[i]; total += gas[i] - cost[i]; if (sum < 0) { // 注意,可能的情况是 i2+1,因此这里记录为 i,而不是 i+1 index = i; sum = 0; } } // 注意,返回的时候为 i+1 return total < 0 ? -1 : index + 1;}
参考文章:
1、 2、转载地址:http://zrerj.baihongyu.com/