LeetCode55 跳跃游戏、LeetCode45跳跃游戏（进阶版）

缺乏、安全感 2021-09-21 06:18 322阅读 0赞

### LeetCode55 跳跃游戏 ###

**【题目】**

给定一个非负整数数组，你最初位于数组的第一个位置。  
数组中的每个元素代表你在该位置可以跳跃的最大长度。  
判断你是否能够到达最后一个位置。

**【样例】**

输入: \[2,3,1,1,4\]  
输出: true  
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

**【思考】**

使用动规，dp\[x\]代表从头到x是否可以达到

**【代码】**

public boolean canJump(int[] nums) { 
            if (nums==null || nums.length==0) return false;
    
            int i,j,len;
            len = nums.length;
            boolean[] dp = new boolean[len];
            dp[0] = true;
            for (i=1; i<len; i++) { 
                if (dp[i-1] && nums[i-1]>0) { 
                    dp[i] = true;
                } else { 
                    for (j=0; j<i; j++) { 
                        if (dp[j] && nums[j]>=(i-j)) { 
                            dp[i] = true;
                            break;
                        }
                    }
                }
            }
    
            return dp[len-1];
        }

### LeetCode45 跳跃游戏 || ###

**【题目】**

给定一个非负整数数组，你最初位于数组的第一个位置。  
数组中的每个元素代表你在该位置可以跳跃的最大长度。  
你的目标是使用最少的跳跃次数到达数组的最后一个位置。

**【样例】**

输入: \[2,3,1,1,4\]  
输出: 2  
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

**【思考】**

使用dp会超时

考虑使用贪心：每次计算一步能够跳跃的范围,每一次都以一个范围作为一步来计算  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]

/** * 这种方式的dp会超时 * */
        public int jump1(int[] nums) { 
            if (nums==null || nums.length==0) return 0;
    
            int i,j,len,l;
            len = nums.length;
            int[] dp = new int[len];
            dp[0] = 0;
            for (i=1; i<len; i++) { 
                l = Integer.MAX_VALUE;
                for (j=0; j<i; j++) { 
                    if (nums[j]>=(i-j) && l>dp[j]) { 
                        l = dp[j];
                    }
                }
                dp[i] = l+1;
            }
    
            return dp[len-1];
        }
    
        /** * 使用贪心算法，每次计算一步能够跳跃的范围 * 每一次都以一个范围作为一步来计算 * */
        public int jump(int[] nums) { 
            if (nums==null || nums.length==0) return 0;
    
            int left,right,max,i,step;
            left = 0;
            right = 1;
            step = 0;
    
            while (right<nums.length) { 
                max = 0;
                for (i=left; i<right; i++) { 
                    if (max < nums[i]+i) max = nums[i]+i;
                }
                left = right;
                right = max+1;
                step ++;
            }
    
            return step;
        }

--------------------

**【Java 面试那点事】**

**这里致力于分享 Java 面试路上的各种知识，无论是技术还是经验，你需要的这里都有！**

**这里可以让你【快速了解 Java 相关知识】，并且【短时间在面试方面有跨越式提升】**

**面试路上，你不孤单！**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70]: /images/20210920/42edf87a7d7647e0bfeeb6d2a3868880.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzOTQ1MjQ2_size_16_color_FFFFFF_t_70 1]: /images/20210920/2a244922773a4dbbb7b04828b0279382.png