代码随想录训练营Day 38|力扣435. 无重叠区间、763.划分字母区间、56. 合并区间

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

1.无重叠区间

代码随想录

代码:(贪心算法)

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){if(a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {int result = 0;if(intervals.size() == 1) return 0;sort(intervals.begin(),intervals.end(),cmp);for(int i = 1;i < intervals.size();i++){if(intervals[i - 1][1] > intervals[i][0]){result++;intervals[i][1] = min(intervals[i - 1][1],intervals[i][1]);}}return result;}
};

 思路:

        这道题和我昨天做的用最少的箭引爆气球的题很像。都是按照左边界排序,然后去判断当前区间的左边界有没有小于前一个结点的有边界,如果有,就说明这两个区间重叠。当然也可能后续的很多区间都重叠了,因此,这里把当前区间的右边界赋值为min(当前区间的右边界,前一个区间的右边界),然后继续循环就好了。代码随想录训练营Day 37|力扣860.柠檬水找零、406.根据身高重建队列、452. 用最少数量的箭引爆气球-CSDN博客

        上一题问的是最少数量的箭,因此我们是把它初始化为1.然后在区间不重叠的时候++。 本题是求有多少给重叠区间,所以我们把它初始化为0,在区间重叠的时候++。

        (本题如果前后两个区间紧挨着——也就是前一个区间的右边界=当前区间的左边界,算作不重叠,我这里就错了

2.划分字母区间

代码随想录

代码: (贪心算法+哈希法)

class Solution {
public:vector<int> partitionLabels(string s) {int hash[27] = {0};// 统计每个字母出现的最远的下标for(int i = 0;i < s.size();i++){hash[s[i] - 'a'] = i;}// 找分界线——分界线的下标=当前遍历过的字母出现的最远下标int index = 0;int pre = 0;vector<int> result;for(int i = 0;i < s.size();i++){index = max(index,hash[s[i] - 'a']);if(i == index){result.push_back(index - pre + 1);pre = index + 1;}}return result;}
};

 思路:

具体步骤是什么? 

先把所有字母的最远下标映射到hash表里,然后再去找分界线——满足此时的下标 = 我们已经遍历过的所有字母的最远下标值。

这道题怎么体现贪心的思路的?

局部最优:尽可能少得控制划分区间的长度;全局最优:得到最多的区间数

有什么细节要注意?

这道题,我在边界问题上摔跟头了。我用pre来表示区间的左边界,index来表示区间的有边界——区间是左闭右闭的!!所以,我在收集完一个区间后,pre应该赋值为index+1!! 

3.合并区间

代码随想录

代码:(贪心算法)

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){if(a[0] == b[0]) return a[1] < b[1];return a[0] < b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);vector<vector<int>> result;// 题上已经说了intervals最少有一个元素// result初始化result.push_back(intervals[0]);for(int i = 1;i < intervals.size();i++){if(result.back()[1] >= intervals[i][0]){ // 重叠区间时,在result里直接进行合并result.back()[1] = max(intervals[i][1],result.back()[1]);}else{result.push_back(intervals[i]); // 不重叠时,直接把当前的区间加入结果}}return result;}
};

 思路:

这道题也是求重叠区间,可是我感觉什么合并很复杂,合并后原来的数组下标是不是还要改变?

是的呢,所以,我直接对result里收集的数组进行融合操作。

这道题的重叠区间的判断,为什么不是取右边界的最小值了?

因为这道题要的是“合并”,两个区间重叠后合并,是要找它们的最大的边界范围的。而后续判断能否合并,则是看你“合并”后的上一个区间和现在你遍历的区间有没有重叠。 

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



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

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

poj 2104 and hdu 2665 划分树模板入门题

题意: 给一个数组n(1e5)个数,给一个范围(fr, to, k),求这个范围中第k大的数。 解析: 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码: poj 2104: #include <iostream>#include <cstdio>#include <cstdlib>#include <al

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip