【leetcode面試經(jīng)典150題】專欄系列將為準(zhǔn)備暑期實習(xí)生以及秋招的同學(xué)們提高在面試時的經(jīng)典面試算法題的思路和想法。本專欄將以一題多解和精簡算法思路為主，題解使用C++語言。（若有使用其他語言的同學(xué)也可了解題解思路，本質(zhì)上語法內(nèi)容一致）
【題目描述】
給定一個長度為?n?的?0 索引整數(shù)數(shù)組?nums。初始位置為?nums[0]。
每個元素?nums[i]?表示從索引?i?向前跳轉(zhuǎn)的最大長度。換句話說，如果你在?nums[i]?處，你可以跳轉(zhuǎn)到任意?nums[i + j]?處:文章來源：http://www.zghlxwxcb.cn/news/detail-844803.html
-
0 <= j <= nums[i]? i + j < n
返回到達(dá)?nums[n - 1]?的最小跳躍次數(shù)。生成的測試用例可以到達(dá)?nums[n - 1]。文章來源地址http://www.zghlxwxcb.cn/news/detail-844803.html
【示例一】
輸入: nums = [2,3,1,1,4] 輸出: 2 解釋: 跳到最后一個位置的最小跳躍數(shù)是 2。 ? 從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳?1步，然后跳?3步到達(dá)數(shù)組的最后一個位置。
【示例二】
輸入: nums = [2,3,0,1,4] 輸出: 2
【提示及數(shù)據(jù)范圍】
1 <= nums.length <= 10的4次方0 <= nums[i] <= 1000- 題目保證可以到達(dá)?
nums[n-1]
【代碼】
// 貪心
// 維護(hù)當(dāng)前能夠到達(dá)的最大下標(biāo)位置，記為邊界。
// 我們從左到右遍歷數(shù)組，到達(dá)邊界時，更新邊界并將跳躍次數(shù)增加 1。
// 由于題目中一定可以到達(dá)最后一個元素，所以不用再枚舉最后一個元素
int jump(vector<int>& nums) {
int maxpos = 0,n = nums.size(),end = 0,step = 0;
for(int i = 0;i<n-1;i++){
maxpos = max(maxpos,i + nums[i]);
if(i == end){
end = maxpos;
step++;
}
}
return step;
}到了這里，關(guān)于【leetcode面試經(jīng)典150題】10.跳躍游戲 II（C++）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
