leetcode力扣_贪心思想

455.分发饼干(easy-自己想得出来并写好)

        假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i,都有一个胃口值 g[i],这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j,都有一个尺寸 s[j] 。如果 s[j] >= g[i],我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。

示例 1:输入: g = [1,2,3], s = [1,1] 输出: 1

解释: 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。 虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1

思路:先将饼干大小和孩子的胃口大小都排序,再一一对比...需要注意的是for中的循环条件是饼干不是孩子,孩子加一的条件是前一个孩子得到满足之后,孩子的下标i才会加一!并且一旦这个孩子得到了满足,那么饼干的下标j和孩子的下标i均要直接加1进入下一次判断。所以才有了break语句!

代码如下:

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {int g_len = g.size() ;int s_len = s.size() ;int i = 0 , j = 0 ,cnt = 0;sort(g.begin(),g.end());sort(s.begin(),s.end());for(j ;j<s_len ;j++){//当饼干满足孩子后,孩子才会加一while((i<g_len) && (s[j]>=g[i])){i++;cnt++;break ;//保证一块饼干只给一个孩子}}return cnt ;}
};

435.无重叠区间(hard-自己没什么思路,写不了一点)

        给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后,剩下的区间没有重叠。

示例 2:

输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。

示例 3:

输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间,因为它们已经是无重叠的了。

思路:自己想了一下大概只能想到需要排序,因为这是一个区间,区间怎么排序呢,按照边界排序的话,排好了之后呢?又要怎么做呢?后面就不是很明了了。看了一下官方思路结合下面万能网友的评论大概理清楚了(直接贴一下评论区的某位网友回答,感觉比官方的更容易明白)

  1. 关于解法二贪心算法的合理性,这里作一下补充。其实这里的难点在于理解“为什么是按照右端点排序而不是左端点排序”。
  2. 官解里对这个描述的非常清楚了,这个题其实是预定会议的一个问题,给你若干时间的会议,然后去预定会议,那么能够预定的最大的会议数量是多少?核心在于我们要找到最大不重叠区间的个数。 如果我们把本题的区间看成是会议,那么按照右端点排序,我们一定能够找到一个最先结束的会议,而这个会议一定是我们需要添加到最终结果的的首个会议。(这个不难贪心得到,因为这样能够给后面预留的时间更长)。
  3. 这里补充一下为什么不能按照区间左端点排序。同样地,我们把本题的区间看成是会议,如果“按照左端点排序,我们一定能够找到一个最先开始的会议”,但是最先开始的会议,不一定最先结束。举个例子:

        理清楚了算法的思路再进一步完成代码的编写,还是不太会,这个sort函数的用法,搜了一下感觉搜出来的都不太一样,有点迷惑,反正先整一份正确答案先。

        这种情况是使用自定义比较函数对区间进行排序,然后自定义的比较函数cmp排序准则是,按照区间右端点的升序(a[1] < b[1])进行排序。因为题目中明确说了区间是一个长度为2的数组,所以索引只有0和1,索引0指示左端点,索引1指示右端点。======== 这样排序之后就可以按照上面的思路就行进一步操作了,排序后的第一个区间肯定是需要保留的,遍历后面的区间,留下与前面区间没有重合的即可。下面的代码定义的初始右端点是INT_MIN而不是第一个区间的右端点,道理是一样的。

class Solution {
public://std::sort 期望一个静态函数或一个函数对象//故作为“自定义比较函数”应该定义为static类型//根据题目,intervals是长度为2的数组,故索引只有0和1static bool cmp(vector<int> &a, vector<int> &b){return a[1] < b[1] ;}//vector<vector<int>>& intervals表明intervals是一个二维整数向量int eraseOverlapIntervals(vector<vector<int>>& intervals) {int cnt = intervals.size() ;sort(intervals.begin(), intervals.end(), cmp) ;//使用 INT_MIN 宏来表示最小的 32 位整数值int right = INT_MIN;for(auto i :intervals){//比较新intervals的左端点与当前intervals的右端点)(right)//若左端点i[0]大于等于right,则新的intervals就不需要删除,同时更新right值if(i[0]>=right){right = i[1] ;cnt--;}}return cnt ;}};

        看了一下另外的解答方法:这里使用的是sort函数的默认排序方法,对于一维数组来说就是把数据按照升序排列好,但是对于区间来说,sort方法的默认排序是按照每个区间的第一个元素(起始位置)进行升序排序,如果起始位置的值是一样的,那么就按照第二个位置(结束位置)进行升序排序。

        假设输入的二维数组(几个区间)为:intervals = {{1, 3}, {2, 2}, {3, 4}, {1, 2}},那么直接使用下面的sort函数进行排序,排列后的结果是intervals={{1, 2}, {1, 3} ,{2, 2}, {3, 4} }。

        使用sort函数直接排序之后的进一步处理,没有第一种方法那么清晰明了,其实思路最后还是一样,都是需要不断更新区间的右端点,只是上一个右端点是按照升序拍好的,只需要看后一个区间和前一个有无重合就可以,现在这个需要自己来判断并更新右端点的值【因为排序可能会出现右端点的顺序是上面2324这样交错的】,需要理解一下,大概讲讲,意会一下:比如说你使用sort函数排序后得到了这样一组排序好的区间intervals={[1,5],[1,6],[2,3],[3,6],[4,7],[7,8]},按照代码,将排序后的第一个区间的右端点初始化为最小右端点,也就是right=5,然后从第二个区间开始遍历并更新right的值:

i=1时:intervals[1][0]=1 < right=5,表明第二个区间是和第一个区间有重合的,有重合就需要删除区间,所以cnt++,cnt=1,那删除哪个区间呢,根据上面的思想,需要删除右端点大的,保留右端点小的区间,所以就有了这句”right = min(right, intervals[i][1]);“此时right=5;

i=2时:intervals[2][0]=2 < right=5,表明第三个区间是和第二个区间有重合的,有重合就需要删除区间,所以cnt++,cnt=2,那删除哪个区间呢,根据上面的思想,需要删除右端点大的,保留右端点小的区间,所以此时right=3;

i=3时:intervals[3][0]=3 = right=3,表明第四个区间是和第三个区间是没有重合的,没有重合就要保留,就执行else中的语句,更新右端点的值,right=6,此时cnt还是等于2;

后面同理,不再赘述。最后的结果应该是,保留的区间是{[2,3],[3,6],[7,8]},cnt=3。画一个上面的那种线段区间图可以看得更清楚。

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int cnt = 0;//这里排序默认是按照每个区间的第一个元素(起始位置)进行升序排序//如果起始位置相同,则按第二个元素(结束位置)进行升序排序。sort(intervals.begin(), intervals.end()) ;//将排序后的第一个区间右端点初始化为最小的右端点int right = intervals[0][1]; for (int i = 1; i < intervals.size(); i++) {//判断当前区间的左端点是否小于上一个区间的右端点//若小于 则需要删除,cnt++,同时更新if (intervals[i][0] < right) {cnt++;right = min(right, intervals[i][1]);} else {right = intervals[i][1];}}return cnt ;}
};

⭐关于sort函数:

  std::sort 是 C++ 标准库中的一个函数,用于对指定范围内的元素进行排序。可以通过多种方式使用 std::sort,例如按照默认顺序排序,或者使用自定义的比较函数来排序。下面是几个使用示例:

① 按照默认(升序)顺序排序,该代码的输出是:1 2 3 5 7 8

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> nums = {5, 3, 8, 1, 2, 7};std::sort(nums.begin(), nums.end());for(int num : nums) {std::cout << num << " ";}return 0;
}

