int farthest; // 裡面可能是垃圾值
int farthest = 0; // 明確從 0 開始
這題一開始在 index 0,所以:farthest = 0最合理。
2.每一格都要檢查因為目前這格可能把最遠距離推得更遠!
nums = [2,3,1,1,4]
index 0 1 2 3 4
先看 index 0:0 + nums[0]= 0 + 2= 2ㄤ;farthest = 2
目前知道可以走到:index 0、1、2
接著一定要看 index 1,因為:1 + nums[1]= 1 + 3= 4 so farthest = 4直接可以到終點。
每一格其實檢查兩件事:① current 有沒有在目前可達範圍內?② 這一格能不能把 farthest 推得更遠?
兩個 return true 差別:
if (farthest >= nums.size() - 1)
return true;提早成功,直接停止。
例如:nums = [2,0,0]
current = 0
0 + 2 = 2最後 index = 2(;index = 2=陣列中的位置2)→已知一定到得→ 馬上 return true
return true;function 最後的保底 return。
其實以這題目前的寫法+題目保證 nums 非空,正常成功時幾乎都會在上面先 return true;下面那行主要是讓 function 保證有回傳值。not good
nums = [3,2,1,0,4]
index 0 1 2 3 4
從 index 0:0 + 3 = 3;farthest = 3
補充0 + 3 = 3
0 = 目前站的位置 index 0
3 = nums[0] 的值,代表從這格最多能往右跳 3 格
所以:目前位置 0 + 最多跳 3 格 = 最遠能到 index 3。
回到主線
看 index 1:1 + 2 = 3;farthest 還是 3
看 index 2:2 + 1 = 3;farthest 還是 3
到 index 3:3 + 0 = 3;還是只能到 3,永遠到不了 index 4,所以 false。
每一格最多都只能把你送到 index 3,而 index 3 又是 0,路就在這裡斷掉。
4.早停萬歲
class Solution {
public:
bool canJump(vector<int>& nums) {
int last = nums.size() - 1;// 最後一格的 index
int farthest = 0;// 目前最遠能到的位置
for (int current = 0; current <= farthest; ++current) { // 只檢查目前到得了位置
farthest = max(farthest, current + nums[current]); // 更新最遠可達位
if (farthest >= last) // 已到終點
return true; // 早停
}
return false; // 可達範圍斷掉
}
};
5.current <= farthest
直接把「目前位置是否還走得到」放進 for 條件;一旦走不到,loop 自己停止,最後 return false。
能走就繼續 → 更新最遠 → 碰到終點立即 true → 可達範圍斷掉就 false。