当前位置: 首页 > news >正文

LeetCode刷题笔记【27】:贪心算法专题-5(无重叠区间、划分字母区间、合并区间)

文章目录

  • 前置知识
  • 435. 无重叠区间
    • 题目描述
    • 参考<452. 用最少数量的箭引爆气球>, 间接求解
    • 直接求"重叠区间数量"
  • 763.划分字母区间
    • 题目描述
    • 贪心 - 建立"最后一个当前字母"数组
    • 优化marker创建的过程
  • 56. 合并区间
    • 题目描述
    • 解题思路
    • 代码
      • ① 如果有重合就合并到ans.back()里面
      • ② 直接在intervals上操作(非常麻烦其实)
      • ③ 整一个current数组来操作
  • 总结

前置知识

参考前文

参考文章:
LeetCode刷题笔记【23】:贪心算法专题-1(分发饼干、摆动序列、最大子序和)
LeetCode刷题笔记【24】:贪心算法专题-2(买卖股票的最佳时机II、跳跃游戏、跳跃游戏II)
LeetCode刷题笔记【25】:贪心算法专题-3(K次取反后最大化的数组和、加油站、分发糖果)
LeetCode刷题笔记【26】:贪心算法专题-4(柠檬水找零、根据身高重建队列、用最少数量的箭引爆气球)

435. 无重叠区间

题目描述

在这里插入图片描述

LeetCode链接:https://leetcode.cn/problems/non-overlapping-intervals/description/

参考<452. 用最少数量的箭引爆气球>, 间接求解

思路: 让我们求要移除多少区间, 从而让剩下的区间不重叠
那我们参考<452. 用最少数量的箭引爆气球>, 进行修改
引爆气球这一题中, 每一箭都代表一个"重叠区间组", 那么用 总区间数-箭数, 就得到多余的重复区间数量

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.empty())   return 0;int ans=1;sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[0] < b[0];});for(int i=1; i<intervals.size(); ++i){if(intervals[i][0] >= intervals[i-1][1]){ans++;}else{intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);}}return intervals.size()-ans;}
};

直接求"重叠区间数量"

直接求"重叠区间数量"

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {if(intervals.empty())   return 0;int count=0;sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[0] < b[0];});for(int i=1; i<intervals.size(); ++i){if(intervals[i][0] >= intervals[i-1][1]){continue;}else{count ++;intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);}}return count;}
};

763.划分字母区间

题目描述

截图

LeetCode链接:https://leetcode.cn/problems/partition-labels/description/

贪心 - 建立"最后一个当前字母"数组

参考<代>: 在真正开始遍历之前, 先建立一个vector<int> marker数组
marker[i]存储s[i]最远的下一个相同字母在哪一位
然后遍历的时候, 比如从i, 跳到了j, 那么下一个区间就从j开始

但是除此之外, 在第一次的i~j之间, 如果某个kmarker[k]>j, 那么j就要更新为marker[k]

class Solution {
public:vector<int> partitionLabels(string s) {vector<int> marker(s.size());for(int i=0; i<s.size(); ++i){char c = s[i];int j=s.size()-1;while(s[j] != s[i])j--;marker[i] = j;}// for(int i : marker)//     cout << i << " " ;vector<int> ans;int left=0, right=0;for(int i=0; i<s.size(); ++i){right = max(right, marker[i]);if(i==right){ans.push_back(right-left+1);left = i+1;}}return ans;}
};

优化marker创建的过程

干菜这样做没问题, 但是在建立marker数组的时候可以更优雅

class Solution {
public:vector<int> partitionLabels(string s) {vector<int> marker(27);for(int i=0; i<s.size(); ++i){marker[s[i]-'a'] = i;}// for(int i : marker)//     cout << i << " " ;vector<int> ans;int left=0, right=0;for(int i=0; i<s.size(); ++i){right = max(right, marker[s[i]-'a']);if(i==right){ans.push_back(right-left+1);left = i+1;}}return ans;}
};

56. 合并区间

题目描述

截图

LeetCode链接:xxx(记得加点击跳转链接)

解题思路

思路和<452. 用最少数量的箭引爆气球>以及<435. 无重叠区间>一样
都是先sort, 然后倒腾右边界(依次遍历, 如果有重叠就合并, 没有重叠就加入ans)

相比于前面两道例题, 没有合并后右边界取min的思维拐弯, 其实难度是降低的, 但还是要注意, 右边界要取cur和cpr的max

这里的"有重叠就合并", 一方面可以先在ans中加入一个区间, 然后和ans.back()合并
也可以直接在intervals上操作
甚至可以单独拎一个current数组出来进行操作
以下将分别展示这三种做法:

代码

① 如果有重合就合并到ans.back()里面

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[0] < b[0];});vector<vector<int>> ans;ans.push_back(intervals[0]);for(int i=1; i<intervals.size(); ++i){if(intervals[i][0] <= ans.back()[1]){// 一方面注意这里不是intervals[i-1], 而是ans.back()ans.back()[1] = max(intervals[i][1], ans.back()[1]);// 另一方面要注意, 这里原先的ans.back()的右侧边界可能还更大}else{ans.push_back(intervals[i]);}}return ans;}
};

② 直接在intervals上操作(非常麻烦其实)

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[0] < b[0];});vector<vector<int>> ans;for(int i=0; i<intervals.size()-1; ++i){if(intervals[i][1] < intervals[i+1][0]){ans.push_back(intervals[i]);}else{intervals[i+1][0] = min(intervals[i+1][0], intervals[i][0]);intervals[i+1][1] = max(intervals[i+1][1], intervals[i][1]);}}ans.push_back(intervals.back());return ans;}
};