② 按自定义顺序排序(降序),改代码的输出是:8 7 5 3 2 1

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> nums = {5, 3, 8, 1, 2, 7};std::sort(nums.begin(), nums.end(), std::greater<int>());for(int num : nums) {std::cout << num << " ";}return 0;
}

③ 使用自定义比较函数排序,该代码的输出是:8 7 5 3 2 1

⭐ 关于这里为什么customCompare函数又不需要定义成静态的,不是很明白,GPT又说“std::sort 函数并不要求传入的自定义比较函数必须是静态函数”可是第一版本的代码中,如果不降传入的cmp函数定义成静态的话运行是会报错的

  个人猜测,第一版代码中,cmp函数是定义在类中的,然而这里是一个普通全局函数,先这样记一下吧。

#include <iostream>
#include <vector>
#include <algorithm>bool customCompare(int a, int b) {return a > b; // 降序排序
}int main() {std::vector<int> nums = {5, 3, 8, 1, 2, 7};std::sort(nums.begin(), nums.end(), customCompare);for(int num : nums) {std::cout << num << " ";}return 0;
}

④ 使用 Lambda 表达式排序,该代码的输出是:8 7 5 3 2 1

#include <iostream>
#include <vector>
#include <algorithm>int main() {std::vector<int> nums = {5, 3, 8, 1, 2, 7};std::sort(nums.begin(), nums.end(), [](int a, int b) {return a > b; // 降序排序});for(int num : nums) {std::cout << num << " ";}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

