Open sisterAn opened 2 years ago
最近在不间断、碎片的看贪心算法问题,相比回溯、动态规划问题,贪心算法理论最简单,死扣理论解决问题却很难,大部分的贪心问题一眼懵,很难看出是贪心问题,也很难找到解题套路,因此此部分介绍几道典型的贪心问题,并总结一套贪心套路帮助解题
贪心算法,故名思义,总是做出当前的最优选择,即期望通过局部的最优选择获得整体的最优选择。
某种意义上说,贪心算法是很贪婪、很目光短浅的,它不从整体考虑,仅仅只关注当前的最大利益,所以说它做出的选择仅仅是某种意义上的局部最优,但是贪心算法在很多问题上还是能够拿到最优解或较优解,所以它的存在还是有意义的。
在日常生活中,我们使用到贪心算法的时候还是挺多的,例如:从100章面值不等的钞票中,抽出 10 张,怎样才能获得最多的价值?
我们只需要每次都选择剩下的钞票中最大的面值,最后一定拿到的就是最优解,这就是使用的贪心算法,并且最后得到了整体最优解。
往往遇到的问题并不是这么简单,例如:
给定一个长度为偶数的整数数组 arr,只有对 arr 进行重组后可以满足
arr
0 <= i < len(arr) / 2
arr[2 * i + 1] = 2 * arr[2 * i]
true
false
例如:
输入:arr = [4,-2,2,-4] 输出:true 解释:可以用 [-2,-4] 和 [2,4] 这两组组成 [-2,-4,2,4] 或是 [2,4,-2,-4]
解题思路:
[4,-2,2,-4] ,假设正数正向排序、负数逆向排序,得到 [-2,-4,2,4] ,那么遍历数组,每个数要不被之前的数匹配,要不之后存在 2 倍数
[4,-2,2,-4]
[-2,-4,2,4]
2
arr[0]=-2
1/2
也就是从 arr[0] 开始,仅仅只关注当前的 2倍数结果 ,仅仅关注当前局部的最优,通过每一步的最优解,获取全局最优解,这样看就是 贪心算法 问题
arr[0]
以上这样思路,称之为 抽象贪心算法模型
大部分的贪心问题,都很难看出来,我们最重要的是学会如何抽象成贪心算法模型,这步处理好,代码实现很简单
对于本题,我们还需要关注重复数的问题,例如 [2,2,4,4] ,可以使用 Set 去重,Map 记录重复个数,实现如下:
[2,2,4,4]
Set
Map
var canReorderDoubled = function(arr) { if(arr.length < 2) return false // 正数正序,负数逆序 arr.sort((a, b)=>{ if(a<0 && b<0) return b-a return a-b }) // 去重 let nums = [...new Set(arr)], map = new Map() // 记录重复数个数 for(let a of arr) { map.set(a, (map.get(a) || 0)+1) } for(let i=0; i<nums.length; i++) { // 当前数与二倍数差值 let temp = (map.get(nums[i] * 2) || 0)-map.get(nums[i]) if(temp>=0) { // 满足当前二倍数,或已匹配 map.set(nums[i] * 2, temp) // 只关注当前最优,局部最优 } else { // 不满足 return false } } return true };
再看一道:
给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
n
height
i
(i, 0)
(i, height[i])
找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。
x
返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例:
输入:[1,8,6,2,5,4,8,3,7] 输出:49 解释:图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。
首先,两个边构成一个容器,这个容器的容水量由最短边和 x 轴间距决定,如果从 x 轴最大,即 i=0, j=height.length-1 开始选择两个边:
i=0, j=height.length-1
因此,我们只要选择每次的局部最优:短边向内收缩一步,使用 res 更新每次操作后的全局最优,最终拿到整体最优,这就是 贪心算法 问题
res
代码实现:
var maxArea = function(height) { if(height.length <2) return 0 let res = 0, i = 0, j = height.length-1 while(i<j) { res = Math.max(Math.min(height[j],height[i])*(j-i), res) // 收缩 if(height[i]<height[j]) { i++ } else { j-- } } return res };
采用的是双指针解题,贪心算法是实现,双指针是实现手段,像回溯、动态规划都是思想,DFS、BFS是手段,所有的问题都离不开算法思想
相似的有:有效三角形的个数问题
问题给出一组数据,并给出该组数据的条件或环境(限制),以及结果期望,要求判断这组数据是否满足期望,或从这组数据中选择部分数据,能否达到期望结果最优值
根据问题,抽象出符合满足局部最优,且能通过局部的最优选择获得整体的最优选择的贪心算法模型,例如:
贪心算法模型是对当前问题的一种抽象,一种变体,帮助我们解决问题, 不要问如何抽象贪心算法模型,多刷几道,刷着刷着就有感觉了
通过示例判断结果是否是最优解
给定一个非负整数数组 nums ,你最初位于数组的 第一个下标 。
nums
数组中的每个元素代表你在该位置可以跳跃的 最大长度 。
判断你是否能够到达最后一个下标。
输入:nums = [2,3,1,1,4] 输出:true 解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标
第一步 判定是否是贪心问题
给出一组数,限制每个数组代表能跳跃的最大长度,期待能够能够到达最后一个数字位置,贪心算法问题
第二步 抽象贪心算法模型
从下标 i=0 开始,选择当前局部最优,能够达到的最远位置 i+nums[i] ,然后和全局最优 end 对比,更新全局最优,最后拿到整体最优解
i=0
i+nums[i]
end
var canJump = function(nums) { // 全局最优 let end = 0 for(let i=0; i<nums.length; i++) { // 当前位置不可达,超出此前所有最大可达位置 if(end < i) return false // 最大可达位置已经到达甚至超越最后一个下标,返回 true if(end >= nums.length-1) return true // 更新全局最优 end = end > i+nums[i] ? end: i+nums[i] } return true };
第三步 判断贪心解题是否最优
结合示例 [2,3,1,1,4] 验证结果正确
[2,3,1,1,4]
canJump([2,3,1,1,4]) // true
给你一个非负整数数组 nums ,你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
输入: nums = [2,3,1,1,4] 输出: 2 解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置,跳 1 步,然后跳 3 步到达数组的最后一个位置。
给出一组数,限制每个数组代表能跳跃的最大长度,期待从中选择几个数字,能够最快(最少跳跃)到达最后一个数字位置,贪心算法问题
从下标 i=0 开始,选择当前局部最优,能够达到的最远位置 end=i+nums[i] ,那么 i+1、...、end 为下一步跳跃可能的起点
end=i+nums[i]
i+1、...、end
从 i=i+1 继续遍历,选择当前局部最优,能够达到的最远位置 i+nums[i] ,然后和全局最远 maxPos 对比,更新全局最远,直到 i=end ,当前步起点跳跃结束,开启下一步,上一步全局最远 end 和全局最远 maxPos 对比,更新全局最远 end
i=i+1
maxPos
i=end
这里 end 与 maxPos 不同:
图片来自:https://leetcode-cn.com/problems/jump-game-ii/solution/45-by-ikaruga/
通过 end 选择每一轮的局部最优,更新跳跃次数,获取整体最优
var jump = function(nums) { let end = 0, maxPos = 0, count = 0 for(let i=0; i<nums.length-1; i++) { maxPos = maxPos > i+nums[i] ? maxPos : i+nums[i] // 到达 count 轮终点,更新 end 与 count if(i === end) { // 启动下一轮 end = maxPos // 更新跳跃次数 count++ } } return count }
jump([2,3,1,1,4]) // 2
最近在不间断、碎片的看贪心算法问题,相比回溯、动态规划问题,贪心算法理论最简单,死扣理论解决问题却很难,大部分的贪心问题一眼懵,很难看出是贪心问题,也很难找到解题套路,因此此部分介绍几道典型的贪心问题,并总结一套贪心套路帮助解题
贪心算法
算法策略
贪心算法,故名思义,总是做出当前的最优选择,即期望通过局部的最优选择获得整体的最优选择。
某种意义上说,贪心算法是很贪婪、很目光短浅的,它不从整体考虑,仅仅只关注当前的最大利益,所以说它做出的选择仅仅是某种意义上的局部最优,但是贪心算法在很多问题上还是能够拿到最优解或较优解,所以它的存在还是有意义的。
在日常生活中,我们使用到贪心算法的时候还是挺多的,例如:从100章面值不等的钞票中,抽出 10 张,怎样才能获得最多的价值?
我们只需要每次都选择剩下的钞票中最大的面值,最后一定拿到的就是最优解,这就是使用的贪心算法,并且最后得到了整体最优解。
往往遇到的问题并不是这么简单,例如:
二倍数对数组问题
给定一个长度为偶数的整数数组
arr
,只有对arr
进行重组后可以满足0 <= i < len(arr) / 2
,都有arr[2 * i + 1] = 2 * arr[2 * i]
时,返回true
;false
。例如:
解题思路:
[4,-2,2,-4]
,假设正数正向排序、负数逆向排序,得到[-2,-4,2,4]
,那么遍历数组,每个数要不被之前的数匹配,要不之后存在2
倍数arr[0]=-2
只能存在2
倍数,不会存在1/2
的数也就是从
arr[0]
开始,仅仅只关注当前的2
倍数结果 ,仅仅关注当前局部的最优,通过每一步的最优解,获取全局最优解,这样看就是 贪心算法 问题以上这样思路,称之为 抽象贪心算法模型
大部分的贪心问题,都很难看出来,我们最重要的是学会如何抽象成贪心算法模型,这步处理好,代码实现很简单
对于本题,我们还需要关注重复数的问题,例如
[2,2,4,4]
,可以使用Set
去重,Map
记录重复个数,实现如下:再看一道:
盛最多水的容器
给定一个长度为
n
的整数数组height
。有n
条垂线,第i
条线的两个端点是(i, 0)
和(i, height[i])
。找出其中的两条线,使得它们与
x
轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
说明:你不能倾斜容器。
示例:
解题思路:
首先,两个边构成一个容器,这个容器的容水量由最短边和
x
轴间距决定,如果从x
轴最大,即i=0, j=height.length-1
开始选择两个边:x
轴间距决定,短边不变,x
轴间距缩小了,储水量只可能缩小因此,我们只要选择每次的局部最优:短边向内收缩一步,使用
res
更新每次操作后的全局最优,最终拿到整体最优,这就是 贪心算法 问题以上这样思路,称之为 抽象贪心算法模型
代码实现:
采用的是双指针解题,贪心算法是实现,双指针是实现手段,像回溯、动态规划都是思想,DFS、BFS是手段,所有的问题都离不开算法思想
相似的有:有效三角形的个数问题
贪心套路
第一步 判定是否是贪心问题
问题给出一组数据,并给出该组数据的条件或环境(限制),以及结果期望,要求判断这组数据是否满足期望,或从这组数据中选择部分数据,能否达到期望结果最优值
例如:
height
,限制每两个数都可以构成容器,求从这组数据中选择两个数据,达到容器最大值第二步 抽象贪心算法模型
根据问题,抽象出符合满足局部最优,且能通过局部的最优选择获得整体的最优选择的贪心算法模型,例如:
i=0, j=height.length-1
开始选择两个边,每次做出当前的最优选择:每次短边向内收缩一步,更新全局最优,最终拿到整体最优:容器最大值贪心算法模型是对当前问题的一种抽象,一种变体,帮助我们解决问题, 不要问如何抽象贪心算法模型,多刷几道,刷着刷着就有感觉了
第三步 判断贪心解题是否最优
通过示例判断结果是否是最优解
经典案例:跳跃游戏
给定一个非负整数数组
nums
,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的 最大长度 。
判断你是否能够到达最后一个下标。
示例:
第一步 判定是否是贪心问题
给出一组数,限制每个数组代表能跳跃的最大长度,期待能够能够到达最后一个数字位置,贪心算法问题
第二步 抽象贪心算法模型
从下标
i=0
开始,选择当前局部最优,能够达到的最远位置i+nums[i]
,然后和全局最优end
对比,更新全局最优,最后拿到整体最优解第三步 判断贪心解题是否最优
结合示例
[2,3,1,1,4]
验证结果正确经典案例:跳跃游戏||
给你一个非负整数数组
nums
,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。
示例:
第一步 判定是否是贪心问题
给出一组数,限制每个数组代表能跳跃的最大长度,期待从中选择几个数字,能够最快(最少跳跃)到达最后一个数字位置,贪心算法问题
第二步 抽象贪心算法模型
从下标
i=0
开始,选择当前局部最优,能够达到的最远位置end=i+nums[i]
,那么i+1、...、end
为下一步跳跃可能的起点从
i=i+1
继续遍历,选择当前局部最优,能够达到的最远位置i+nums[i]
,然后和全局最远maxPos
对比,更新全局最远,直到i=end
,当前步起点跳跃结束,开启下一步,上一步全局最远end
和全局最远maxPos
对比,更新全局最远end
这里
end
与maxPos
不同:end
为上一步全局最优,上一步跳跃所能达到的最远位置,也是这一步起跳点的最远位置maxPos
为实时的全局最优,当启动新一轮跳跃时,为新一轮跳跃所能达到的最远位置图片来自:https://leetcode-cn.com/problems/jump-game-ii/solution/45-by-ikaruga/
通过
end
选择每一轮的局部最优,更新跳跃次数,获取整体最优第三步 判断贪心解题是否最优
结合示例
[2,3,1,1,4]
验证结果正确