@[toc]
題目
Problem: 45. 跳躍游戲 II
給定一個(gè)長度為 n 的 0 索引整數(shù)數(shù)組 nums。初始位置為 nums[0]。
每個(gè)元素 nums[i] 表示從索引 i 向前跳轉(zhuǎn)的最大長度。換句話說，如果你在 nums[i] 處，你可以跳轉(zhuǎn)到任意 nums[i + j] 處:
0 <= j <= nums[i]
i + j < n
返回到達(dá) nums[n - 1] 的最小跳躍次數(shù)。生成的測(cè)試用例可以到達(dá) nums[n - 1]。
示例 1:
輸入: nums = [2,3,1,1,4]
輸出: 2
解釋: 跳到最后一個(gè)位置的最小跳躍數(shù)是 2。
從下標(biāo)為 0 跳到下標(biāo)為 1 的位置，跳 1 步，然后跳 3 步到達(dá)數(shù)組的最后一個(gè)位置。
示例 2:
輸入: nums = [2,3,0,1,4]
輸出: 2
提示:
1 <= nums.length <= 104
0 <= nums[i] <= 1000
題目保證可以到達(dá) nums[n-1]
題解
思路
正向太復(fù)雜，直接考慮反向，從后往前跳。
每次都試圖跳到最前面，重復(fù)多次，到達(dá)起點(diǎn)即可。
試圖跳到最前面的原因：
如果有兩種路線可以跳到n-1位置，一個(gè)從j出發(fā)，一個(gè)從k出發(fā)，j<k，那么，前一次跳躍：
- 如果從j的前方出發(fā)，能夠到達(dá)k的跳躍一定能到達(dá)j，而能夠到達(dá)j的跳躍不一定能到達(dá)k，可能需要再一次跳躍，所以選擇j，這話次數(shù)不會(huì)比k多。
- 如果從j的后方出發(fā)，可以將新的出發(fā)點(diǎn)視為k，增加了一次跳躍，但情況沒有任何改善。
解題方法
- 定義一個(gè)函數(shù)，輸入現(xiàn)在的位置，輸出跳到現(xiàn)在位置的最優(yōu)起點(diǎn)（即index最小的起點(diǎn)）
采用一個(gè)遍歷，從0開始往后遍歷，直到能夠到達(dá)現(xiàn)在的位置，就返回，如果沒找到，返回NAN
- 采用一個(gè)while循環(huán)，當(dāng)位置>0時(shí)，重復(fù)調(diào)用1中的函數(shù)，并計(jì)數(shù)。
復(fù)雜度
時(shí)間復(fù)雜度:
空間復(fù)雜度:
Code
class Solution {
public:
int jump(vector<int>& nums) {
//只要彈跳最大長度比所需要的長度長，那么就可以彈跳。
//我們需要找到彈跳次數(shù)的最小值，如果某種情況確定比其他情況更快，即可以將其他情況排除。
//從正向來分析的話，可能性有非常多種，因?yàn)閺椞鴷r(shí)可以在最大長度以內(nèi)隨意跳躍，不知道哪一個(gè)是最優(yōu)解。
//只能從反向來分析，如果我需要跳躍到末尾，可能性是相對(duì)有限的，它所在的位置+它的值高于末尾所在的位置才可以跳躍。
//最重要的特性：在一步彈跳內(nèi)，出發(fā)的位置越靠前，一定越有優(yōu)勢(shì)，因?yàn)樵谝淮翁S中，能跳到靠后位置的，一定能跳到靠前的位置，但能跳到靠前位置的，可能需要再一次跳躍才能跳到靠后的位置，因此，靠前的出發(fā)點(diǎn)不會(huì)比靠后的出發(fā)點(diǎn)所需要的次數(shù)更多。
//以下所有內(nèi)容，采用反向的分析，即從末尾往前跳，每次跳到可行的最遠(yuǎn)的位置
int place = nums.size()-1;
auto oneJump = [&](int placeBefore)->int{//一次jump（從后往前跳），輸入jump前的place，輸出jump后的place，輸出的place是所有jump可能中，最靠前的那一個(gè)jump
for(int i = 0; i<placeBefore;i++){//從前開始遍歷，遍歷到能夠到達(dá)placeBefore即返回
if(nums[i] + i >= placeBefore){
return i;
}
}
return NAN;
};
int jumpTime = 0;
while(place > 0){
place = oneJump(place);
jumpTime++;
}
return jumpTime;
};
};