无人机便携式侦测干扰设备(定全向)技术详解

无人机便携式侦测干扰设备&#xff08;定全向&#xff09;是一种专门针对无人机进行侦测和干扰的设备。它具备定向和全向两种工作模式&#xff0c;能够覆盖较宽的频率范围&#xff0c;有效侦测并干扰无人机与遥控器之间的通信信号&#xff0c;从而达到控制或驱离无人机的目的。…

小酌消烦暑|人间正清欢

小暑是二十四节气之第十一个节气。暑&#xff0c;是炎热的意思&#xff0c;小暑为小热&#xff0c;还不十分热。小暑虽不是一年中最炎热的时节&#xff0c;但紧接着就是一年中最热的节气大暑&#xff0c;民间有"小暑大暑&#xff0c;上蒸下煮"之说。中国多地自小暑起…

Qt 基础组件速学 鼠标和键盘事件

学习目标&#xff1a; 鼠标事件和键盘事件应用 前置环境 运行环境:qt creator 4.12 学习内容和效果演示&#xff1a; 1.鼠标事件 根据鼠标的坐标位置&#xff0c;做出对应的事件。 2.键盘事件 根据键盘的输入做出对应操作 详细主要代码 1.鼠标事件 #include "main…

MySQL 8.0新特性INTERSECT和EXCEPT用于集合运算

MySQL8.0.31 新版本的推出&#xff0c;MySQL增加了对SQL标准INTERSECT和EXCEPT运算符的支持。 1、INTERSECT INTERSECT输出多个SELECT语句查询结果中的共有行。INTERSECT运算符是ANSI/ISO SQL标准的一部分(ISO/IEC 9075-2:2016(E))。 我们运行两个查询&#xff0c;第一个会列…

windows启动Docker闪退Docker desktop stopped

Windows启动Docker闪退-Docker desktop stopped 电脑上很早就安装有Docker了&#xff0c;但是有一段时间都没有启动了&#xff0c;今天想启动启动不起来了&#xff0c;打开没几秒就闪退&#xff0c;记录一下解决方案。仅供参考 首先&#xff0c;参照其他解决方案&#xff0c;本…

【Python系列】数字的bool值

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学…

JAVA每日作业day7.4

ok了家人们今天学习了Date类和simpleDateformat类&#xff0c;话不多说我们一起看看吧 一.Date类 类 java.util.Date 表示特定的瞬间 ( 日期和时间 ) &#xff0c;精确到毫秒。 1.2 Date类的构造方法 public Date(): 用来创建当前系统时间对应的日期对象。 public Date(long …

Linux系统(CentOS)安装iptables防火墙

1&#xff0c;先检查是否安装了iptables 检查安装文件-执行命令&#xff1a;rpm -qa|grep iptables 检查安装文件-执行命令&#xff1a;service iptables status 2&#xff0c;如果安装了就卸装(iptables-1.4.21-35.el7.x86_64 是上面命令查出来的版本) 执行命令&#xff1a…

【高性能服务器】多进程并发模型

