第三十六天| 435. 无重叠区间、763.划分字母区间、56. 合并区间

2024-02-20 05:04

本文主要是介绍第三十六天| 435. 无重叠区间、763.划分字母区间、56. 合并区间,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Leetcode 435. 无重叠区间

题目链接:435 无重叠区间

题干:给定一个区间的集合 intervals ,其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量,使剩余区间互不重叠 

思考:贪心法。和452 用最少数量的箭引爆气球原理类似。按照左边界排序,从左向右记录多余交叉区间的个数。或者按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间的个数。

此图先按右边界排序,之后记录非交叉区间的个数还是有技巧的。取 区间1 和 区间2 右边界的最小值,因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分,如果这个最小值也触达到区间3,那么说明 区间 1,2,3都是重合的。

代码一(按右边界排序):

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 (intervals[i][0] >= intervals[i - 1][1])count++;elseintervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);        //更新重叠区间右边界}return intervals.size() - 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 result = 0;     //记录多余重叠区间个数for (int i = 1; i < intervals.size(); i++) {if (intervals[i][0] < intervals[i - 1][1]) {        //存在重叠区间intervals[i][1] = min(intervals[i][1], intervals[i - 1][1]);        //更新重叠区间右边界result++;}}return result;}
};

Leetcode 763.划分字母区间

题目链接:763 划分字母区间

题干:给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。

注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

  • 1 <= s.length <= 500
  • s 仅由小写英文字母组成

思考:贪心法。先寻找所有字母的最后出现的下标位置,和其首次出现的位置形成区间。接下来将重叠的区间合并起来,并记录每个不重叠区间的大小。由于按顺序遍历字符串因此在合并区间时只需要更新右边界,在不重叠时初始化新区间的边界。

代码:

class Solution {
public:vector<int> partitionLabels(string s) {int lastPresence[27] = { 0 };       //记录所有字母最后出现的下标位置for (int i = 0; i < s.size(); i++)      lastPresence[s[i] - 'a'] = i;int left = 0;       //记录区间的左边界int right = 0;      //记录区间的右边界vector<int> result;for (int i = 0; i < s.size(); i++) {right = max(right, lastPresence[s[i] - 'a']);       //更新当前区间右边界if (i == right) {result.push_back(right - left + 1);left = i + 1;       //新区间左边界}}return result;}
};

Leetcode 56. 合并区间

题目链接:56 合并区间

题干:以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

思考:贪心法。本题和435. 无重叠区间非常相似,都是先排序后再处理。区别:处理过程中如果记录区间和当前处理区间存在重叠,则更新记录区间的右边界,否则记录当前处理区间。

代码:

class Solution {
public:static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0];     //按左区间排序}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0)  return result;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]);     //将首个区间放入结果集,后面出现重叠则修改右边界for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0])result.back()[1] = max(result.back()[1], intervals[i][1]);      //更新重叠区间右边界elseresult.push_back(intervals[i]);     //区间不重叠则加入新区间}return result;}
};

自我总结:

  • 逐步理解贪心法处理区间问题,排序+特殊处理。

这篇关于第三十六天| 435. 无重叠区间、763.划分字母区间、56. 合并区间的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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

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 (

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

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

Thread如何划分为Warp?

1 .Thread如何划分为Warp? https://jielahou.com/code/cuda/thread-to-warp.html  Thread Index和Thread ID之间有什么关系呢?(线程架构参考这里:CUDA C++ Programming Guide (nvidia.com)open in new window) 1维的Thread Index,其Thread

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点