Jump Game II (H)
題目
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.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: 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.
題意
給定一個陣列，每個數字元素代表以當前下標為起點，能夠向右走的步數，回傳該陣列能從第一個元素開始走到最后一個元素所需要的最小步數，
思路
在 55. Jump Game 基礎上，對方法做出修改：
第一種方法代碼結合圖更清晰：
貪心：變數lastPos初值為nums.length - 1，從右向左遍歷，對于每一個lastPos，找到它左側最左邊一個滿足 left + nums[left] >= lastPos 的值left，步數加1，并更新 lastPos = left，重復上述步驟直到 lastPost = 0，
代碼實作
Java
迭代
class Solution {
public int jump(int[] nums) {
int count = 0;
int preLast = 0; // 上一步最遠能到達的位置
int last = 0; // 下一步最遠能到達的位置
for (int i = 0; i < nums.length; i++) {
// 當上一步能到達的位置全部走完后，要到更遠的位置需要多邁一步
if (i > preLast) {
count++;
preLast = last;
}
last = Math.max(last, i + nums[i]); // 更新下一步最遠能到達的位置
}
return count;
}
}
貪心
class Solution {
public int jump(int[] nums) {
int count = 0;
int lastPos = nums.length - 1;
int left = lastPos;
while (lastPos != 0) {
// 每次找到最左邊一個能夠到達lastPos的位置
for (int i = lastPos - 1; i >= 0; i--) {
if (i + nums[i] >= lastPos) {
left = i;
}
}
count++;
lastPos = left;
}
return count;
}
}
JavaScript
迭代
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function (nums) {
let step = 0
let start = 0
let end = 0
while (end < nums.length - 1) {
step++
let max = end
for (let i = start; i <= end; i++) {
max = Math.min(Math.max(max, nums[i] + i), nums.length - 1)
}
start = end + 1
end = max
}
return step
}
貪心
/**
* @param {number[]} nums
* @return {number}
*/
var jump = function (nums) {
let step = 0
let pos = nums.length - 1
while (pos !== 0) {
let i = 0
while (nums[i] + i < pos) {
i++
}
pos = i
step++
}
return step
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/36595.html
標籤：其他