55 Jump Game
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
一開(kāi)始考慮用動(dòng)態(tài)規(guī)劃嫌褪，當(dāng)前位置i是否可以到達(dá)可以轉(zhuǎn)化為纤虽，[0,...,i-1]區(qū)間的位置可以到達(dá)且該位置step大于與i的index差值轰传，用一個(gè)boolean數(shù)組dp[]來(lái)存儲(chǔ)之前的狀態(tài)，然而寫(xiě)完就LTE了昌执。。丧慈。不開(kāi)心馍迄。。麦备。因?yàn)槊看闻袛喽夹枰玫街八袪顟B(tài)孽椰，太耗時(shí)了昭娩。
改進(jìn)：用maxCover記錄最大可到達(dá)距離，step記錄仍然可走的步數(shù)黍匾，遍歷數(shù)組更新這兩個(gè)值栏渺，若step=0且沒(méi)有走到數(shù)組尾部，則返回false锐涯；若遍歷完成則返回true磕诊，這樣只用掃描一遍且每一步都不需要再掃描之前每一步的狀態(tài)。
原因是每次只用記錄當(dāng)前可以走到最大距離的那個(gè)狀態(tài)Ｎ齐纭ｖ铡！
代碼：
public class Solution {
public boolean canJump(int[] nums) {
if (nums.length == 0) return false;
int maxCover = 0, step = 1;
for (int i = 0; i < nums.length; i++) {
step--;
if (i + nums[i] > maxCover) {
maxCover = i + nums[i];
step = nums[i];
}
if (step == 0 && i < nums.length-1) return false;
}
return true;
}
}
45 Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
For example:
Given array A = [2,3,1,1,4]
The minimum number of jumps to reach the last index is 2.
(Jump 1 step from index 0 to 1, then 3 steps to the last index.)
Note:You can assume that you can always reach the last index.
關(guān)鍵的問(wèn)題1：到底什么時(shí)候總步數(shù)+1呢壶笼？
回答：假設(shè)到遍歷到數(shù)組index=i的位置神僵，在此之前jump到的位置為k；在位置k最遠(yuǎn)可以到達(dá)的范圍是[k,reach]覆劈，如果reach<i保礼，說(shuō)明[k-reach]之間必須再jump一次，這樣才能保證i在可以reach的范圍內(nèi)责语！
關(guān)鍵問(wèn)題2：那究竟在[k-reach]的哪個(gè)位置再次jump呢炮障？
回答：根據(jù)貪心算法，應(yīng)該挑可以reach范圍最遠(yuǎn)的那個(gè)點(diǎn)坤候，如果需要求jump game的最短次數(shù)的jump路徑胁赢，就需要記錄這個(gè)點(diǎn)了。
本題僅解決問(wèn)題1即可白筹。
public class Solution {
public int jump(int[] nums) {
if (nums.length <= 1) return 0;
int reach = nums[0];
int lastreach = 0;
int step = 0;
for (int i = 1; i <= reach && i < nums.length; i++) {
if (i > lastreach) {
step++;
lastreach = reach;
}
reach = Math.max(reach, i+nums[i]);
}
if (reach < nums.length-1) return 0;
return step;
}
}
