DAY27|贪心算法Part01|LeetCode:455.分发饼干、376. 摆动序列、53. 最大子序和

ops/2024/11/19 1:15:34/

算法>贪心算法

        贪心的本质是选择每一阶段的局部最优,从而达到全局最优

        算法>贪心算法并没有固定的套路,最难想的就在于如何通过局部最优去推出全局最优。在做一个题目的时候,靠自己手动模拟,如果模拟可行,就可以试一试贪心策略,如果不可行,可能需要动态规划。

        那么什么时候可以使用算法>贪心算法呢?刷题或者面试的时候,手动模拟一下感觉可以局部最优推出整体最优,而且想不到反例,那么就试一试贪心

LeetCode:455.分发饼干

力扣代码链接

文字讲解:LeetCode:455.分发饼干

视频讲解:算法>贪心算法,你想先喂哪个小孩?

基本思路

        要求每个孩子最多只能喂一块饼干,那么就不能造成饼干尺寸的浪费,做到物尽其用,大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子,那么就应该优先满足胃口大的。这里的局部最优就是大饼干喂给胃口大的,充分利用饼干尺寸喂饱一个,全局最优就是喂饱尽可能多的小孩

        此时我们就可以利用贪心策略,先对饼干尺寸和小孩的胃口值进行排序,从后向前遍历小孩数组,然后用大饼干去投喂胃口大的小孩,并统计出能满足的小孩的数量。

        注意:上面的方法中,我们选择先遍历小孩数组,然后再去遍历饼干,为什么我们没有先遍历饼干,然后在遍历小孩呢?看了下面的图,其实就不难看出,由于index指向胃口值,只有满足条件才会移动,如果我们先遍历饼干,那么就会因为一直无法找到能满足胃口值为10的小孩而导致所有的饼干都无法匹配。

C++代码

// 版本一
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;}
};

LeetCode:376. 摆动序列

力扣代码链接

文字讲解:LeetCode:376. 摆动序列

视频讲解:算法>贪心算法,寻找摆动有细节!

基本思路

        本题要求通过从原始序列中删除一些(也可以不删除)元素来获得子序列,剩下的元素保持其原始顺序。以示例2为例:

        实际操作上,其实连删除的操作都不用做,因为题目要求的是最长摆动子序列的长度,所以只需要统计数组的峰值数量就可以了(相当于是删除单一坡度上的节点,然后统计长度)。这就是贪心所贪的地方,让峰值尽可能的保持峰值,然后删除单一坡度上的节点。

        这里我们可以定义prediff和curdiff,用来计算当前下标i所对应的元素的前后波动情况。这个题目最难想清楚的就是所出现的三种情况:

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

情况一:上下坡中有平坡

        例如 [1,2,2,2,1]这样的数组,它的摇摆序列长度是多少呢? 其实是长度是 3,也就是我们在删除的时候 要不删除左面的三个 2,要不就删除右边的三个 2。为了统一规则我们可以删除左边三个2,那么 当 prediff = 0 && curdiff < 0 也要记录一个峰值。

        所以我们记录峰值的条件应该是: (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)。

情况二:数组首尾两端

        题目中说了,如果只有两个不同的元素,那摆动序列也是 2。因为我们在计算 prediff(nums[i] - nums[i-1]) 和 curdiff(nums[i+1] - nums[i])的时候,至少需要三个数字才能计算,而数组只有两个数字。对于数组[2,5]来讲,假设数组为[2, 5, 5]。这样就有了prediff = 0,curdiff=3。

        针对上述情况可以设置result 初始为 1(默认最右面有一个峰值),此时 curDiff > 0 && preDiff <= 0,那么 result++(计算了左面的峰值),最后得到的 result 就是 2(峰值个数为 2 即摆动序列长度为 2)。

// 版本一
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size();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)) {result++;}preDiff = curDiff;}return result;}
};

        如果只考虑这两种情况,那么提交会提示报错,表示我们还有情况没有考虑到。

情况三:单调坡度有平坡

        这种情况很容易被忽略,如果在一个单调坡度上有平坡,例如[1,2,2,2,3,4],如图:

        图中,我们可以看出,版本一的代码在三个地方记录峰值,但其实结果因为是 2,因为 单调中的平坡 不能算峰值(即摆动)。之所以版本一会出问题,是因为我们实时更新了 prediff。那么我们应该什么时候更新 prediff 呢?我们只需要在这个坡度摆动变化的时候,更新 prediff 就行,这样 prediff 在单调区间有平坡的时候就不会发生变化,造成我们的误判。

C++代码

// 版本二
class Solution {
public:int wiggleMaxLength(vector<int>& nums) {if (nums.size() <= 1) return nums.size();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)) {result++;preDiff = curDiff; // 注意这里,只在摆动变化的时候更新prediff}}return result;}
};

