算法知识点————贪心
贪心:只考虑局部最优解,不考虑全部最优解。有时候得不到最优解。
DP:考虑全局最优解。DP的特点:无后效性(正在求解的时候不关心前面的解是怎么求的);
二者都是在求最优解的,都有最优子结构的性质(子问题的最优解构成当前问题的最优解)。
经典的区间分割问题
1、无重叠区间
思路:如果当前区间的左端点大于等于前一个区间的右端点,说明当前区间可以是一个独立的区间,我们可以保存它,如果当前区间的左端点小于前一个区间的右端点,说明当前区间和前面一个区间重合了,我们需要删除一个区间,那么删除哪个更好呢?很明显是当前这个,因为下一个区间如果和前面那个区间重合了,也肯定和当前区间重合,这时候又要删除一个区间,但是下一个区间如果和当前区间重合,那么把当前区间删除后,不一定会和前面的区间重合。所以不论是Case 2还是Case 3我们都应该删除current区间。因此我们只需要不断的维护前一个保留区间的右端点即可,只有当当前区间的左端点大于前一个保留区间右端点时,我们才更新保留区间。

class Solution {
public:int eraseOverlapIntervals(vector<vector<int>>& intervals) {int len = intervals.size();if(len == 1) return 0;sort(intervals.begin(),intervals.end(),[](const auto& u,const auto& v){return u[1] < v[1];});int base = intervals[0][1];//第一个里面的右边界int cnt = 1;for(int i=1;i<len ;i++){// 若当前区间与最近区间没有重叠,则移动到当前区间进行后续判定(之后的区间不可能与最近区间重叠)// 若当前区间与最近区间重叠,则删除二者中右边界更靠后的if(intervals[i][0] >= base){cnt++; //统计非重叠的区间数量base = intervals[i][1];}}return len - cnt;}
};
//排序规则:
//先对右边界排序,右边界相同的时候左边界大的排在前面
区间合并类型的问题一般都要对左端点或者右端点进行排序,然后再进行区间的合并就方便了,因为左端点或者右端点已经有序了。
对这道题来说前后紧挨着的区间的相对位置关系只有3种:
对这道题来说前后紧挨着的区间的相对位置关系只有3种:1. st1 ed1 两区间相互包含st2 ed22. st1 ed1 两区间不完全包含但有交叉st2 ed23. st1 ed1 两区间完全没有交集st2 ed24. 不会出现这种情况 st1 ed1 因为之前对区间的左端点排过序了,后面区间的左端点不st2 ed2 可能超过前面区间的左端点最多相同。
2、合并区间://按照左边界排序
class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> res;sort(intervals.begin(),intervals.end(),[](const vector<int>& a,const vector<int>& b){if(a[0] == b[0]) return a[1] < b[1]; //左边界相等时按右边界排return a[0] < b[0] ;//先按照左边界排序});//记录新区间的左右端点,判断当前区间能否合并int left = intervals[0][0],right = intervals[0][1];for(auto interval : intervals){//当前区间左端点小于当前右边界,合并,并更新可能增大的右边界//当前区间左端点大于当前右边界,记录新的区间,进入下一个新区间构建if(interval[0] <= right && interval[1] > right){right = interval[1];continue;}if(interval[0] > right){res.push_back({left,right});left = interval[0];right = interval[1];}}res.push_back({left,right});//添加最后一个区间return res;}
};
//按照左边界排序
3、区间列表的交集
两个指针分别指向列表区间的开头
每次求得两个区间的交集(左端点取max,右端点取min)
每次将右端点靠后的区间指针向后移动。比较的时候舍弃右边界小的

class Solution {
public:vector<vector<int>> intervalIntersection(vector<vector<int>>& firstList, vector<vector<int>>& secondList) {int len1 = firstList.size();int len2 = secondList.size();vector<vector<int>> res;int i =0,j =0;while(i < len1 && j < len2){int l = max (firstList[i][0],secondList[j][0]);int r = min(firstList[i][1],secondList[j][1]);if(l <= r) res.push_back({l,r});if(firstList[i][1] == secondList[j][1]) {i++;j++;} else if(firstList[i][1] < secondList[j][1]) i++;else j++;}return res;}
};
相关文章:
算法知识点————贪心
贪心:只考虑局部最优解,不考虑全部最优解。有时候得不到最优解。 DP:考虑全局最优解。DP的特点:无后效性(正在求解的时候不关心前面的解是怎么求的); 二者都是在求最优解的,都有最优…...
python数据分析
Python是一种非常流行的编程语言,尤其在数据分析领域。Python拥有丰富的库和框架,可以帮助你执行各种数据分析任务。Python常用的数据分析工具之一:NumPy。 Numpy用于进行大规模数值和矩阵运算,提供了多维数组对象和一系列操作这…...
UGUI(现成组合控件)
Drop Down Scroll View Scroll Bar size是滚动条的填充程度 Slider 如果设置为静态,那么传入的值始终为自己设置的那个值 Input Field content type为standard时 可以设置line type, 只读不改,就是可以复制,但是你已经不能输入了…...
软件交付体系文件(Word源资料)
软件文档交付清单是指在软件开发项目完成后,开发团队需要准备的一份详细清单,用于确保交付的软件产品符合客户需求并达到预期的质量标准。以下是软件文档交付清单中可能包含的一些关键要素 软件全套资料部分文档清单: 工作安排任务书…...
【视频目标分割-2024CVPR】Putting the Object Back into Video Object Segmentation
Cutie 系列文章目录1 摘要2 引言2.1背景和难点2.2 解决方案2.3 成果 3 相关方法3.1 基于记忆的VOS3.2对象级推理3.3 自动视频分割 4 工作方法4.1 overview4.2 对象变换器4.2.1 overview4.2.2 Foreground-Background Masked Attention4.2.3 Positional Embeddings 4.3 Object Me…...
掌握 C# 文件和输入输出操作
在任何编程语言中,文件和输入输出操作(I/O)都是非常重要的组成部分。C# 提供了一系列工具和类来帮助开发者处理文件的读取、写入、二进制文件的处理以及数据的序列化与反序列化。本文将介绍 C# 中的文件操作,包括 File 类、Stream…...
k8s 中的金丝雀发布(灰度发布)
目录 1 什么是金丝雀发布 2 Canary 发布方式 3 Canary 两种发布方式实操 3.1 准备工作 3.1.1 将 nginx 命名两个版本 v1 与 v2 3.1.2 暴露端口并指定微服务类型 3.1.3 进入 pod 修改默认发布文件 3.1.4 测试 service 是否正常 3.2 基于权重的灰度发布 3.2.1 创建 Igress 资源类…...
《IDEA:让编程效率翻倍的强大工具》
哪个编程工具让你的工作效率翻倍? 在众多编程工具中,IntelliJ IDEA 无疑是一款让我的工作效率得到显著提升的利器。 一、功能特点 智能代码补全 IDEA 的代码补全功能极其智能。它不仅能根据你输入的前缀快速列出可能的代码选项,还会根据上…...
Docker 部署 Prometheus+Grafana 监控系统快速指南
Docker 部署 PrometheusGrafana 监控系统快速指南 文章目录 Docker 部署 PrometheusGrafana 监控系统快速指南一 创建网络二 监控部署三 配置 prometheus.yml四 测试部署是否成功五 Grafana表盘下载 本文详细介绍了通过 Docker 和 Docker Compose 快速部署 Prometheus 和 Grafa…...
No.8 笔记 | SQL 查询语句:数据探索的钥匙
2024/10/7 心记 - 致在路上默默奋斗的你 在当今数字化的时代,网络安全已成为我们生活中不可或缺的一部分。它如同守护数字世界的隐形盾牌,保护着我们的隐私、数据和整个社会的稳定运行。 学习网络安全,是踏上一段充满挑战与机遇的征程。 每一…...
全局数据在Python包中模块间管理方法探讨
在开发大型 Python 应用程序时,有时需要多个模块共享和管理全局数据。如何优雅地在 Python 包内的不同模块间共享全局数据是一个常见的设计问题。我们希望避免全局变量的混乱和难以维护的代码,但同时能够安全、高效地管理这些共享数据。 下面我们将探讨…...
无人机在矿业领域的应用!
矿区测绘与建模 无人机可以快速、全面地获取矿区的地形地貌数据,生成高精度的二维或三维模型。 这些模型可用于矿区的规划、设计、监测和管理,提高矿山的生产效率。 库存量量化监测 无人机能够捕捉厘米级的地形数据,通过计算得出准确的库…...
基于JavaWeb开发的java springmvc+mybatis学生考试系统设计和实现
基于JavaWeb开发的java springmvcmybatis学生考试系统设计和实现 🍅 作者主页 网顺技术团队 🍅 欢迎点赞 👍 收藏 ⭐留言 📝 🍅 文末获取源码联系方式 📝 🍅 查看下方微信号获取联系方式 承接各…...
【CKA】四、etcd的备份与恢复
4、etcd的备份与恢复 1. 考题内容: 2. 答题思路: 1、ssh到有etcdctl、etcdutl命令的节点 2、备份时注意添加证书并保证路径正确 3、备份完可以验证下 4、恢复备份时要停服务,恢复备份后重启kubelet 题型是一样的,我考的证书的路…...
基于Arduino的SG90舵机驱动
一.SG90舵机引脚说明 SG90舵机三根线的连接方法: 1.红色线:电源线(VCC),接入5v电源 2.棕色线:地线(GND),接地 3.黄色线:信号线(SIG)…...
大模型泡沫破了?| 转行建筑师混战大模型圈
最近秋招惨淡卷动,**地产天坑不敢进,科技大厂不可期。**阿里直裁应届生、腾讯拉长职级晋升时间,字节一家繁荣,但也在和美国政府大打官司。此前「大模型」风生水起,但近期融资、应用双双预冷。 GPT-5迟迟不出࿰…...
Windows开发工具使用技巧
Windows开发工具使用技巧 在Windows系统下进行软件开发时,掌握并熟练使用合适的开发工具可以极大地提高工作效率和代码质量。本篇文章将介绍几款常见的Windows开发工具及其使用技巧,涵盖集成开发环境(IDE)、命令行工具、版本控制…...
【PyTorch学习-1】张量操作|自动求导|神经网络模块|优化器|数据加载与处理|GPU 加速...
【PyTorch学习-1】张量操作|自动求导|神经网络模块|优化器|数据加载与处理|GPU 加速… 【PyTorch学习-1】张量操作|自动求导|神经网络模块|优化器|数据加载与处理|GPU 加速… 文章目录 【PyTorch学习-1】张量操作|自动求导|神经网络模块|优化器|数据加载与处理|GPU 加速...前言…...
Leecode热题100-560.和为k的子数组
给你一个整数数组 nums 和一个整数 k ,请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1: 输入:nums [1,1,1], k 2 输出:2示例 2: 输入:nums [1,2,3], k…...
Mac 卸载 IDEA 流程
1、现在应用程序中删除Idea 2、进入Library目录 cd /Users/zhengzhaoxiang/Library 3、删除IntelliJIdea2023.3(根据自己的版本而定)记得进去看下是否删除干净了 rm -rf Logs/JetBrains/IntelliJIdea2023.3 rm -rf Preferences/com.jetbrains.intel…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
大语言模型如何处理长文本?常用文本分割技术详解
为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
Pydantic + Function Calling的结合
1、Pydantic Pydantic 是一个 Python 库,用于数据验证和设置管理,通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发(如 FastAPI)、配置管理和数据解析,核心功能包括: 数据验证:通过…...
02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...
OpenGL-什么是软OpenGL/软渲染/软光栅?
软OpenGL(Software OpenGL)或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式(包括几何处理、光栅化、着色等),不依赖GPU硬件加速。这种模式通常性能较低,但兼容性极强,常用于不支持硬件加速…...
