建站宝盒购买,静态网页制作代码html,网站后台 栏目管理,哈尔滨百度推广公司一、无重叠区间
题目一#xff1a;453. 无重叠区间
435. 无重叠区间
给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠 。 主要思想是优先保留结束时间早的区间#xff0c;这样…一、无重叠区间
题目一453. 无重叠区间
435. 无重叠区间
给定一个区间的集合 intervals 其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量使剩余区间互不重叠 。 主要思想是优先保留结束时间早的区间这样留给其他区间的空间就更多从而减少需要移除的区间数量。具体做法是先根据每个区间的结束时间进行排序然后遍历这些区间每次选择结束时间最早且与前一个选中的区间不重叠的区间。 /** lc appleetcode.cn id435 langcpp** [435] 无重叠区间*/// lc codestart
class Solution {
public:int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.empty()) return 0;sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b) {return a[1] b[1];});int count 0; int end intervals[0][1]; for (int i 1; i intervals.size(); i) {if (intervals[i][0] end) {count;} else {end intervals[i][1];}}return count;}
};
// lc codeend
二、划分字母区间
题目一763. 划分字母区间
763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。 基本思路是首先遍历字符串记录每个字符最后出现的位置。然后再次遍历字符串使用一个变量来跟踪当前片段的结束位置。如果在遍历过程中遇到的任何字符的最后出现位置超过了当前片段的结束位置就更新结束位置。一旦达到或超过当前片段的结束位置就可以确定一个片段并开始寻找下一个片段。 /** lc appleetcode.cn id763 langcpp** [763] 划分字母区间*/// lc codestart
class Solution {
public:vectorint partitionLabels(string s) {vectorint last(26, 0);int length s.length();for (int i 0; i length; i) {last[s[i] - a] i;}vectorint partition;int start 0, end 0;for (int i 0; i length; i) {end max(end, last[s[i] - a]);if (i end) {partition.push_back(end - start 1);start end 1;}}return partition;}
};
// lc codeend
三、合并区间
题目一56. 合并区间
56. 合并区间
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。 基本思路是先根据区间的起始位置进行排序然后遍历排序后的区间列表合并所有重叠的区间。 在这个算法中首先对区间按起始位置进行排序。然后遍历每个区间如果当前区间的起始位置大于已合并区间集合中最后一个区间的结束位置则说明当前区间与已合并区间集合中的区间不重叠可以直接添加到已合并区间集合中。如果有重叠则将已合并区间集合中最后一个区间的结束位置更新为当前区间的结束位置和已合并区间集合中最后一个区间的结束位置中的较大值。 /** lc appleetcode.cn id56 langcpp** [56] 合并区间*/// lc codestart
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {if (intervals.empty()) return {};sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b) {return a[0] b[0];});vectorvectorint merged;for (const auto interval : intervals) {if (merged.empty() || merged.back()[1] interval[0]) {merged.push_back(interval);} else {merged.back()[1] max(merged.back()[1], interval[1]);}}return merged;}
};
// lc codeend
