題目描述（中等難度）
把這個(gè)題理解成下邊的圖就可以辉词。
每個(gè)節(jié)點(diǎn)表示添加的油量必孤，每條邊表示消耗的油量。題目的意思就是問我們從哪個(gè)節(jié)點(diǎn)出發(fā)瑞躺，還可以回到該節(jié)點(diǎn)隧魄。只能順時(shí)針方向走。
解法一 暴力解法
考慮暴力破解隘蝎，一方面是驗(yàn)證下自己對題目的理解是否正確购啄，另一方面后續(xù)的優(yōu)化也可以從這里入手。
考慮從第 0 個(gè)點(diǎn)出發(fā)嘱么，能否回到第 0 個(gè)點(diǎn)狮含。
考慮從第 1 個(gè)點(diǎn)出發(fā)，能否回到第 1 個(gè)點(diǎn)曼振。
考慮從第 2 個(gè)點(diǎn)出發(fā)几迄，能否回到第 2 個(gè)點(diǎn)。
... ...
考慮從第 n 個(gè)點(diǎn)出發(fā)冰评，能否回到第 n 個(gè)點(diǎn)映胁。
由于是個(gè)圓，得到下一個(gè)點(diǎn)的時(shí)候我們需要取余數(shù)甲雅。
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
//考慮從每一個(gè)點(diǎn)出發(fā)
for (int i = 0; i < n; i++) {
int j = i;
int remain = gas[i];
//當(dāng)前剩余的油能否到達(dá)下一個(gè)點(diǎn)
while (remain - cost[j] >= 0) {
//減去花費(fèi)的加上新的點(diǎn)的補(bǔ)給
remain = remain - cost[j] + gas[(j + 1) % n];
j = (j + 1) % n;
//j 回到了 i
if (j == i) {
return i;
}
}
}
//任何點(diǎn)都不可以
return -1;
}
解法二 優(yōu)化嘗試一
暴力破解慢的原因就是會(huì)進(jìn)行很多重復(fù)的計(jì)算解孙。比如下邊的情況：
假設(shè)當(dāng)前在考慮 i,先初始化 j = i
* * * * * *
^
i
^
j
隨后 j 會(huì)進(jìn)行后移
* * * * * *
^ ^
i j
繼續(xù)后移
* * * * * *
^ ^
i j
繼續(xù)后移
* * * * * *
^ ^
j i
此時(shí) j 又回到了第 0 個(gè)位置坑填，我們在之前已經(jīng)考慮過了這個(gè)位置。
如果之前考慮第 0 個(gè)位置的時(shí)候弛姜，最遠(yuǎn)到了第 2 個(gè)位置脐瑰。
那么此時(shí) j 就可以直接跳到第 2 個(gè)位置，同時(shí)加上當(dāng)時(shí)的剩余汽油廷臼，繼續(xù)考慮
* * * * * *
^ ^
j i
利用上邊的思想我們可以進(jìn)行一個(gè)優(yōu)化苍在，就是每考慮一個(gè)點(diǎn)，就將當(dāng)前點(diǎn)能夠到達(dá)的最遠(yuǎn)距離記錄下來荠商，同時(shí)到達(dá)最遠(yuǎn)距離時(shí)候的剩余汽油也要記下來寂恬。
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
//記錄能到的最遠(yuǎn)距離
int[] farIndex = new int[n];
for (int i = 0; i < farIndex.length; i++) {
farIndex[i] = -1;
}
//記錄到達(dá)最遠(yuǎn)距離時(shí)候剩余的汽油
int[] farIndexRemain = new int[n];
for (int i = 0; i < n; i++) {
int j = i;
int remain = gas[i];
while (remain - cost[j] >= 0) {
//到達(dá)下個(gè)點(diǎn)后的剩余
remain = remain - cost[j];
j = (j + 1) % n;
//判斷之前有沒有考慮過這個(gè)點(diǎn)
if (farIndex[j] != -1) {
//加上當(dāng)時(shí)剩余的汽油
remain = remain + farIndexRemain[j];
//j 進(jìn)行跳躍
j = farIndex[j];
} else {
//加上當(dāng)前點(diǎn)的補(bǔ)給
remain = remain + gas[j];
}
if (j == i) {
return i;
}
}
//記錄當(dāng)前點(diǎn)最遠(yuǎn)到達(dá)哪里
farIndex[i] = j;
//記錄當(dāng)前點(diǎn)的剩余
farIndexRemain[i] = remain;
}
return -1;
}
遺憾的是，這個(gè)想法針對 leetcode 的測試集速度上沒有帶來很明顯的提升莱没。不過記錄已經(jīng)求出來的解進(jìn)行優(yōu)化掠剑，這個(gè)思想還是經(jīng)常用的，也就是空間換時(shí)間郊愧。
讓我們換個(gè)思路繼續(xù)優(yōu)化。
解法三 優(yōu)化嘗試二
我們考慮一下下邊的情況井佑。
* * * * * *
^ ^
i j
當(dāng)考慮 i 能到達(dá)的最遠(yuǎn)的時(shí)候属铁，假設(shè)是 j。
那么 i + 1 到 j 之間的節(jié)點(diǎn)是不是就都不可能繞一圈了躬翁？
假設(shè) i + 1 的節(jié)點(diǎn)能繞一圈焦蘑，那么就意味著從 i + 1 開始一定能到達(dá) j + 1。
又因?yàn)閺?i 能到達(dá) i + 1盒发，所以從 i 也能到達(dá) j + 1例嘱。
但事實(shí)上，i 最遠(yuǎn)到達(dá) j 宁舰。產(chǎn)生矛盾拼卵，所以 i + 1 的節(jié)點(diǎn)一定不能繞一圈。同理蛮艰，其他的也是一樣的證明腋腮。
所以下一次的 i 我們不需要從 i + 1 開始考慮，直接從 j + 1 開始考慮即可壤蚜。
還有一種情況即寡，就是因?yàn)榈竭_(dá)末尾的時(shí)候，會(huì)回到 0袜刷。
如果對于下邊的情況聪富。
* * * * * *
^ ^
j i
如果 i 最遠(yuǎn)能夠到達(dá) j ，根據(jù)上邊的結(jié)論 i + 1 到 j 之間的節(jié)點(diǎn)都不可能繞一圈了著蟹。想象成一個(gè)圓墩蔓，所以 i 后邊的節(jié)點(diǎn)就都不需要考慮了梢莽，直接返回 -1 即可。
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
for (int i = 0; i < n; i++) {
int j = i;
int remain = gas[i];
while (remain - cost[j] >= 0) {
//減去花費(fèi)的加上新的點(diǎn)的補(bǔ)給
remain = remain - cost[j] + gas[(j + 1) % n];
j = (j + 1) % n;
//j 回到了 i
if (j == i) {
return i;
}
}
//最遠(yuǎn)距離繞到了之前钢拧，所以 i 后邊的都不可能繞一圈了
if (j < i) {
return -1;
}
//i 直接跳到 j蟹漓，外層 for 循環(huán)執(zhí)行 i++，相當(dāng)于從 j + 1 開始考慮
i = j;
}
return -1;
}
總
寫題的時(shí)候先寫出暴力的解法源内，然后再考慮優(yōu)化葡粒，有時(shí)候是一種不錯(cuò)的選擇。
更多詳細(xì)通俗題解詳見 leetcode.wang 膜钓。
