没有合适的资源？快使用搜索试试~ 我知道了~

文库首页安全技术网络安全2-数据结构与算法高频真题1

2-数据结构与算法高频真题1

需积分: 0 0 下载量 106 浏览量 2022-08-03 16:15:32 上传评论收藏 1.8MB PDF 举报

温馨提示

试读

31页

1. 情况一：两个区间没有任何重叠的部分，因此区间不会发生融合 2. 情况二和三：区间有重叠 1. 先将所有的区间按照起始时间的先后顺序排序，从头到尾扫描一遍

资源详情

资源评论

资源推荐

例题分析一

LeetCode 第 56 题：给出一个区间的集合，请合并所有重叠的区间。

示例 1

输入: [[1,3], [2,6], [8,10], [15,18]]

输出: [[1,6], [8,10], [15,18]]

解释: 区间 [1,3] 和 [2,6] 重叠，将它们合并为 [1,6]。

示例 2

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

输出: [[1,5]]

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

解题思路：贪婪法

在分析一些比较复杂的问题时，可以从比较简单的情况着手来寻找突破口，先

来看看两个区间会出现多少种情况。

假设有区间 a 和 b，区间 a 的起始时间要早于 b 的起始时间。那么它们之

间有如下 3 种可能会出现的情况。

拉勾教育

1. 情况一：两个区间没有任何重叠的部分，因此区间不会发生融合。

2. 情况二和三：区间有重叠。

a. 新区间的起始时间是 a 的起始时间，这个不变；

b. 新区间的终止时间是 a 的终止时间和 b 的终止时间的最大值，这个就是融合

两个区间的最基本的思想。

拉勾教育

给定了 n 个区间，如何有效地融合它们呢？以下是一种很直观也是非常有效

的做

法。

1. 先将所有的区间按照起始时间的先后顺序排序，从头到尾扫描一遍

2. 定义两个变量 previous 和 current，分别表示前一个区间和当前的区间

a. 如果没有融合，那么当前区间就变成了新的前一个区间，下一个区间成为新的

当前区间

b. 如果发生了融合，更新前一个区间的结束时间。

这个就是贪婪算法。

代码实现

int[][] merge(int[][] intervals) {

// 将所有的区间按照起始时间的先后顺序排序

Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0],

i2[0]));

// 定义一个 previous 变量，初始化为 null

int[] previous = null;

拉勾教育

// 定义一个 result 变量，用来保存最终的区间结果

List<int[]> result = new ArrayList<>();

// 从头开始遍历给定的所有区间

for (int[] current : intervals) {

// 如果这是第一个区间，或者当前区间和前一个区间没有重叠，那

么将当前区间加入到结果中

if (previous == null || current[0] > previous[

1]) {

result.add(previous = current);

} else { // 否则，两个区间发生了重叠，更新前一个区间的结

束时间

prev[1] = Math.max(previous[1], current[1]

);

}

return result.toArray(new int[result.size()][]);

}

算法分析

时间复杂度 O(nlog(n))，因为一开始要对数组进行排序。

空间复杂度为 O(n)，因为用了一个额外的 result 数组来保存结果。

注意：和区间相关的问题，有非常多的变化，融合区间可以说是最基本也是最

常考的一个。

例题分析二

LeetCode 第 435 题：给定一个区间的集合，找到需要移除区间的最小数

量，使剩余区间互不重叠。

注意:

拉勾教育

1. 可以认为区间的终点总是大于它的起点。

2. 区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。

示例 1

输入: [ [1,2], [2,3], [3,4], [1,3] ]

输出: 1

解释: 移除 [1,3] 后，剩下的区间没有重叠。

示例 2

输入: [ [1,2], [1,2], [1,2] ]

输出: 2

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

示例 3

输入: [ [1,2], [2,3] ]

输出: 0

解释: 你不需要移除任何区间，因为它们已经是无重叠的了。

解题思路一：暴力法

拉勾教育

剩余30页未读，继续阅读

内容反馈

我就是月下

粉丝: 25
资源: 337

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

2-数据结构与算法高频真题1

评论0

最新资源

2-数据结构与算法高频真题1

评论0

PTA-数据结构与算法题目集.zip

026-数据结构与算法之美026-数据结构与算法之美026-数据结构与算法之美026-数据结构与算法之美

5-数据结构与算法高频真题1

4-数据结构与算法高频真题1

C++ STL--数据结构与算法实现（余文溪）示例程序代码.rar

小甲鱼-数据结构和算法.docx

西安电子科技大学-数据结构与算法-期末知识点总结.pdf

双向链表 - 数据结构与算法 C 请看！

计算机系---数据结构与算法设计.pptx

hanoi塔问题--数据结构与算法必备

贪心算法--数据结构与算法必知必会

c++数据结构算法面试笔试题-数据结构与算法笔试题.pdf

计算机-数据结构与算法.docx

最佳学习教材-C#-数据结构-算法分析

计算机基础-数据结构与算法.pdf

最新版ISO/IEC 27001:2022、ISO 27002:2022中英文合集

Goby红队版-win-x64-2.4.7版本

Chrome Header Editor 插件

ISO SAE 21434-2021 中文版.pdf

OpenVAS GVM 中文翻译补丁

安全认证cisp教材全套

CISP、NISP二级、CISE题库最新版（2024年1月更新）

现代永磁同步电机控制原理及MATLAB仿真__袁雷编著1

全面的安全基线核查清单

OpenVAS离线资源

2024最新：Hvv中常见的面试问题

软件工程导论(第六版)课后习题答案1

最新资源