2.贪心算法.基础

admin2024-07-09  12

2.贪心算法.基础

  • 基础知识
  • 题目
    • 1.分发饼干
    • 2.摆动序列
    • 3.最大子序和
    • 4.买股票的最佳时机2
    • 4.2.买股票的最佳时机
    • 5.跳跃游戏
    • 5.1.跳跃游戏2
    • 6.K次取反后最大化的数组和
    • 7.加油站
    • 8.分发糖果

基础知识

什么是贪心? 贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
贪心的套路
贪心算法并没有固定的套路。不好意思,也没有! 靠自己手动模拟,如果模拟可行,就可以试一试贪心策略,如果不可行,可能需要动态规划。那如何验证可不可用贪心算法?最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧
一般的数学证明有如下两种方法:
1.数学归纳法
2.反证法

面试中基本不会让面试者现场证明贪心的合理性,代码写出来跑过测试用例即可,或者自己能自圆其说理由就行了。
贪心一般解题步骤,一般分为如下四步:
1.将问题分解为若干个子问题
2.找出适合的贪心策略
3.求解每一个子问题的最优解
4.将局部最优解堆成全局最优解
做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,其实就够了。

贪心没有套路,说白了就是常识性推导加上举反例。贪心的一般解题步骤,大家可以发现这个解题步骤也是比较抽象的,不像是二叉树,回溯算法,给出了那么具体的解题套路和模板。

题目

1.分发饼干

(题目链接)
对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
2.贪心算法.基础,在这里插入图片描述,第1张
为了不浪费饼干的尺寸,打算尽量用尺寸最大的饼去给胃口最大的孩子,以此往下推,每一步充分发挥这个当前饼尺寸的作用。

    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循环可以从饼开始匹配,从人开始匹配,但要主要方向的不同


2.摆动序列

(题目链接)
如果连续数字之间的差严格地在正数和负数之间交替,则数字序列称为摆动序列。第一个差(如果存在的话)可能是正数或负数。少于两个元素的序列也是摆动序列。例如, [1,7,4,9,2,5] 是一个摆动序列,而[1,4,7,2,5] 和 [1,7,4,5,5] 不是摆动序列。
因此题目要求是 给定一个整数序列,返回作为摆动序列的最长子序列的长度
这是思路是:局部最优——除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值;整体最优——整个序列有最多的局部峰值,从而达到最长摆动序列。
实际操作上,其实连删除的操作都不用做,因为题目要求的是最长摆动子序列的长度,所以只需要统计数组的峰值数量就可以了(相当于是删除单一坡度上的节点,然后统计长度)
2.贪心算法.基础,在这里插入图片描述,第2张
要处理一下三种特殊情况,结合题目要求情况一的结果应该是3;情况二的结果应该是2;情况三的结果应该是2,因为单调种的平坡不能算是峰值。那如何如何消除这些平坡的影响呢?因为摆动是通过prediffcurdiff的符号变化来添加峰值计数,我们只要让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)


3.最大子序和

(题目链接)
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和
暴力解法:通过两层for循环,完成整数数组的子集和的统计,最后比较得出最大的值即可。
其时间复杂度:O(n^2);空间复杂度:O(1)

贪心解法:局部最优——最大连续和的,设置另外一个数组存放原本数组上从0开始连续和>0的数值,当连续和<0时,则从下一个数值开始计数。最后得到这个连续
2.贪心算法.基础,在这里插入图片描述,第3张

    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是为了处理当数组首个字母是负数的情况;


4.买股票的最佳时机2

(题目链接)
给定一个数组,它的第 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数组-动态规划方法完成

4.2.买股票的最佳时机

(题目链接)
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。只有一个购买-卖出的周期,也就是一次获取利润的机会。

    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;
    }

5.跳跃游戏

(题目链接)
给你一个非负整数数组 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;
    }

5.1.跳跃游戏2

(题目链接)
给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:目标是使用最少的跳跃次数,并返回该次数。
2.贪心算法.基础,在这里插入图片描述,第4张
与上一题不同,该题要求最小步数,因此需要设置两个变量存储当前步可覆盖范围,下一步可覆盖范围:循环特点是 没进入一层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;

6.K次取反后最大化的数组和

(题目链接)
给你一个整数数组 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;
    }

7.加油站

(题目链接)
2.贪心算法.基础,在这里插入图片描述,第5张
暴力的方法很明显就是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)


8.分发糖果

(题目链接)
这道题目有点意思 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;
    }
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!