56. 合并区间,738.单调递增的数字

简介: **简介:**本文介绍了两道经典的算法题及其解法,分别是“合并区间”和“单调递增的数字”。 - **合并区间**:通过排序与遍历,将重叠的区间合并为不重叠的区间集合。核心思想是按区间左边界排序,判断当前区间的左边界是否小于等于前一区间的右边界,若满足则更新右边界。时间复杂度为O(nlogn)。- **单调递增的数字**:使用贪心算法解决,从后向前遍历数字字符串,遇到非单调递增的情况时,将前一位减1,并将后续位全部置为9,以确保结果最大且满足单调性。此方法高效且易于实现。两题均通过清晰的逻辑与代码示例展示了算法设计思路,适合初学者理解排序、贪心等基础算法的应用场景。

 题目:56. 合并区间

以数组 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].

示例 2:

输入:intervals = [[1,4],[4,5]]

输出:[[1,5]]

解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示:

1 <= intervals.length <= 104

intervals[i].length == 2

0 <= starti <= endi <= 104

思考历程与知识点:  

本题的本质其实还是判断重叠区间问题。

发现和我们刚刚讲过的452. 用最少数量的箭引爆气球 (opens new window)和 435. 无重叠区间 (opens new window)都是一个套路。

这几道题都是判断区间重叠,区别就是判断区间重叠后的逻辑,本题是判断区间重贴后要进行区间合并。

所以一样的套路,先排序,让所有的相邻区间尽可能的重叠在一起,按左边界,或者右边界排序都可以,处理逻辑稍有不同。

按照左边界从小到大排序之后,如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界,则一定有重叠。(本题相邻区间也算重贴,所以是<=)

题解:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        if (intervals.size() == 0) return result; // 区间集合为空直接返回
        // 排序的参数使用了lambda表达式
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
 
        // 第一个区间就可以放进结果集里,后面如果重叠,在result上直接合并
        result.push_back(intervals[0]);  
 
        for (int i = 1; i < intervals.size(); i++) {
            if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间
                // 合并区间,只更新右边界就好,因为result.back()的左边界一定是最小值,因为我们按照左边界排序的
                result.back()[1] = max(result.back()[1], intervals[i][1]);  
            } else {
                result.push_back(intervals[i]); // 区间不重叠  
            }
        }
        return result;
    }
};

 题目:738. 单调递增的数字

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

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

示例 1:

输入: n = 10

输出: 9

示例 2:

输入: n = 1234

输出: 1234

示例 3:

输入: n = 332

输出: 299

提示:

0 <= n <= 109

思考历程与知识点:  

题目要求小于等于N的最大单调递增的整数,那么拿一个两位的数字来举例。

例如:98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]--,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。

这一点如果想清楚了,这道题就好办了。

此时是从前向后遍历还是从后向前遍历呢?

从前向后遍历的话,遇到strNum[i - 1] > strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能又小于strNum[i - 2]。

这么说有点抽象,举个例子,数字:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。

那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 -> 329 -> 299

确定了遍历顺序之后,那么此时局部最优就可以推出全局,找不出反例,试试贪心。

题解:

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);
    }
};


