![[算法手记] 贪心 爬楼梯问题](images/news1.jpg)
本文将用于分析博主的算法刷题记录,同时也是为了勉励自己每天刷题保持手感,记录博客这次要介绍的是两道力扣经典贪心算法题一, 跳跃游戏附上题目链接https://leetcode.cn/problems/jump-game/description/1.思路题目很简单,让我们找出能否到达楼梯的最顶部本题我们就使用贪心来解决,关键点在于维护一个可以到达的最远跳跃视野maxLen.maxLen是变化的, 每走到一个位置它都会赋予我们一个新的“最远跳跃视野”。当我们位于i处的台阶上, 台阶上表示的数字代表我们可以跳跃的最远距离,随着我们的跳跃,可能会出现一个问题,当我们所处位置 i maxLen小 表示这个位置是可以到达的,i nums[i]处,当所处位置 i maxLen ,说明当前的脚下这步根本走不到被中间的0卡死了,无法跳跃直接返回false。贪心选择我们每次都更新maxReach Math.max(maxReach, i nums[i])始终保持手里的视野是最远的。如果能把n遍历完,代表可以走完楼梯,返回true2. 代码classSolution{publicbooleancanJump(int[]nums){intnnums.length;int[]dpnewint[n1];intk0;//记录能从起点跳跃到的最远距离for(inti0;in;i){//i k说明永远无法跳跃到末尾maxReach 是单调不减的后续i只会大于k不可达if(ik)returnfalse;kMath.max(k,inums[i]);}returntrue;}}二,跳跃游戏(二)附上题目链接https://leetcode.cn/problems/jump-game-ii/description/1.思路本题和上一题的不同点在于是求出到达楼梯顶的最小跳跃次数对于我们的每次跳跃操作,都会到达一个最终点, 在这个最终点范围内的任何楼梯都能作为起跳点,我们的目的就是在这个范围内找出一个起跳点,让我们能够从这个位置跳跃到达的距离比上一步的最远边界更大在范围内这个起跳点的存在是未知的,可能永远也无法超出我们之前能够到达的最远距离,所以还需要使用贪心来维护一个变量end作为可达最远距离 , maxReach则代表在end范围内寻找一个能跳的更远的跳板这就需要我们使用贪心始终更新maxReach2.代码(贪心)classSolution{publicintjump(int[]nums){intjumps0;// 跳跃次数intend0;// 当前跳跃步数能达到的最远边界intnextMaxReach0;// 在当前边界内下一跳能达到的最远边界// 注意i nums.length - 1不需要遍历最后一个终点for(inti0;inums.length-1;i){// 贪心在当前能走的范围内找出能跳得最远的下一个“跳板”nextMaxReachMath.max(nextMaxReach,inums[i]);// 走到了当前这一步的边界必须强制“跳”一下并切换到新的边界if(iend){jumps;endnextMaxReach;// 这一步跳完最远能到新的边界}}returnjumps;}}除此之外对于该题还有一种思路则是使用动态规划, 毕竟是我最初想到的解法,虽然时间复杂度为O(N^2)我们可以定义一个dp表, dp[i]则表示到达i位置所需要的最小跳跃次数初始状态, dp[0] 0 ,无需跳跃操作当我们到达i位置,此时跳跃范围就变为[ i , i nums[i] ] ,我们可以从最远距离i nums[i] (姑且称为end吧) 从end向前寻找一个跳板,这个跳板有两个要求可以到达,或者超越end必须距离end越远越好,这代表需要跳跃的次数会更少所以我们就可以来在向前寻找最远跳板的过程中来维护dp表, 注意这里dp[i]表示:到达i位置所需要的最小跳跃次数在最初我们把dp表中除了0 位置的所有值初始化为一个非常大的数,表示初始不可到达代码(动态规划)classSolution{publicintjump(int[]nums){intnnums.length;int[]dpnewint[n];//dp[i]:到达i位置所需要的最小跳跃次数Arrays.fill(dp,Integer.MAX_VALUE);dp[0]0;//起点不用跳for(inti1;in;i){//向前推导起跳位置找最小的起跳点for(intj0;ji;j){if(jnums[j]i){//j位置可以通过一次跳跃到达i位置或者比i更远的位置//更新最小值dp[i]Math.min(dp[j]1,dp[i]);}}}returndp[n-1];}}虽然上述 DP 代码能在 LeetCode 上通过但O(n2)O(n^2)O(n2)的时间复杂度在数据量极大时效率较低。如果我们仔细观察这个 DP 数组会发现一个非常神奇的数学性质dpdpdp数组是单调非递减的。以nums [2, 3, 1, 1, 4]为例dp[0]0dp[0] 0dp[0]0从索引 0 最远到索引 2所以dp[1],dp[2]dp[1], dp[2]dp[1],dp[2]都可以由dp[0]1dp[0] 1dp[0]1得到即[0, 1, 1]接下来从索引 1 扩散最远到索引 4所以dp[3],dp[4]dp[3], dp[4]dp[3],dp[4]都可以由dp[1]1dp[1] 1dp[1]1得到即[0, 1, 1, 2, 2]会发现dpdpdp数组的值变成了成块的[0, 1, 1, 2, 2]。既然它是单调的当我们在内层循环中从左往右找第一个能到达iii的jjj时第一个找到的jjj对应的dp[j]dp[j]dp[j]一定是最小的所以我们根本不需要内层循环去遍历所有的jjj只需要用一个指针固定在左边随着iii的右移而缓缓右移。这进一步将时间优化到了O(n)O(n)O(n)其本质逻辑就与维护“当前步数边界”的贪心算法不谋而合了。这种用 DP 先推导出正确性再通过“单调性”优化掉一层循环的思路在解决各种高阶算法题时是非常强大的通用技巧。
[算法手记] 贪心 爬楼梯问题
本文将用于分析博主的算法刷题记录,同时也是为了勉励自己每天刷题保持手感,记录博客这次要介绍的是两道力扣经典贪心算法题一, 跳跃游戏附上题目链接https://leetcode.cn/problems/jump-game/description/1.思路题目很简单,让我们找出能否到达楼梯的最顶部本题我们就使用贪心来解决,关键点在于维护一个可以到达的最远跳跃视野maxLen.maxLen是变化的, 每走到一个位置它都会赋予我们一个新的“最远跳跃视野”。当我们位于i处的台阶上, 台阶上表示的数字代表我们可以跳跃的最远距离,随着我们的跳跃,可能会出现一个问题,当我们所处位置 i maxLen小 表示这个位置是可以到达的,i nums[i]处,当所处位置 i maxLen ,说明当前的脚下这步根本走不到被中间的0卡死了,无法跳跃直接返回false。贪心选择我们每次都更新maxReach Math.max(maxReach, i nums[i])始终保持手里的视野是最远的。如果能把n遍历完,代表可以走完楼梯,返回true2. 代码classSolution{publicbooleancanJump(int[]nums){intnnums.length;int[]dpnewint[n1];intk0;//记录能从起点跳跃到的最远距离for(inti0;in;i){//i k说明永远无法跳跃到末尾maxReach 是单调不减的后续i只会大于k不可达if(ik)returnfalse;kMath.max(k,inums[i]);}returntrue;}}二,跳跃游戏(二)附上题目链接https://leetcode.cn/problems/jump-game-ii/description/1.思路本题和上一题的不同点在于是求出到达楼梯顶的最小跳跃次数对于我们的每次跳跃操作,都会到达一个最终点, 在这个最终点范围内的任何楼梯都能作为起跳点,我们的目的就是在这个范围内找出一个起跳点,让我们能够从这个位置跳跃到达的距离比上一步的最远边界更大在范围内这个起跳点的存在是未知的,可能永远也无法超出我们之前能够到达的最远距离,所以还需要使用贪心来维护一个变量end作为可达最远距离 , maxReach则代表在end范围内寻找一个能跳的更远的跳板这就需要我们使用贪心始终更新maxReach2.代码(贪心)classSolution{publicintjump(int[]nums){intjumps0;// 跳跃次数intend0;// 当前跳跃步数能达到的最远边界intnextMaxReach0;// 在当前边界内下一跳能达到的最远边界// 注意i nums.length - 1不需要遍历最后一个终点for(inti0;inums.length-1;i){// 贪心在当前能走的范围内找出能跳得最远的下一个“跳板”nextMaxReachMath.max(nextMaxReach,inums[i]);// 走到了当前这一步的边界必须强制“跳”一下并切换到新的边界if(iend){jumps;endnextMaxReach;// 这一步跳完最远能到新的边界}}returnjumps;}}除此之外对于该题还有一种思路则是使用动态规划, 毕竟是我最初想到的解法,虽然时间复杂度为O(N^2)我们可以定义一个dp表, dp[i]则表示到达i位置所需要的最小跳跃次数初始状态, dp[0] 0 ,无需跳跃操作当我们到达i位置,此时跳跃范围就变为[ i , i nums[i] ] ,我们可以从最远距离i nums[i] (姑且称为end吧) 从end向前寻找一个跳板,这个跳板有两个要求可以到达,或者超越end必须距离end越远越好,这代表需要跳跃的次数会更少所以我们就可以来在向前寻找最远跳板的过程中来维护dp表, 注意这里dp[i]表示:到达i位置所需要的最小跳跃次数在最初我们把dp表中除了0 位置的所有值初始化为一个非常大的数,表示初始不可到达代码(动态规划)classSolution{publicintjump(int[]nums){intnnums.length;int[]dpnewint[n];//dp[i]:到达i位置所需要的最小跳跃次数Arrays.fill(dp,Integer.MAX_VALUE);dp[0]0;//起点不用跳for(inti1;in;i){//向前推导起跳位置找最小的起跳点for(intj0;ji;j){if(jnums[j]i){//j位置可以通过一次跳跃到达i位置或者比i更远的位置//更新最小值dp[i]Math.min(dp[j]1,dp[i]);}}}returndp[n-1];}}虽然上述 DP 代码能在 LeetCode 上通过但O(n2)O(n^2)O(n2)的时间复杂度在数据量极大时效率较低。如果我们仔细观察这个 DP 数组会发现一个非常神奇的数学性质dpdpdp数组是单调非递减的。以nums [2, 3, 1, 1, 4]为例dp[0]0dp[0] 0dp[0]0从索引 0 最远到索引 2所以dp[1],dp[2]dp[1], dp[2]dp[1],dp[2]都可以由dp[0]1dp[0] 1dp[0]1得到即[0, 1, 1]接下来从索引 1 扩散最远到索引 4所以dp[3],dp[4]dp[3], dp[4]dp[3],dp[4]都可以由dp[1]1dp[1] 1dp[1]1得到即[0, 1, 1, 2, 2]会发现dpdpdp数组的值变成了成块的[0, 1, 1, 2, 2]。既然它是单调的当我们在内层循环中从左往右找第一个能到达iii的jjj时第一个找到的jjj对应的dp[j]dp[j]dp[j]一定是最小的所以我们根本不需要内层循环去遍历所有的jjj只需要用一个指针固定在左边随着iii的右移而缓缓右移。这进一步将时间优化到了O(n)O(n)O(n)其本质逻辑就与维护“当前步数边界”的贪心算法不谋而合了。这种用 DP 先推导出正确性再通过“单调性”优化掉一层循环的思路在解决各种高阶算法题时是非常强大的通用技巧。