③ 整一个current数组来操作

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b){return a[0] < b[0];});vector<vector<int>> ans;vector<int> cur=intervals[0];for(vector<int>& interval : intervals){if(interval[0] > cur[1]){//么有重合ans.push_back(cur);cur = interval;}else{cur[1] = max(cur[1], interval[1]);}}ans.push_back(cur);return ans;}
};

总结

今天三道题, 可以和昨天的最后一道题结合来看, 都是区间操作的题目.
今天的第二题也可以用回溯来做, 但是回溯毕竟是遍历, 时间复杂度高.

这些区间操作题目可以提炼出以下操作方式和注意点

  1. 先sort, 再遍历操作 (如果按照左边界sort, 那么就操作右边界(反之亦可));
  2. 遍历操作过程中, 判断前后有无重合, 分类讨论操作;
  3. 如果是要求重叠区间类问题, 那么对右边界, 要转换为当前区间和新区间的min
  4. 如果是要求合并区间的问题, 那么对右边界, 要转换为当前区间和新区间的max(不能简单地认为新区间的右边界>当前区间的右边界, 可能是当前区间大到包含了新区间)

本文参考:
无重叠区间
划分字母区间
合并区间

相关文章:

LeetCode刷题笔记【27】:贪心算法专题-5(无重叠区间、划分字母区间、合并区间)

文章目录 前置知识435. 无重叠区间题目描述参考<452. 用最少数量的箭引爆气球>, 间接求解直接求"重叠区间数量" 763.划分字母区间题目描述贪心 - 建立"最后一个当前字母"数组优化marker创建的过程 56. 合并区间题目描述解题思路代码① 如果有重合就合…...

nvidia-smi 命令详解

nvidia-smi 命令详解 1. nvidia-smi 面板解析2. 显存与GPU的区别 Reference: nvidia-smi命令详解 相关文章&#xff1a; nvidia-smi nvcc -V 及 CUDA、cuDNN 安装 nvidia-smi(NVIDIA System Management Interface) 是一种命令行实用程序&#xff0c;用于监控和管理 NVIDIA G…...

fork()函数的返回值

在程序中&#xff0c;int pd fork() 是一个典型的 fork() 调用。fork() 函数会创建一个新的进程&#xff0c;然后在父进程中返回子进程的进程ID&#xff08;PID&#xff09;&#xff0c;在子进程中返回0。所以 pd 的值会根据当前进程是父进程还是子进程而有所不同&#xff1a;…...

Stable Diffusion WebUI挂VPN不能跑图解决办法(Windows)

如何解决SD在打开VPN的状态不能运行的问题 在我们开VPN的时候会出现无法生成图片&#xff0c;也无法做其他任何事&#xff0c;这个时候是不是很着急呢&#xff1f; 别急&#xff0c;我这里会说明如何解决。 就像这样&#xff0c;运行半天生成不了图&#xff0c;有时还会出现…...

Android的本地数据

何为本地&#xff0c;即写完之后除非手动修改&#xff0c;否像嘎了一样在那固定死了 有些需求可能也会要求我们去写死数据&#xff0c;因为这需求是一成不变的&#xff0c;那么你通常会用什么方法写死呢&#xff1f; 1. 本地存储-SharedPreferences 此方法可以长时间保存于手…...

android NDK 开发包,网盘下载,不限速

记录下ndk 开发包的地址&#xff0c;分享给大家。 另外有Android studio的下载包&#xff0c; 在另一篇文章 链接&#xff1a;http://t.csdn.cn/JSr9x Android Studio.exe 下载 2023 最新更新&#xff0c;网盘下载_hsj-obj的博客-CSDN博客 主要是19-25&#xff0c;其他的没有…...

【每日一题Day320】LC2651计算列车到站时间 | 数学

计算列车到站时间【LC2651】](https://leetcode.cn/problems/calculate-delayed-arrival-time/) 给你一个正整数 arrivalTime 表示列车正点到站的时间&#xff08;单位&#xff1a;小时&#xff09;&#xff0c;另给你一个正整数 delayedTime 表示列车延误的小时数。 返回列车实…...

C语言柔性数组详解:让你的程序更灵活

柔性数组 一、前言二、柔性数组的用法三、柔性数组的内存分布四、柔性数组的优势五、总结 一、前言 仔细观察下面的代码&#xff0c;有没有看出哪里不对劲&#xff1f; struct S {int i;double d;char c;int arr[]; };还有另外一种写法&#xff1a; struct S {int i;double …...

Redis-带你深入学习数据类型list

目录 1、list列表 2、list相关命令 2.1、添加相关命令&#xff1a;rpush、lpush、linsert 2.2、查找相关命令&#xff1a;lrange、lindex、llen 2.3、删除相关命令&#xff1a;lpop、rpop、lrem、ltrim 2.4、修改相关命令&#xff1a;lset 2.5、阻塞相关命令&#xff1a…...

react拖拽依赖库react-dnd

注&#xff1a;对于表格自定义行可以拖拽和树自定义节点可以拖拽等比较适用&#xff0c;其余的拖拽处理可以使用dragstart&#xff0c;drop等js原生事件来实现 react-dnd使用方法很简单&#xff0c;直接上干货 第一步安装依赖并引入 import { DndProvider } from react-dnd;…...

win10环境安装使用docker-maxwell

目的&#xff1a;maxwell可以监控mysql数据变化&#xff0c;并同步到kafka、mq或tcp等。 maxwell和canal区别&#xff1a; maxwell更轻量&#xff0c;canal把表结构也输出了 docker bootstrap可导出历史数据&#xff0c;canal不能 环境 &#xff1a;win10&#xff0c;mysql5…...

Docker部署RabbitMQ

Docker部署RabbitMQ 介绍 RabbitMQ是一个开源的消息队列系统&#xff0c;它被设计用于在应用程序之间传递消息。它采用了AMQP&#xff08;高级消息队列协议&#xff09;作为底层通信协议&#xff0c;这使得它能够在不同的应用程序之间进行可靠的消息传递。 那么&#xff0c;…...

23个react常见问题

1、setState 是异步还是同步&#xff1f; 合成事件中是异步 钩子函数中的是异步 原生事件中是同步 setTimeout中是同步 相关链接&#xff1a;你真的理解setState吗&#xff1f;&#xff1a; 2、聊聊 react16.4 的生命周期 图片 相关连接&#xff1a;React 生命周期 我对 Reac…...

【python基础】——Anaconda下包更新的坑及安装与卸载、及安装后Jupyter Notebook没反应的解决方法

文章目录 前言一、起因:如何一步步走到卸载重装anaconda?二、卸载anaconda二、重新安装anaconda三、关于安装Anaconda后,打开Jupyter Notebook运行代码没反应且in[ ]没有*前言 本文主要用来记录自己近期踩坑的一些复盘。其中坑有: ‘.supxlabel’ 不起作用的解决pip list 与…...

CSS 中的 display 和 visibility

CSS 中的 display 和 visibility 都可以设置一个元素在浏览器中的显示或隐藏效果。 display: 隐藏某个元素时&#xff0c;不会占用任何空间。换句话讲&#xff0c;不会影响布局。visibility: 隐藏某个元素时&#xff0c;仍需占用与未隐藏之前一样的空间。换句话讲&#xff0c;…...

解决mysql报错this is incompatible with DISTINCT

环境 centos 9 php7.4 mysql5.7 问题 mysql查询报如下错误&#xff1a; SQLSTATE[HY000]: General error: 3065 Expression #1 of ORDER BY clause is not in SELECT list, references column hst_csc.q.timestamp which is not in SELECT list; this is incompatible with…...

C++-map和set

本期我们来学习map和set 目录 关联式容器 键值对 pair 树形结构的关联式容器 set multiset map multimap 关联式容器 我们已经接触过 STL 中的部分容器&#xff0c;比如&#xff1a; vector 、 list 、 deque 、forward_list(C11)等&#xff0c;这些容器统称为序列式…...

微信小程序AI类目-深度合成-AI问答/AI绘画 互联网信息服务算法备案审核通过教程

近期小程序审核规则变化后&#xff0c;很多使用人类小徐提供的chatGPT系统的会员上传小程序无法通过审核&#xff0c;一直提示需要增加深度合成-AI问答、深度合成-AI绘画类目&#xff0c;该类目需要提供互联网信息服务算法备案并上传资质&#xff0c;一般对企业来说这种务很难实…...

蓝桥杯官网练习题(星期一)

题目描述 本题为填空题&#xff0c;只需要算出结果后&#xff0c;在代码中使用输出语句将所填结果输出即可。 整个 2020 世纪&#xff08;1901 年 1 月 1 日至 2000 年 12 月 3131 日之间&#xff09;&#xff0c;一共有多少个星期一&#xff1f;(不要告诉我你不知道今天是星…...

centos7更新podman

实验环境&#xff1a;centos7.7.1908 1.安装podman并查看版本 yum install podman podman -v 当前podman版本信息是1.6.4 2.更新podman版本 通过查看资料显示centos 7 支持最高版本为 3.4.4&#xff0c;更新podman大致有以下四步&#xff1a; golang 安装(本次使用版本: 1.…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...