【算法day25】贪心:重叠区间2

ops/2024/12/29 8:55:20/

题目引用


  1. 合并区间
  2. 单调递增的数字

1. 合并区间


以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

学习了昨天的题目之后大家应该对这种题目驾轻就熟了,唯一可能有问题的就是语法上的小细节,大家看看代码注意一下就好啦。

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

2. 单调递增的数字


当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。

示例 1:
输入: n = 10
输出: 9

示例 2:
输入: n = 1234
输出: 1234

这道题像不像咱们小学做的数学拓展呀,题目理解上大家应该没什么问题,那么我们来看一下怎么做。
首先大家肯定能想到当前一位大于后一位时我们让其–,再从后往前赋值为9。
但是是从后往前判断–呢还是从前往后判断–呢,我们来模拟一下,以332举例,当我们从前往后这样执行时,会发现我们的结果最后会是329,不符合题意,所以应该是从后往前遍历比较。
这里的局部最优就是尽量让当前数字符合递增规律,全局最优就是让数字整体符合递增规律而且为最大。
那么我们直接看代码吧:

class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值,为了防止第二个for循环在flag没有被赋值的情况下执行int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; i--) {if (strNum[i - 1] > strNum[i] ) {flag = i;strNum[i - 1]--;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

总结


到这里咱们的贪心就算结束啦,希望大家下来好好吸收和总结。


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

相关文章

流架构的读书笔记(2)

流架构的读书笔记&#xff08;2&#xff09; 一、建模工具之一沃德利地图 推测技术的发展,交流和辩论思想的最有力的方法是沃德利地图 沃德利地图的制作步骤 1确定范围和用户需求 2确定满足用户需求所需的组件 3在一条范围从全新到被人们接受的演进轴上评估这些组成 部分的演…

5.npm包

文章目录 [TOC](文章目录) 3.npm与包3.1.包3.2.npm体验在项目中安装包的命令包管理配置文件一次性安装开发项目时安装的包如何从项目中卸载包devDependencies节点的作用解决下载包速度比较慢的问题nrm工具&#xff0c;利用其提供的终端命令&#xff0c;可以快速查看和切换下包的…

mybatis/mybatisplus

一、mybatis 1.什么是 持久化框架。通过XML或注解的方式将实体类和SQL语句进行映射&#xff0c;开发者快速进行CRUD操作。 2.核心组件 (1)SqlSessionFactory 创建SqlSession实例。用于执行SQL操作 。代码 String resource "org/mybatis/example/mybatis-config.xml&q…

【反转链表系列】力扣206,92,25

文章目录 一、前言二、反转链表三、反转链表 II四、K 个一组翻转链表 一、前言 本文涉及的力扣题目&#xff0c;涉及简单、中等、困难三个难度 力扣206.反转链表力扣92.反转链表 II力扣25.K 个一组翻转链表 反转链表这类型的题目&#xff0c;折磨了挺久&#xff0c;经常弄懂了一…

Docker Container 可观测性最佳实践

Docker Container 介绍 Docker Container&#xff08; Docker 容器&#xff09;是一种轻量级、可移植的、自给自足的软件运行环境&#xff0c;它在 Docker 引擎的宿主机上运行。容器在许多方面类似于虚拟机&#xff0c;但它们更轻量&#xff0c;因为它们不需要模拟整个操作系统…

神经网络-LeNet

LeNet在1990年被提出&#xff0c;是一系列网络的统称&#xff0c;包括了LeNet1~LeNet5&#xff0c;对于神经网络的学习者来说&#xff0c;大家对下面这个图一定很熟悉&#xff0c;该图是对LeNet的简化展示。 在LeNet中已经提出了卷积层、Pooling层等概念&#xff0c;只是但是由…

Oracle数据库高级应用与优化策略

Oracle数据库高级应用与优化策略 在数据驱动的时代,Oracle数据库作为企业级数据库管理的佼佼者,以其强大的数据处理能力、高可用性和安全性,在众多行业领域中扮演着不可或缺的角色。本文旨在深入探讨Oracle数据库的高级应用与优化策略,通过具体代码使用案例,帮助开发者和…

FAISS进行高效的向量检索 原理详解

FAISS&#xff08;Facebook AI Similarity Search&#xff09;是由Facebook研发的一个用于高效相似性搜索和密集向量聚类的库。它特别适用于处理大规模向量数据库和提供快速的近邻搜索。FAISS高效的原因在于其专门的索引结构和优化的搜索算法。以下将详细解释FAISS的底层原理和…