广东新闻联播2020,sem对seo的影响有哪些,定制网站建设推广方案,国家市场监督管理435. 无重叠区间 - 力扣#xff08;LeetCode#xff09;
给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠 。
示例 1:
输入: intervals [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解…435. 无重叠区间 - 力扣LeetCode
给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。
示例 1:
输入: intervals [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后剩下的区间没有重叠。示例 2:
输入: intervals [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
思路明确一点如果前一个数组的右边界大于后一个数组的左边界就算重叠利用这个统计不重叠的数组个数剩下的就是重叠的个数。
解决首先需要对intervals排序以每个数组的右边界排序再将第一个数组的右边界作为起始点循环比较前数组的右边界和后数组的左边界。最后用全部数组个数减去统计的不重叠个数就是需要移除的数组个数。
代码
class Solution {
public:static bool cmp (vectorint a,vectorint b){return a[1]b[1];}int eraseOverlapIntervals(vectorvectorint intervals) {if(intervals.size()0) return 0;sort(intervals.begin(),intervals.end(),cmp);int r1;int endintervals[0][1];for(int i1;iintervals.size();i){if(endintervals[i][0]){endintervals[i][1];r;}}return intervals.size()-r;}
};
763. 划分字母区间 - 力扣LeetCode
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1
输入s ababcbacadefegdehijhklij
输出[9,7,8]
解释
划分结果为 ababcbaca、defegde、hijhklij 。
每个字母最多出现在一个片段中。
像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。
思路把同一字母最多出现在一个片段中相当是找一个范围包含所有的之前出现过的字母这个范围应该尽可能小。
解决先统计每个字母最后出现的位置再依次遍历每个元素更新当前已经遍历过的元素中最远边界如果当前元素的最后出现的位置小于最远边界说明目前范围没有包含所有元素。直达字符最远出现位置下标和当前下标相等了则找到了。找到以后记录当前遍历的范围个数,right-left1同时更新范围的左边界lefti1
代码
class Solution {
public:vectorint partitionLabels(string s) {int h[27]{0};for(int i0;is.size();i){int nums[i] - a;h[num]i;}vectorint r;int right0;int left0;for(int i0;is.size();i){rightmax(right,h[s[i] - a] );if(iright){r.push_back(right-left1);lefti1;}}return r;}
};
56. 合并区间 - 力扣LeetCode
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
示例 1
输入intervals [[1,3],[2,6],[8,10],[15,18]]
输出[[1,6],[8,10],[15,18]]
解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2
输入intervals [[1,4],[4,5]]
输出[[1,5]]
解释区间 [1,4] 和 [4,5] 可被视为重叠区间。
思路明确什么情况下两个区间可以合并①前一个数组的右边界在后一个数组左右边界之内②两个数组存在包含关系。之后合并的区间左右边界数值也会因情况不同而改变。
解决首先按照数组的左边界排序再比较前数组后边界和后数组的前边界如果包含就就将后数组的后边界和前数组前边界当成合成的区间如果不包含当前数组没有其他数组包含它直接加入结果数组。
代码
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint r;if(intervals.size()0) return r;sort(intervals.begin(),intervals.end(),[](const vectorint a,const vectorint b){return a[0]b[0];//按左边界排序});r.push_back(intervals[0]);for(int i1;iintervals.size();i){if(r.back()[1]intervals[i][0]){//前数组右边界大于后数组左边界,r.back()[1]取r中最后一维数组的右边界r.back()[1]max(r.back()[1],intervals[i][1]);//更新当前合并区间的右边界}else{r.push_back(intervals[i]);}}return r;}};
