Jump Game (M)
題目
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.
Example 1:
Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.
題意
給定一個陣列，每個數字元素代表以當前下標為起點，能夠向右走的步數，判斷該陣列能否從第一個元素開始走到最后一個元素，
思路
使用回溯法會超時，原因在于對每個下標進行了多次判斷，利用陣列記錄每個下標在遞回程序中是否已經嘗試過，以此對回溯法優化，可以AC，但運行時間將近1000ms，
動態規劃：dp[i]代表以下標i結尾的左子陣列整體能夠走到的最遠的下標，以 [3, 1, 2, 0] 為例，dp[0] = 3 表示子陣列 [3] 最遠能走到下標3，dp[1] = 3 表示子陣列 [3, 1] 整體最遠能走到下標3，dp[2] = 4 表示子陣列 [3, 1, 2] 整體最遠能走到下標4(雖然4已經在陣列外)，不難發現規律：\(dp[i]=max(dp[i-1],\ i+nums[i])\)，當然前提是 i <= dp[i - 1]，即i必須是一個能夠到達的點；如果不能到達i，則i之后所有的下標都無法到達，那么最后一個下標也一定無法到達，
官方解答(貪心)：官方提供了一種更加高效省空間的貪心演算法：用lastPos標記最左側一個能夠到達尾元素的下標，初始為nums.length - 1；從右向左掃描，如果當前下標i能夠到達的最遠位置 i + nums[i] >= lastPos，說明從i出發能夠到達尾元素，更新 lastPos = i，最后判斷 lastPos == 0，
迭代：可以直接用一個變數rightMax來標注最遠能到達的位置，只要i小于等于rightMax，說明i位置是能到達的，不斷更新rightMax，判斷最后rightMax是否大于等于最后一個位置，實質上就是動態規劃的簡潔實作方式，
代碼實作
Java
動態規劃
class Solution {
public boolean canJump(int[] nums) {
int[] dp = new int[nums.length];
dp[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
// 只有當i能到達才更新dp[i]；i如果無法到達，則nums.length-1一定也無法到達
if (i <= dp[i - 1]) {
dp[i] = Math.max(dp[i - 1], i + nums[i]);
// 如果判斷已經可以到達最后一個下標，則提前結束
if (dp[i] >= nums.length - 1) {
return true;
}
} else {
return false;
}
}
return true;
}
}
貪心
class Solution {
public boolean canJump(int[] nums) {
int lastPos = nums.length - 1;
for (int i = nums.length - 2; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
lastPos = i;
}
}
return lastPos == 0;
}
}
回溯法
class Solution {
boolean[] tried;
public boolean canJump(int[] nums) {
tried = new boolean[nums.length];
return jump(nums, 0);
}
private boolean jump(int[] nums, int index) {
if (index >= nums.length - 1) {
return true;
}
for (int i = index + 1; i <= index + nums[index]; i++) {
// 如果下標i已經嘗試過，說明i走不通，無需再嘗試
if (tried[i]) {
continue;
}
if (jump(nums, i)) {
return true;
}
// 每次行不通則將i標記為已嘗試
tried[i] = true;
}
return false;
}
}
JavaScript
迭代
/**
* @param {number[]} nums
* @return {boolean}
*/
var canJump = function (nums) {
let rightMax = 0, i = 0
while (i < nums.length && i <= rightMax) {
rightMax = Math.max(rightMax, nums[i] + i)
i++
}
return rightMax >= nums.length - 1
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/27697.html
標籤：其他