leetcode:45.跳跃游戏 II

亦凉 2022-04-24 13:44 201阅读 0赞

### 题目描述： ###

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

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

你的目标是使用最少的跳跃次数到达数组的最后一个位置。

###### 示例： ######

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

###### 说明： ######

假设你总是可以到达数组的最后一个位置。

##### 题目难度：困难 #####

##### 分析： #####

典型的`贪心算法`，只需要知道当前跳跃的步数，还有跳跃完下一次能跳跃的步数最大值即可，两者相加就是`贪心算法`的最大值。此时也就是每一步应该跳跃的步数。  
代码如下：

class Solution { 
        public int jump(int[] nums) { 
        	// i：数组下标，n：跳跃次数
            int length = nums.length, i = 0, n = 0;
            // 测试用例，如果长度为1直接返回0即可
            if (length == 1) { 
                return 0;
            }
            // 当条件满足时代表暂时还没有跳跃到数组最后
            while (i < length - 1) { 
                int temp = nums[i];
                // 如果数组的值为1，说明只能跳一步，直接判断完即可
                if (temp == 1) { 
                    i++;
                    n++;
                    continue;
                }
                // 如果数组的值大于等于数组剩余的元素个数，说明可以一次性跳完
                if (temp >= length - i - 1) { 
                    return n + 1;
                }
                // max：在1～temp之间跳跃后的最大值，也就是当前范围内数组元素的最大值
                int max = 0;
                // jump：应该跳的步数
                int jump = 0;
                for (int j = 1; j <= temp; j++) { 
                    int temp2 = nums[i + j];
                    // 这里是跳跃后元素的值+跳跃的步数=贪心算法的最大值
                    // 不能光考虑跳跃后元素的值
                    if (temp2 + j >= max) { 
                        max = temp2 + j;
                        jump = j;
                    }
                }
                // 执行跳跃，并且步数+1
                i += jump;
                n++;
            }
            return n;
        }
    }

##### 总结： #####

`贪心算法`是很经典的解决背包类问题的算法，在各大算法书中几乎都有提到，也是需要掌握的算法之一。