代码随想录算法训练营第三十一天| 理论基础、LeetCode 455.分发饼干、376. 摆动序列、53. 最大子序和

一、理论基础

文章讲解:https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html

1.贪心的定义

        贪心的本质是选择每一阶段的局部最优解,从而达到全局最优解。例如,有一堆钞票,你可以拿走十张,如果想要拿走的金钱价值最大,那么每次都拿剩余钞票中价值最大的一张即可。而另一类问题,满足每个阶段都是局部最优解,但最后不一定是全局最优解。比如有一堆盒子,你有一个背包体积为n,如何把背包尽可能装满,如果还每次选最大的盒子,就不行了,因为可能选体积小的盒子反而能最大程度利用空间(相信大家开学装行李箱的时候都深有体会)。

2.贪心的套路

        贪心并没有固定套路,偏意识流。难点在于如何看出局部最优能够推出全局最优。现在也没有固定的方法能够说明某题就是贪心,纯靠自己手动模拟,如果模拟可行,就可以试一试贪心策略,如果不可行,可能需要动态规划。拿不准的时候可以举反例,如果想不到反例,那么就试一试贪心吧。当然也可以进行严格的数学推理来表明此题就适合贪心,但不是数学专业的人建议不要这么做,因为比较复杂,面试或者比赛的时候并不要求参与者能够当场证明贪心的合理性。因此,贪心说白了就是常识推导+举反例。

3.贪心一般解题步骤

        贪心算法一般分为如下四步:

(1)将问题分解为若干个子问题

(2)找出适合的贪心策略

(3)求解每一个子问题的最优解

(4)将局部最优解堆叠成全局最优解

        但这个四步其实过于理论化了,我们平时在做贪心类的题目 很难去按照这四步去思考。做题的时候,只要想清楚 局部最优 是什么,如果推导出全局最优,就够了。

二、LeetCode 455.分发饼干

题目链接/文章讲解/视频讲解:https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html

状态:已解决

1.思路

        因为是饼干是离散数据,这意味着饼干不可切分,即使一块饼干尺寸大于孩子的胃口,也只能给孩子喂一整块饼干;那么,对于这样的问题,就用最大饼干尽量去喂最大胃口的孩子(或者小饼干喂小胃口的孩子),即贪心策略,相当于最大化利用每块饼干,如果拿大饼干喂小胃口孩子造成的浪费就会很大,因为可能还存在其他较小饼干也能喂饱小孩子,而你用大饼干去喂,其他饼干又较小,那么大胃口的孩子就无法得到满足。

        如图,是大饼干满足大胃口的情况:

如果有一个饼干不满足大饼干喂大胃口,就会出现以下情况,造成部分饼干浪费且减少了满足孩子数。

        明白原理后,思路就很清晰了。我们需要先对饼干和胃口的数组进行排序,排序后,分别从最大值开始,控制饼干和胃口进行对比,如果该饼干大于等于该胃口,饼干和胃口都向前移动一位,如果小于,则只移动胃口,找能被该饼干喂饱的最大胃口。

        注意,遍历顺序是胃口在外,饼干在内。胃口为外循环代表每次无论喂饱成功都会向前移动一位,相当于,饼干是不变量,需要滑动胃口找能被该饼干喂饱的最大胃口,饼干只有在找到能满足的胃口后才往前移。

2.代码实现

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index = s.size()-1;
        int result=0;
        for(int i=g.size()-1;i>=0;i--){
            if(index>=0 && s[index]>=g[i]){
                result++;
                index--;
            }
        }
        return result;
    }
};

三、376.摆动序列 

题目链接/文章讲解/视频讲解:https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html

状态:已解决

1.思路 

        这道题需要画图理解,例如,以示例二来举例:

画图图形后,很容易就看出最大摆动序列的长度是峰值的个数(包括最大和最小)。其中,

局部最优:删除单调坡度上的节点(不包括单调坡度两端的节点),那么这个坡度就可以有两个局部峰值

整体最优:整个序列有最多的局部峰值,从而达到最长摆动序列

局部最优推出全局最优,并且举不出反例,因此可以试试贪心做法。因为题目要求的是最长摆动子序列的长度,所以只需要统计数组的峰值数量就可以了(相当于是删除单一坡度上的节点,然后统计长度)

在计算是否有峰值的时候,大家知道遍历的下标 i ,计算 prediff(nums[i] - nums[i-1]) 和 curdiff(nums[i+1] - nums[i]),如果prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0 此时就有波动就需要统计。

这是我们思考本题的一个大题思路,但本题要考虑三种情况:

  1. 情况一:上下坡中有平坡
  2. 情况二:数组首尾两端
  3. 情况三:单调坡中有平坡
(1)情况一:上下坡中有平坡

        例如,对于数组[1,2,2,2,1],如图

那么这种上下坡包含平坡的数组摇摆序列长度为多少呢?其实为3,整个平坡可以看作一个峰值。删除左边两个或者右边两个2,构造峰值。为了tong'yi

2.代码实现 

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int curdiff = 0;
        int prediff = 0;
        int result = 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)){
                prediff = curdiff;
                result++;
            }
        }
        return result;
    }
};

