luckydog

V1

2022/03/10阅读:48主题:默认主题

Code 55

数组

Code 55
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标。 数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/jump-game 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


题解

代码

  • 方法一
int maxLen = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= maxLen){
                maxLen = Math.max(maxLen, i + nums[i]);
                if (maxLen >= nums.length - 1){
                    return true;
                }
            }
        }
        
        return false;
    }
  • 方法二
int len = nums.length;
        boolean[] dp = new boolean[len];
        for (boolean b : dp) {
            b= false;
        }
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            if (dp[i] && nums[i] != 0){
                for (int j = 1; j <= nums[i]; j++) {
                    if (j + i <= len -1){
                        dp[i + j] = true;
                    }
                }
            }
            if (dp[len - 1]){
                return dp[len - 1];
            }
        }
        return dp[len - 1];

分析

  • 方法一 官方解法
    遍历一遍数组,使用一个flag表示遍历到次可以走到的最远位置maxLen,如果maxLen > n (数组最后一个位置),表示可以到达。
  • 方法二 自己解法
    略显笨拙,使用O(n)辅助空间表示该位置是否可以到达。

分类:

后端

标签:

Java

作者介绍

luckydog
V1