佛山做网站公司,网站顶部小图标怎么做,wordpress注册相关,百度app旧版本下载文章目录 Leetcode 435. 无重叠区间Leetcode 763.划分字母区间Leetcode 56. 合并区间 Leetcode 435. 无重叠区间
题目链接#xff1a; Leetcode 435. 无重叠区间 题目描述#xff1a; 给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回需… 文章目录 Leetcode 435. 无重叠区间Leetcode 763.划分字母区间Leetcode 56. 合并区间 Leetcode 435. 无重叠区间
题目链接 Leetcode 435. 无重叠区间 题目描述 给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回需要移除区间的最小数量使剩余区间互不重叠 。 思路 本题需要求移除区间最小值由于要移除最小个数的区间因此我们首先要让集合内区间尽可能重叠然后统计重叠区间数量 解题步骤
先对集合根据左区间排序右区间也可以遍历集合遇到重叠区间之后根据当前集合与上一个集合二者的右区间最小值来更新。
为什么需要用最小值来更新集合右区间假设当前遍历集合为i由于我们已经判断了i和i-1存在重叠区间该重叠区间后续称为O接下来需要判断i1与O是否存在重叠区间因此需要根据O的右区间也就是i与i-1右区间最小值。
代码如下
class Solution {
public://根据左区间排序static bool cmp(const vectorint a, const vectorint b) {return a[0] b[0];}int eraseOverlapIntervals(vectorvectorint intervals) {int cnt 0;if (intervals.size() 0)return 0;sort(intervals.begin(), intervals.end(), cmp);for (int i 1; i intervals.size(); i) {if (intervals[i][0] intervals[i - 1][1]) {//如果存在重叠区间cnt;//更新当前集合的右区间(方便接下来判断是否重叠)intervals[i][1] min(intervals[i - 1][1], intervals[i][1]);}}return cnt;}
};时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度 O ( n ) O(n) O(n),主要取决于快排所用的栈空间这是最坏情况最好情况是 O ( l o g n ) O(logn) O(logn)
Leetcode 763.划分字母区间
题目链接 Leetcode 763.划分字母区间 题目描述 给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
思路 首先遍历字符串寻找每个字母的最远边界由于本题哈希表长度确定且较小因此可以利用数组模拟哈希表。 解题步骤
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
代码如下
class Solution {
public:vectorint partitionLabels(string s) {int hash[27] {0};for (int i 0; i s.size(); i) { // 统计每一个字符最后出现的位置hash[s[i] - a] i;}vectorint result;int left 0, 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 right 1;}}return result;}
};时间复杂度 O ( n ) O(n) O(n)空间复杂度 O ( 1 ) O(1) O(1)
Leetcode 56. 合并区间
题目链接 Leetcode 56. 合并区间 题目描述 以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。 思路 首先判断区间是否重叠如果重叠则更新右区间如何更新右区间以及原因看这里的解释Leetcode 435. 无重叠区间如果不重叠则加入结果。 代码如下
class Solution {
public:static bool cmp(const vectorint a, const vectorint b) {return a[0] b[0];}vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;sort(intervals.begin(), intervals.end(), cmp);result.push_back(intervals[0]);for (int i 1; i intervals.size(); i) {if (intervals[i][0] result.back()[1]) {//发现重叠区间就更新右边界result.back()[1] max(intervals[i][1], result.back()[1]);} else {result.push_back(intervals[i]);}}return result;}
};时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)空间复杂度: O ( n ) O(n) O(n),主要取决于快排所用的栈空间这是最坏情况最好情况是 O ( l o g n ) O(logn) O(logn) 总结 今天的第二道题Leetcode 763.划分字母区间这种思路值得学习一下。剩下两道题是有关重叠区间的问题理解思路之后并不难。
最后如果文章有错误请在评论区或私信指出让我们共同进步
