代码随想录算法训练营DAY36|C++贪心算法Part.5|435.无重叠区间、763.划分字母区间、56. 合并区间

本文主要是介绍代码随想录算法训练营DAY36|C++贪心算法Part.5|435.无重叠区间、763.划分字母区间、56. 合并区间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 435.无重叠区间
    • 按右边界排序
      • CPP代码
    • 按左边界排序
      • 如何判断相邻区间是否重叠
      • 如何判断一下一个区间与当前相邻区间是否重叠
      • 总结
      • CPP代码
  • 763.划分字母区间
    • 思路
    • 伪代码实现
    • CPP代码
  • 56. 合并区间
    • 思路
    • CPP代码

435.无重叠区间

力扣题目链接

文章链接:435.无重叠区间

视频链接:贪心算法,依然是判断重叠区间 | LeetCode:435.无重叠区间

状态:排序顺序很重要!决定了我们如何处理后续逻辑。对于按右边界排序,我们只要抓住分割线即可,每次更新分割线,说明就有非交叉区间;

想都不用想,本题首先要求的肯定就是进行排序,让为了让我们后续更好进行操作。

并且可以很直观得推导出我们的贪心策略:

局部最优——当前区间与相邻两个区间是否重叠,这里是非常有技巧的,具体可以看下面的思路

全局最优——找出所有的重叠区间

按右边界排序

我们先按右边界进行排序,然后从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

记录非交叉区间的个数也是很需要技巧的:

总之一句话,最重要的点就在于找到区间的分割线,每次遇到分割线,我们就记录一次非交叉区间个数。比如上文中,更新了两次分割线,所以非交叉区间是3。所以在代码表现上,也是比较直观的。
基于以上代码的一个重要前提就是:区间是按照右边界来排序的

CPP代码

class Solution {
public:// 按照区间右边界排序static bool cmp (const vector<int>& a, const vector<int>& b) {return a[1] < b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 1; // 记录非交叉区间的个数int end = intervals[0][1]; // 记录区间分割点for (int i = 1; i < intervals.size(); i++) {if (end <= intervals[i][0]) {	//与每个区间的左边界比较end = intervals[i][1];		//更新分割线count++;}}return intervals.size() - count;}
};

按左边界排序

对于左边界排序,这里拿 intervals = [[1,100],[11,22],[1,11],[2,12]]举例,

排序后:intervals = [[1,100],[1,11],[2,12],[11,22]]。如果我们按照右边界排序的处理还能行吗。简单推导一下,这样会导致我们的最终结果是3!因为end永远都无法更新,程序认为只有一条分割线,也就是count = 1

那么如果按照左边界来排序应该怎么写呢?

如何判断相邻区间是否重叠

如果当前区间的左边界[1, 11]大于等于上一个区间的右边界[1, 100]。说明相邻区间不重叠,如果不满足该情况,那肯定说明区间重叠。
这里的count表示的是重叠区间的个数。
end在此处仍然表示的是区间分割点。

if (intervals[i-1][0] >= intervals[i][1]) end = intervals[i][1];
else {count++; //记录我们重叠了多少个区间
}

如何判断一下一个区间与当前相邻区间是否重叠

要首先计算出之前我们判断的相邻区间的最小边界(左边界的最小值),和我们下一个区间的左边界是否重叠。

else {count++;end = min(end, intervals[i][1])
}

这里num[i][1]=min(nums[i-1][1], nums[i][1]),等到i遍历到下一个区间,应该和之前两个相邻区间的最小右边界比较,如果当前i区间的左边界要大的话,那么说明不是重叠区间。

总结

左边界的思想一句话就是:如果发现了重叠区间,我们就进行更新新的分割点,并且count++

CPP代码

class Solution {
public:static bool cmp (const vector<int>& a, const vector<int>& b) {return a[0] < b[0]; // 改为左边界排序}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 0; // 注意这里从0开始,因为是记录重叠区间int end = intervals[0][1]; // 记录区间分割点for (int i = 1; i < intervals.size(); i++) {   if (intervals[i][0] >= end)  end = intervals[i][1]; // 无重叠的情况else { // 重叠情况 end = min(end, intervals[i][1]);count++;}}return count;}
};# 精简版
class Solution {
public:static bool cmp (const vector<int>& a, const vector<int>& b) {return a[0] < b[0]; // 改为左边界排序}int eraseOverlapIntervals(vector<vector<int>>& intervals) {if (intervals.size() == 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count = 0; // 注意这里从0开始,因为是记录重叠区间for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) { //重叠情况intervals[i][1] = min(intervals[i - 1][1], intervals[i][1]);count++;}}return count;}
};

763.划分字母区间

力扣题目链接

文章链接:763.划分字母区间

视频链接:贪心算法,寻找最远的出现位置! LeetCode:763.划分字母区间

状态:

本题其实就是一句话“面多了加水,水多了加面,直到刚刚好”。

这里完全不是贪心的思路,就是全局的一个模拟,主要它也属于重叠区间的问题。

思路

思路上还是很难想到的。

我们在遍历过程中,相当于找到每一个字母出现的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了

所以分为如下两步:

  • 统计每个字符最后出现的位置
  • 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点

我们需要记录每个字符出现的最后位置,如图:

伪代码实现

  • 统计每一个字符最后出现的位置
int hash[27] = {0}; //i为字符,hash[i]为字符出现的最后位置
for (int i = 0; i < S.size(); ++i) {hash[S[i] - 'a'] = i;
}
  • 定义变量
vector<int> result;
int left = 0;
int right = 0;
  • 字符出现的最远边界的更新和结果存储
for (int i = 0; i < S.size(); i++) {right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界if (i == right) {result.push_back(right - left + 1);left = i + 1;}
}

CPP代码

class Solution {
public:vector<int> partitionLabels(string S) {int hash[27] = {0}; // i为字符,hash[i]为字符出现的最后位置for (int i = 0; i < S.size(); i++) { // 统计每一个字符最后出现的位置hash[S[i] - 'a'] = i;}vector<int> result;int left = 0;int right = 0;for (int i = 0; i < S.size(); i++) {right = max(right, hash[S[i] - 'a']); // 找到字符出现的最远边界if (i == right) {result.push_back(right - left + 1);left = i + 1;}}return result;}
};

56. 合并区间

力扣题目链接

文章链接:56. 合并区间

视频链接:贪心算法,合并区间有细节!LeetCode:56.合并区间

状态:

思路

本题同样也是重叠区间的问题。

区别在于判断区间重叠后的逻辑,本题是将重叠区间进行合并。

先排序,如果intervals[i][0] <= intervals[i - 1][1]就有重叠,所以进行合并

合并的逻辑也比较简单,

用合并区间后左边界和右边界,作为一个新的区间,加入到result数组里就可以了。如果没有合并就把原区间加入到result数组

CPP代码

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

这篇关于代码随想录算法训练营DAY36|C++贪心算法Part.5|435.无重叠区间、763.划分字母区间、56. 合并区间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/931980

相关文章

利用Python调试串口的示例代码

《利用Python调试串口的示例代码》在嵌入式开发、物联网设备调试过程中,串口通信是最基础的调试手段本文将带你用Python+ttkbootstrap打造一款高颜值、多功能的串口调试助手,需要的可以了... 目录概述:为什么需要专业的串口调试工具项目架构设计1.1 技术栈选型1.2 关键类说明1.3 线程模

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各