&#x1f525;博客主页&#xff1a; 我要成为C领域大神&#x1f3a5;系列专栏&#xff1a;【C核心编程】 【计算机网络】 【Linux编程】 【操作系统】 ❤️感谢大家点赞&#x1f44d;收藏⭐评论✍️ 本博客致力于知识分享&#xff0c;与更多的人进行学习交流 对于常见的C/S模型…

spark on k8s两种方式的原理与对比

spark on k8s两种方式的原理与对比 1、spark on k8s 方式 spark-submit可以直接用来向 Kubernetes 集群提交 Spark 应用&#xff0c;提交机制如下&#xff1a; 1、Spark 创建一个在Kubernetes pod中运行的 Spark 驱动程序。 2、驱动程序创建在 Kubernetes Pod 中运行的执行器…

JAVA基础知识(上)

# 一、说说&和&&的区别? 作为运算符&#xff1a;& 将二进制的每一位进行与运算 作为逻辑运算符&#xff1a;两者都是与&#xff0c;&& 如果左边为假则终止右边运算&#xff0c;即短路运算。& 则需要把两边的比较执行完 # 二、int和Integer的区…

智慧校园-资产管理系统总体概述

智慧校园资产管理系统是面向教育机构设计的一体化数字平台&#xff0c;其核心目标在于通过先进的信息技术手段&#xff0c;全面优化校园内部的资产管理流程。该系统致力于提升资产管理的效率与透明度&#xff0c;同时降低成本并确保所有操作符合财务及审计规范&#xff0c;为校…

springboot基于Java的超市进销存系统+ LW+ PPT+源码+讲解

第三章系统分析与设计 3.1 可行性分析 一个完整的系统&#xff0c;可行性分析是必须要有的&#xff0c;因为他关系到系统生存问题&#xff0c;对开发的意义进行分析&#xff0c;能否通过本网站来补充线下超市进销存管理模式中的缺限&#xff0c;去解决其中的不足等&#xff0c…

Cesium 二三维热力图

Cesium 二三维热力图 原理&#xff1a;主要依靠heatmap.js包来实现 效果图&#xff1a;

Vue 前端修改页面标题无需重新打包即可生效

在public文件夹下创建config.js文件 index.html页面修改 其他页面的标题都可以用window.title来引用就可以了&#xff01;

Java项目:基于SSM框架实现的校园快递代取管理系统【ssm+B/S架构+源码+数据库+毕业论文】

一、项目简介 本项目是一套基于SSM框架实现的校园快递代取管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 该系统功能完善、界面美观、操作简单、…

关于 Mac 系统 .DS_store 文件的起源

原文&#xff1a;Arno - 2006.10.01 &#xff08;前排提醒&#xff1a;可以在 .gitignore 中添加 .DS_Store&#xff0c;否则 git 仓库会存储这个和项目无关的文件。&#xff09; 如果你是 Mac 用户&#xff0c;曾经将文件从 Mac 传输到 Windows&#xff0c;那么可能对 .DS_S…

Hadoop权威指南-读书笔记-02-关于MapReduce

Hadoop权威指南-读书笔记 记录一下读这本书的时候觉得有意思或者重要的点~ 还是老样子~挑重点记录哈&#x1f601;有兴趣的小伙伴可以去看看原著&#x1f60a; 第二章 关于MapReduce MapReduce是一种可用于数据处理的编程模型。 MapReduce程序本质上是并行运行的&#xff0c…

算法体系-26 第二十六节:第26节:单调栈结构 (5节)

一 单调栈知识讲解 1.1描述 一个数组里面想的到每个位置与他最近的左边和右边比他小的最近的信息 1.2 分析 通过单调栈的特点&#xff0c;for遍历数组中的每个数&#xff0c;当前数来的时候对比单调栈中的数进行每个数的左右判断完满足条件的进行更新到当前i种的 int[][] re…

【鸿蒙学习笔记】Stage模型工程目录

官方文档&#xff1a;应用配置文件概述&#xff08;Stage模型&#xff09; 目录标题 FA模型和Stage模型工程级目录模块级目录app.json5module.json5程序执行流程程序基本结构开发调试与发布流程 FA模型和Stage模型 工程级目录 模块级目录 app.json5 官方文档&#xff1a;app.j…