四、53. 最大子序和

题目链接/文章讲解/视频讲解:https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html

状态:已解决

1.思路 

        这题我会做!这种求连续子序列最大值类型题的本质是:如果前面的序列和对自身有利才连接序列,否则从自身作为起点重新开始选取序列,也就是自己永远不吃亏。题目要求求具有最大和的连续子数组,我们知道,连续子数组的和=前面连续子数组的和+nums[i],那么怎么选取子序列能够使和最大呢?假如当前在nums[i]的位置,如果前面选取的连续子序列的和<0,那么就说明,nums[i]加上前面的连续子序列后只会拉低nums[i]的值,也就是得到相加结果sum<num[i],这时候单独选nums[i]的结果都比已有连续序列的和大,故我们此时不再连上前面的子序列,而是自立山头,从nums[i]开始做新的序列起点;只有在前面连续子序列的和大于0时,代表连上前面的连续子序列对nums[i]有利,得到相加结果sum>num[i],因此,选择连上前面的序列,扩大连续子序列的范围。

        注意,是连续和小于0时才不选择连接,而不是遇到负数就不连。有人可能觉得遇到负数不是会减小sum吗,但是只有sum仍然大于0,我们就可以把前面的增益效果传递到后面的正数部分,使得正数部分加上后大于自身。例如,假如nums[i]<0,但是连续子数组的和=前面连续子数组的和+nums[i]>0,这种情况仍然是可以被保存的,因为加上下一个num[i+1]后,新的sum值仍会大于nums[i+1]的值。举个示例,[4,-1,5],i此时等于1,显然,nums[-1]=-1<0,但是加上前面的序列和为3,3加到5身上为8,大于5本身,故只有连续和小于0时才不被连接。

2.代码实现

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int result=-100000;
        int nowSum = 0;
        for(int i=0;i<nums.size();i++){
            if(nowSum >= 0){
                nowSum += nums[i];//如果前面的和为非负数,那么证明前面的和对我有利,故加之
            }
            else{
                nowSum = nums[i];//如果前面的和为负数,那么前面的和对我不利,不加,
//我自己就比它们的和大了,故作为新起点开始
            }
            result = (result>nowSum)?result:nowSum;
        }
        return result;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519272.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MySQL常见锁探究

MySQL常见锁探究 1. 各种锁类型1.1 全局锁1.2 表级锁1.2.1 表锁1.2.2 元数据锁&#xff08;MDL&#xff09;1.2.3 意向锁1.2.4 AUTO-INC 锁 1.3 行级锁1.3.1 Record Lock1.3.2 Gap Lock1.3.3 Next-Key Lock 2. MySQL是如何加锁的&#xff1f;2.1 什么 SQL 语句会加行级锁&#…

WPS 不登录无法使用基本功能的解决办法

使用wps时&#xff0c;常常有个比较让人烦恼的事&#xff0c;在不登录的情况下&#xff0c;新建或者打开文档时&#xff0c;wps不让你使用其基本的功能&#xff0c;如设置字体等&#xff0c;相关界面变成灰色&#xff0c;这时Wps提示用户登录注册或登录&#xff0c;但我又不想登…

喜讯 ChatGPT 3.5 免登录|免注册就可以使用了

https://chat.openai.com/ 直接访问openai 官网直接使用&#xff0c;当然还是要魔法的&#xff0c;不用再去用别人二次开发的&#xff0c;还有次数限制&#xff0c;还有开会员&#x1f605;才能用的。&#x1f600;试用啦一下&#xff0c;基本秒回答&#xff0c;能力也是在线的…

深入浅出 -- 系统架构之微服务架构常见的六种设计模式

面向服务的架构&#xff08;SOA&#xff09; 面向服务的架构&#xff08;SOA&#xff09;是一种设计方法&#xff0c;也是一个组件模型&#xff0c;它将应用程序的不同功能单元&#xff08;称为服务&#xff09;通过这些服务之间定义良好的接口和契约联系起来。接口是采用中立的…

软件工程导论

软件工程选择题复习笔记 一、软件工程学概述 用户使用不当、硬件可靠性差、对软件的错误认识属于软件危机的表现&#xff0c;不是原因软件危机&#xff0c;1960年以来&#xff0c;软件工程1968提出软件工程着重于建造一个软件系统 八个阶段可以归纳为计划(定义)阶段&#xf…

一次java.lang.NullPointerException的排查之旅

一次java.lang.NullPointerException的排查之旅 问题由来问题分析问题处理 问题由来 最近在项目中遇到了一个比较奇怪的java.lang.NullPointerException&#xff0c;就是说在自己的本地环境中&#xff0c;功能正常&#xff0c;运行无异常。但是测试环境点击同样的功能时却总是…

每日一练 寻找两个正序数组的中间数

题目参上&#xff0c;以下是解题思路&#xff1a; 首先&#xff0c;我们应该想到的一种方法是把两数组合并为一个整体的数组&#xff0c;然后返回其中位数即可。那么我们如何合并两数组呢&#xff1f;我们可以用归并排序&#xff0c;设置上下两指针&#xff0c;不断遍历返回较…

