（贪心算法）Java 求解跳跃游戏

短命女 2022-10-21 14:52 145阅读 0赞

### 文章目录 ###

*   *  一、题目
     *  二、贪心分析
     *  三、代码
     *  四、总结

## 一、题目 ##

给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]

## 二、贪心分析 ##

该题的贪心之处在于，每次选取覆盖的最大范围，最后判断最大的范围能否覆盖整个数组

比如2,3,1,1,4，第一步处在2的位置上，可以跳两步，也就是可以跳到 3 位置和 1 位置  
对于3位置的覆盖范围：下标`1 + 可以跳跃的区域 3 = 4` ，等于区间的终点下标 4  
所以可以覆盖成功

具体实现时，关键就是每次在可覆盖的范围内更新最大的覆盖范围

## 三、代码 ##

class Solution { 
        public boolean canJump(int[] nums) { 
            if (nums == null || nums.length == 0 || nums.length == 1) { 
                return true;
            }
            int maxRange = 0;
            for (int i = 0; i < nums.length; i++) { 
                //记录当前值的覆盖范围
                int tempRange = i + nums[i];
                //需要保证当前的i值可以被覆盖到
                if (i<=maxRange){ 
                    //更新最大的覆盖范围
                    maxRange = Math.max(maxRange,tempRange);
                    if (maxRange>=nums.length-1){ 
                        return true;
                    }
                }else { 
                    //如果当前 i 值无法被覆盖到，说明出现断层了，全局的范围肯定也无法覆盖
                    return false;
                }
            }
            return false;
        }
    }

代码精简：

class Solution { 
        public boolean canJump(int[] nums) { 
            if (nums.length == 1) { 
                return true;
            }
            //覆盖范围
            int coverRange = nums[0];
            //在覆盖范围内更新最大的覆盖范围
            for (int i = 0; i <= coverRange; i++) { 
                coverRange = Math.max(coverRange, i + nums[i]);
                if (coverRange >= nums.length - 1) { 
                    return true;
                }
            }
            return false;
        }
    }

## 四、总结 ##

第一反应的代码，更加反应贪心策略，就是每次在可覆盖的范围内，选择新的覆盖区域最大的节点继续跳跃

class Solution { 
        public boolean canJump(int[] nums) { 
            if (nums == null || nums.length == 0 || nums.length == 1) { 
                return true;
            }
            int index = 0;
            while (nums[index] != 0 && nums[index] < nums.length - index - 1) { 
                int tempIndex = index;
                int max = 0;
                //在可覆盖的区域内，每次选择覆盖范围最大的节点继续跳跃
                for (int i = 1; i <= nums[index]; i++) { 
                    if (nums[index + i] + i > max) { 
                        max = nums[index + i] + i;
                        tempIndex = index + i;
                    }
                }
                index = tempIndex;
            }
            return nums[index] == 0 ? false : true;
        }
    }

后续的改进，就是可以直接遍历所有节点，每次更新覆盖的最大区域即可

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmh1YWliZWlhbg_size_16_color_FFFFFF_t_70]: /images/20221021/872452986a4f4f07bf844238ae581ed6.png