什么是贪心? 贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
贪心的套路
贪心算法并没有固定的套路。不好意思,也没有! 靠自己手动模拟,如果模拟可行,就可以试一试贪心策略,如果不可行,可能需要动态规划。那如何验证可不可用贪心算法?最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧。
一般的数学证明有如下两种方法:
1.数学归纳法
2.反证法
面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了。
贪心一般解题步骤,一般分为如下四步:
1.将问题分解为若干个子问题
2.找出适合的贪心策略
3.求解每一个子问题的最优解
4.将局部最优解堆成全局最优解
做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。
贪心没有套路,说白了就是常识性推导加上举反例。贪心的一般解题步骤,大家可以发现这个解题步骤也是比较抽象的,不像是二叉树,回溯算法,给出了那么具体的解题套路和模板。
(题目链接)
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
为了不浪费饼干的尺寸,打算尽量用尺寸最大的饼去给胃口最大的孩子,以此往下推,每一步充分发挥这个当前饼尺寸的作用。
int findContentChildren(vector<int>& g, vector<int>& s) {
std::sort(g.begin(), g.end());
std::sort(s.begin(), s.end());
int index=0; // for person
for(int i=0; i<s.size(); i++){ // for cake
if(index<g.size() && g[index]<=s[i]) index++;
}
return index;
}
for循环可以从饼开始匹配,从人开始匹配,但要主要方向的不同
(题目链接)
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。例如, [1,7,4,9,2,5] 是一个摆动序列,而[1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列。
因此题目要求是 给定一个整数序列,返回作为摆动序列的最长子序列的长度;
这是思路是:局部最优——除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值;整体最优——整个序列有最多的局部峰值,从而达到最长摆动序列。
实际操作上,其实连删除的操作都不用做,因为题目要求的是最长摆动子序列的长度,所以只需要统计数组的峰值数量就可以了(相当于是删除单一坡度上的节点,然后统计长度)
要处理一下三种特殊情况,结合题目要求情况一的结果应该是3;情况二的结果应该是2;情况三的结果应该是2,因为单调种的平坡不能算是峰值。那如何如何消除这些平坡的影响呢?因为摆动是通过prediff
与curdiff
的符号变化来添加峰值计数,我们只要让prediff
在发生摆动时,才修改就行了,对于平坡的情况,pre的符号就维持不变。
int wiggleMaxLength(vector<int>& nums) {
if(nums.size()<=1) return nums.size();
int curdiff = 0;
int prediff = 0;
int res = 1;
for(int i=0; i<nums.size()-1; i++){
curdiff = nums[i+1]-nums[i];
if((prediff<=0 && curdiff>0) || (prediff>=0 && curdiff<0)){
res++;
prediff = curdiff;
}
}
return res;
}
时间复杂度:O(n^2);空间复杂度:O(n)
(题目链接)
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
暴力解法:通过两层for循环,完成整数数组的子集和的统计,最后比较得出最大的值即可。
其时间复杂度:O(n^2);空间复杂度:O(1)
贪心解法:局部最优——最大连续和的,设置另外一个数组存放原本数组上从0开始连续和>0的数值,当连续和<0时,则从下一个数值开始计数。最后得到这个连续
int maxSubArray(vector<int>& nums) {
int res = INT_MIN;
int count = 0;
for(int i=0; i<nums.size(); i++){
count += nums[i];
if(count>res) res = count;
if(count<0) count=0;
}
return res;
}
这里res初始化为INT_MIN
是为了处理当数组首个字母是负数的情况;
(题目链接)
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格:计算你所能获取的最大利润(但注意你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票))。
例如:输入: [7,1,5,3,6,4]:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
思路:1.想要获取利润,至少两天为一个交易单元 2.初始想法是选择一个低价买入,再高价卖出…一直这样循环 3.
int maxProfit(vector<int>& prices) {
int res = 0;
for(int i=1; i<prices.size(); i++){
res += max(prices[i]-prices[i-1], 0);
}
return res;
}
这题也可以使用dp数组-动态规划方法完成
(题目链接)
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。只有一个购买-卖出的周期,也就是一次获取利润的机会。
int maxProfit(vector<int>& prices) {
int res = 0;
int min_pri = INT_MAX;
for(int i=0; i<prices.size(); i++){
min_pri = prices[i]<min_pri? prices[i]:min_pri;
res = res<prices[i]-min_pri? prices[i]-min_pri: res;
}
return res;
}
(题目链接)
给你一个非负整数数组 nums
,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标,如果可以,返回 true
;否则,返回 false
。
bool canJump(vector<int>& nums) {
int cover = 0;
if(nums.size()==1) return true;
for(int i=0; i<=cover; i++){
cover = max(i+nums[i], cover);
if(cover >= nums.size()-1) return true;
}
return false;
}
(题目链接)
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:目标是使用最少的跳跃次数,并返回该次数。
与上一题不同,该题要求最小步数,因此需要设置两个变量存储当前步可覆盖范围,下一步可覆盖范围:循环特点是 没进入一层cover时,会更新precover值,并与之前的precover比较覆盖;当cover=curcover时,步数统计count+1,且将precover值赋给curcover;最后当precover覆盖数组末尾时退出。
int jump(vector<int>& nums) {
if(nums.size()==1) return 0;
// 两者初始化从0出发
int curcover = 0;
int precovner = 0;
int count = 0;
for(int i=0; i<nums.size(); i++){
//实时计算在下一步可到达的范围
precovner = max(i + nums[i], precovner);
if(i==curcover){
count++;
curcover = precovner; //转化为当前步可到达的范围
if(precovner>=nums.size()-1) break;
}
}
return count;
(题目链接)
给你一个整数数组 nums
和一个整数 k
,按以下方法修改该数组:选择某个下标 i 并将 nums[i]
替换为 -nums[i]
。重复这个过程恰好 k
次。可以多次选择同一个下标 i 。以这种方式修改数组后,返回数组 可能的最大和 。
基本思路是1.将数组中的负数尽量反转为正数 2.若剩余数组均为正数,此时所剩k值若为奇数,则选择一个值最小的正数反转为负数, 若剩余k值是偶数,则无影响。
// 加了绝对值排序法
int largestSumAfterKNegations(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end(), cmp);
for(int i=0; i<nums.size(); i++){
if(nums[i]<0 && k>0){
nums[i] *= -1;
k--;
}
}
if(k%2 == 1) nums[nums.size()-1] *= -1;
int res = 0;
for(int n:nums) res += n;
return res;
}
//正常递增序列排序法
int largestSumAfterKNegations(vector<int>& nums, int k) {
std::sort(nums.begin(), nums.end());
int min_abs = 0;
for(int i=0; i<nums.size(); i++){
if(nums[i]<0 && k>0){
nums[i] *= -1;
k--;
}
min_abs = abs(nums[min_abs])<abs(nums[i])? min_abs: i;
}
if(k%2==1) nums[min_abs] *= -1;
int res=0;
for(int n:nums) res += n;
return res;
}
(题目链接)
暴力的方法很明显就是O(n^2)的,遍历每一个加油站为起点的情况,模拟一圈。
贪心算法1:情况一若gas总和小于cost总和,则一定跑不完一圈;情况二,从0开始出发,累计一圈下来,若中途累加值<0,则说明从0出发不可行;情况三,此时京start后移,即start从尾部朝头部移动,若该节点和能使之前中途累加值的负值填平,则可以从该节点出发。
贪心算法2:当局部连续数组和<0时,说明在i步遇到较大的负值,到时总和不满足,此时可以判断从i之前开始一定不可行(理解这个判断:说明从start到i-1步及之前是满足>0约束的,若存在start~i之间的一个值index到i值的区间满足>0,则说明在start到index区间的值<0,这不符合假设。),至少从i+1开始。
// 贪心1:最少满足start延后
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int cursum = 0;
int min = INT_MAX;
for(int i=0; i<gas.size(); i++){
int res = gas[i]-cost[i];
cursum += res;
if(cursum<min){
min = cursum;
}
}
if(cursum<0) return -1;
if(min>=0) return 0;
for(int i=gas.size()-1; i>0; i--){
int res = gas[i]-cost[i];
min += res;
if(min>=0) return i;
}
return -1;
}
// 贪心2:最长局部累加和
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int cursum = 0;
int totalsum = 0;
int start = 0;
for(int i=0; i<gas.size(); i++){
cursum += gas[i] - cost[i];
totalsum += gas[i] - cost[i];
if(cursum<0){
start = i+1;
cursum = 0;
}
}
if (totalsum<0) return -1;
return start;
}
时间复杂度:O(n);空间复杂度:O(1)
(题目链接)
这道题目有点意思 n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求,给这些孩子分发糖果:
1.每个孩子至少分配到 1 个糖果。 2.相邻两个孩子评分更高的孩子会获得更多的糖果。请你给每个孩子分发糖果,计算并返回需要准备的 最少糖果数目 。
确定左孩子比右孩子大的情况一定是从后面往前遍历,否则不能利用右边孩子的candy的比较情况,得到vec1;确定右孩子比左孩子大的情况是从前往后遍历,这样也是未来利用左孩子的candy的比较情况,得到vec2;最后取candy的vector时,取vec1,vec2各个索引位置上candy的max情况——这样即满足了右孩子比左孩子大,左孩子比右孩子大的情况。
int candy(vector<int>& ratings) {
std::vector<int> candyvec(ratings.size(), 1);
for(int i=1; i<ratings.size(); i++){
if(ratings[i]>ratings[i-1]) candyvec[i] = candyvec[i-1]+1;
}
for(int i=ratings.size()-2; i>=0; i--){
if(ratings[i]>ratings[i+1]) candyvec[i] = max(candyvec[i+1]+1, candyvec[i]);
}
int res = 0;
for(int n:candyvec) res += n;
return res;
}