字节新作:图像生成质量超越DiT

&#x1f31f;每日更新最新高质量论文&#xff0c;关注我&#xff0c;时刻关注最新大模型进展。&#x1f31f; &#x1f4cc; 元数据概览&#xff1a; 标题&#xff1a;Visual Autoregressive Modeling: Scalable Image Generation via Next-Scale Prediction作者&#xff1a…

2012年认证杯SPSSPRO杯数学建模C题(第二阶段)碎片化趋势下的奥运会商业模式全过程文档及程序

2012年认证杯SPSSPRO杯数学建模 C题 碎片化趋势下的奥运会商业模式 原题再现&#xff1a; 从 1984 年的美国洛杉矶奥运会开始&#xff0c;奥运会就不在成为一个“非卖品”&#xff0c;它在向观众诠释更高更快更强的体育精神的同时&#xff0c;也在攫取着巨大的商业价值&#…

LeetCode-热题100:21. 合并两个有序链表

题目描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1&#xff1a; 输入&#xff1a; l1 [1,2,4], l2 [1,3,4] 输出&#xff1a; [1,1,2,3,4,4] 示例 2&#xff1a; 输入&#xff1a; l1 [], l2 [] 输出…

什么是ICMP协议,如何防护ICMP攻击

一.什么是ICMP ICMP&#xff08;Internet Control Message Protocol&#xff09;是互联网控制报文协议&#xff0c;是TCP/IP协议族的一个子协议。它主要用于在IP网络中传递控制信息和错误消息&#xff0c;是IP协议的补充。ICMP协议是一种无连接协议&#xff0c;它不需要建立…

如何锁定鼠标光标在水平、垂直或45度对角线模式下移动 - 鼠标水平垂直移动锁定器简易教程

在我们进行精细工作例如如创建图标和图形设计时&#xff0c;通常需要我们对鼠标移动进行精确控制。一旦向左或向右轻微移动&#xff0c;都可能导致设计出错。若出现不必要的错误&#xff0c;我们极有可能不得不重新开始&#xff0c;这会令人感到非常沮丧。这种情况下&#xff0…

NIO基础知识

在学习Netty之前先要学习一下NIO相关的知识&#xff0c;因为Netty是基于NIO搭建的一套网络编程框架。 一. NIO 基础 non-blocking io 非阻塞 IO 1. 三大组件 1.1 Channel & Buffer channel 有一点类似于 stream&#xff0c;它就是读写数据的双向通道&#xff0c;可以从…

SSM实战项目——哈哈音乐(三)文件服务器模块开发

1、创建模块 创建一个子模块&#xff08;hami-fie&#xff09;&#xff0c;里面不写任何代码&#xff0c;专门用于文件上传的服务器 在hami-file的webapp下创建上传文件资源的文件夹&#xff0c;并引入资源&#xff08;图片、音频&#xff09; 2、pom.xml主配置文件中引入文件…

提升提测质量之研测共建

提升提测质量之研测共建 简介 你是否也有同样的困惑&#xff1f;跟进的需求&#xff0c;就在提测前一秒&#xff0c;被告知不能如期提测了&#xff0c;研测计划被打乱&#xff1b;提测的功能&#xff0c;犹如遇到不好的购物体验&#xff0c;缺斤短两&#xff0c;与prd预期不符…

Elasticsearch:我们如何演化处理二进制文档格式

作者&#xff1a;来自 Elastic Sean Story 从二进制文件中提取内容是一个常见的用例。一些 PDF 文件可能非常庞大 — 考虑到几 GB 甚至更多。Elastic 在处理此类文档方面已经取得了长足的进步&#xff0c;今天&#xff0c;我们很高兴地介绍我们的新工具 —— 数据提取服务&…

AopContext.currentProxy() 的代理对象错误(未被更新)问题

背景&#xff1a; 原来在springAOP的用法中&#xff0c;只有代理的类才会被切入&#xff0c;我们在controller层调用service的方法的时候&#xff0c;是可以被切入的&#xff0c;但是如果我们在service层 A方法中&#xff0c;调用B方法&#xff0c;切点切的是B方法&#xff0c;…

猫头虎技术分享 || 断网了,还能ping127.0.0.1吗?

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …

开源大语言模型(LLM)汇总(持续更新中)

随着ChatGPT的火爆&#xff0c;越来越多人希望在本地运行一个大语言模型。为此我维护了这个开源大语言模型汇总&#xff0c;跟踪每天不发的大语言模型和精调语言模型。 我将根据个模型采用的基础大模型进行分类&#xff0c;每个大模型下列出各派生模型。 Alpaca (Stanford) 斯…

Java毕业设计 基于SSM jsp商城系统 美妆系统

Java毕业设计 基于SSM jsp商城系统 美妆系统 SSM jsp 商城系统 美妆系统 功能介绍 首页 分类展示商品 搜索商品 登录 注册 邮箱激活 购物车 结算 支付 我的订单 个人信息设置 后台管理 登录 商品管理 添加修改下架商品 商品类型管理 添加修改删除分类 订单管理 确认发货 取消…