LeetCode:53. 最大子序和

力扣代码链接

文字讲解:LeetCode:53. 最大子序和

视频讲解:算法>贪心算法的巧妙需要慢慢体会!

基本思路

        很容易想到的是暴力解法,使用两层for循环,第一层设置起始位置,而第二层可以遍历数组,寻求最大和。

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) { // 设置起始位置count = 0;for (int j = i; j < nums.size(); j++) { // 每次从起始位置i开始遍历寻找最大值count += nums[j];result = count > result ? count : result;}}return result;}
};

        但是这种方法所耗费的时间很多,很容易会超时。

而我们使用算法>贪心算法,可以先设置一个结果值,result = INT_MIN,然后开始遍历整个数组,很容易想到的是如果一个数组的存在正数,那么最大和数组的起始位置一定正数,那么我们遍历 nums,从头开始用 count 累积,如果 count 一旦加上 nums[i]变为负数,那么就应该从 nums[i+1]开始从 0 累积 count 了,因为已经变为负数的 count,只会拖累总和。

        并且一旦count大于当前记录的最大值,我们就及时记录下来。

if (count > result) result = count;

C++代码

class Solution {
public:int maxSubArray(vector<int>& nums) {int result = INT32_MIN;int count = 0;for (int i = 0; i < nums.size(); i++) {count += nums[i];if (count > result) { // 取区间累计的最大值(相当于不断确定最大子序终止位置)result = count;}if (count <= 0) count = 0; // 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和}return result;}
};

http://www.ppmy.cn/ops/134824.html

相关文章

源码解析-Spring Eureka(更新ing)

源码解析-Spring Eureka 文章目录 源码解析-Spring Eureka前言一、从Spring.factory和注解开始二、重要的一步EurekaServerInitializerConfiguration三、初始化了什么&#xff1f;自动保护 四, 重新回到EurekaServerAutoConfiguration关于unavailable-replicas 前言 无 一、从…

去地面算法——depth_clustering算法调试(1)

1 源码下载 论文&#xff1a; 《2016-Fast Range Image-Based Segmentation of Sparse 3D Laser Scans for Online Operation》 《2017-Efficient Online Segmentation for Sparse 3D Laser Scans》 代码&#xff1a;git链接 2 问题记录 2.1 无法找到qt问题 问题截图&…

Python 小高考篇(7)常用模板

目录 斐波那契数列常规算法递推法递归法 判断质数常规算法埃氏筛法 最大公因数常规算法辗转相除法 三条边求三角形面积海伦公式 阶乘常规算法递归法 结尾 本文由Jzwalliser原创&#xff0c;发布在CSDN平台上&#xff0c;遵循CC 4.0 BY-SA协议。 因此&#xff0c;若需转载/引用本…

Flutter 新建工程一直等待 解决办法

Flutter报错之Waiting for another flutter command to release the startup lock解决方案 open ~/.bash_profile 此时进入编辑模式&#xff0c;添加如下代理&#xff0c;最后一个是你自己安装的flutter路径 export PUB_HOSTED_URLhttps://pub.flutter-io.cn //国内用户需要…

解析“ChatGPT网络错误”:从网络专线到IP地址的根源与解决方案

在日常使用 ChatGPT 或其他在线服务时&#xff0c;偶尔会遇到“网络错误”的提示&#xff0c;尤其是在请求响应时间较长或出现连接中断的情况下。这种错误常常让用户感到困扰&#xff0c;但实际上&#xff0c;网络错误的发生并不总是因为服务端出现问题&#xff0c;很多时候&am…

【C++ 算法进阶】算法提升十六

目录 背包问题变种 &#xff08;动态规划&#xff09;题目题目分析 连续可组成数字题目题目分析 min-patches题目 最小补丁问题题目分析代码 逆序对个数 &#xff08;归并排序&#xff09;题目题目分析 约瑟夫环问题 &#xff08;公式&#xff09;题目题目分析 背包问题变种 &a…

从浏览器地址栏输入url到显示页面的步骤

1. 输入url&#xff0c;并点击搜索2. 从浏览器获取缓存&#xff08;从浏览器http的header中读取&#xff0c;缓解服务器压力&#xff0c;提高页面加载效率&#xff09; 灰色的200代表是获取的浏览器缓存的数据&#xff0c;黑色的200是后端返回的数据协商缓存&#xff08;优先级…

【原创】java+ssm+mysql美食论坛网系统设计与实现

个人主页&#xff1a;程序猿小小杨 个人简介&#xff1a;从事开发多年&#xff0c;Java、Php、Python、前端开发均有涉猎 博客内容&#xff1a;Java项目实战、项目演示、技术分享 文末有作者名片&#xff0c;希望和大家一起共同进步&#xff0c;你只管努力&#xff0c;剩下的交…