代码随想录算法训练营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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa