LeetCode刷题实战55：跳跃游戏
共 1966字，需浏览 4分钟
·
2020-10-03 07:29
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
今天和大家聊的问题叫做 跳跃游戏，我们先来看题面：
https://leetcode-cn.com/problems/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.
题意
样例
示例 1:
输入: [2,3,1,1,4]
输出:
true
解释: 我们可以先跳
1 步，从位置
0 到达 位置
1, 然后再从位置
1 跳
3 步到达最后一个位置。
示例 2:
输入: [3,2,1,0,4]
输出:
false
解释: 无论怎样，你总会到达索引为
3 的位置。但该位置的最大跳跃长度是
0 ， 所以你永远不可能到达最后一个位置。
解题
public class Solution {
int steps;
public int jump(int[] nums) {
int n = nums.length;
steps = n -
1;
jump(nums,
0,
0);
return steps;
}
private void jump(int[] nums, int index, int tempSteps) {
if(index >= nums.length -
1) {
if(index == nums.length -
1) {
steps = Math.min(steps, tempSteps);
}
return;
}
for (int i =
1; i <= nums[index]; i++) {
jump(nums, index + i, tempSteps +
1);
}
}
}
public class Solution {
public int jump(int[] nums) {
int n = nums.length;
if(n == 1) {
return 0;
}
int[][] steps = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
steps[i][j] = n - 1;
}
}
for (int i = 0; i < n; i++) {
steps[i][i] = 0;
}
for (int i = 0; i >= 1 - n; i--) {
for (int j = 0; j < n + i; j++) {
if(nums[j] + j >= j - i) {
steps[j][j - i] = 1;
}else {
for (int k = 1; k <= nums[j]; k++) {
steps[j][j - i] = Math.min(steps[j][j - i], 1 + steps[j + k][j - i]);
}
}
}
}
return steps[0][n - 1];
}
}
public class Solution {
public int jump(int[] nums) {
int n = nums.length;
int steps = 0;
int index = 0;
while(index < n - 1) {
steps++;
int[] lengths = new int[nums[index]];
if(index + nums[index] >= n - 1) {
break;
}
for (int i = index + 1; i <= index + nums[index]; i++) {
lengths[i - index - 1] = i + nums[i];
}
int max = 0;
for (int i = 0; i < lengths.length; i++) {
if(lengths[i] > lengths[max]) {
max = i;
}
}
index = max + index + 1;
}
return steps;
}
}
上期推文：