相关文章
|
算法 容器
最详细版本|UI2Code智能生成Flutter代码——机器生成代码
作者: 闲鱼技术-上叶,余晏 背景   在《UI2CODE--整体设计》篇中,我们提到UI2Code工程的整体流程。前步图片分析之后,我们可以得到对应的DSL布局描述。利用DSL的资讯,结合IntelliJ Plugin介面工具,面向使用者提供生成对应Flutter代码。
13353 0
|
1月前
|
弹性计算 缓存 测试技术
2026年阿里云双十一2核4G云服务器报价,一年/一月/一小时收费明细对比
对于准备上云的个人开发者、初创团队和中小企业来说, [阿里云 ECS 云服务器](https://www.aliyun.com/product/ecs?userCode=t1dwdo7u) 2核4G是一档"承上启下"的关键配置。它不像2核2G那样只够轻量测试,也不像4核8G那样预算门槛相对更高,而是在成本和性能之间找到了一个非常均衡的平衡点:2核CPU能承载一定程度的并发,4GB内存又比2GB多出不少缓冲空间,让应用、数据库连接池、缓存、后台服务等组件有更从容的运行环境。很多中小型网站、企业官网、内容管理系统、小程序后端、API服务,甚至轻量级AI应用,都能在这一档配置上跑得不错。
321 0
|
数据采集 存储 人工智能
141_模型更新:在线学习策略 - 焦点在增量微调的独特无中断部署
在大语言模型(LLM)的实际生产环境中,模型更新是维持服务质量和持续改进的关键环节。随着业务需求的演变、数据分布的变化以及模型能力的提升,如何高效、安全地更新已部署的LLM成为技术团队面临的重要挑战。传统的全量模型替换方法往往伴随着服务中断风险、资源消耗大以及可能的性能波动等问题。为此,增量微调技术作为一种轻量级的模型更新策略,正逐渐成为2025年LLM部署领域的主流选择。
979 9
|
8月前
|
并行计算 编译器 调度
GPU红绿阵营对决:CUDA与ROCm内核调度机制深度漫游指南
本文深入剖析GPU内核(Kernel)在CUDA与ROCm异构生态中的底层交互机制,涵盖命令包生成、环形队列投递、Doorbell通知、硬件调度等关键环节;对比NVIDIA的Warp/SIMT与AMD的Wavefront/HSA架构差异;详解内存优化、延迟掩盖、寄存器级通信及Graph静态调度等极限性能调优策略,助工程师穿透抽象,直抵算力本质。(239字)
1202 6
|
11月前
|
存储 关系型数据库 调度
微服务原理篇(XXLJOB-幂等-MySQL)
本课程涵盖XXL-JOB任务调度、幂等性解决方案及MySQL数据库核心知识。学习内容包括:掌握XXL-JOB的分布式调度优势与搭建使用,理解并实现幂等性以避免重复操作;深入MySQL存储引擎差异、索引机制(如B+树)、回表与覆盖索引原理,并熟悉SQL调优与分库分表策略,提升系统性能与数据一致性保障能力。
 微服务原理篇(XXLJOB-幂等-MySQL)
|
XML JSON Java
【SpringBoot(三)】从请求到响应再到视图解析与模板引擎,本文带你领悟SpringBoot请求接收全流程!
Springboot专栏第三章,从请求的接收到视图解析,再到thymeleaf模板引擎的使用! 本文带你领悟SpringBoot请求接收到渲染的使用全流程!
828 3
|
安全 算法 数据安全/隐私保护
安全漏洞、eBPF、机密计算、商用密码等技术分享|龙蜥大讲堂113期
欢迎大家参加首届中国研究生操作系统创新大赛。我是龙蜥社区安全委员会委员、阿里云技术专家张诗乐。今天,我将为大家介绍龙蜥社区的漏洞治理以及相关的赛题。主要内容分为三个部分:首先,我将简要介绍龙蜥社区及其操作系统;其次,我们将探讨龙蜥社区的漏洞治理流程;最后,我们将解析与龙蜥社区相关的赛题。 1. 龙蜥社区漏洞治理 2. 龙蜥社区赛题介绍 3. 基于 eBPF 的容器异常检测 4. 赛题解析系列
685 12
|
存储 关系型数据库 Linux
2024 年 16 个适用于 Linux 的开源云存储软件 (上)
2024 年 16 个适用于 Linux 的开源云存储软件 (上)
1059 2
2024 年 16 个适用于 Linux 的开源云存储软件 (上)
|
网络协议 算法 Linux
通过实验深入了解 TCP 数据的发送和接收
本系列文章是组内写给新人和实习生的 TCP入门系列教程,结合了理论和实践,本篇为第二篇,建议先读上篇《通过实验深入了解TCP 连接的建立和关闭》。