网站做推广页需要什么软件下载,顺企网黄页企业,做建材网站怎么做,游戏推广代理app文档讲解#xff1a;无重叠区间 划分字母区间 合并区间 435.无重叠区间
题目链接#xff1a;https://leetcode.cn/problems/non-overlapping-intervals/description/
思路#xff1a; 按照右边界排序#xff0c;从左向右记录非交叉区间的个数。最后用区间总数减去非交叉… 文档讲解无重叠区间 划分字母区间 合并区间 435.无重叠区间
题目链接https://leetcode.cn/problems/non-overlapping-intervals/description/
思路 按照右边界排序从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。此时问题就是要求非交叉区间的最大个数。
核心代码
class Solution {
public:static bool cmp (const vectorint a, const vectorint b) {return a[1] b[1];}int eraseOverlapIntervals(vectorvectorint 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 (end intervals[i][0]) {end intervals[i][1];count;}}return intervals.size() - count;}
};
763.划分字母区间
题目链接https://leetcode.cn/problems/partition-labels/description/
思路 一想到分割字符串就想到了回溯但本题其实不用回溯去暴力搜索。 题目要求同一字母最多出现在一个片段中那么如何把同一个字母的都圈在同一个区间里呢 在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。 可以分为如下两步 1.统计每一个字符最后出现的位置。 2.从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点。
核心代码
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;int 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 i 1;}}return result;}
};
56.合并区间
题目链接https://leetcode.cn/problems/merge-intervals/description/
思路 先排序让所有的相邻区间尽可能的重叠在一起按左边界或者右边界排序都可以处理逻辑稍有不同。 按照左边界从小到大排序之后如果 intervals[i][0] intervals[i - 1][1] 即intervals[i]的左边界 intervals[i - 1]的右边界则一定有重叠。本题相邻区间也算重贴所以是 知道如何判断重复之后剩下的就是合并了如何去模拟合并区间呢 其实就是用合并区间后左边界和右边界作为一个新的区间加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
核心代码
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;if (intervals.size() 0) return result;sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b){return a[0] b[0];});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]); } else {result.push_back(intervals[i]);}}return result;}
};今日总结 今日学习时长2h基本是看的题解没时间做了学了下思路这几天忙着别的事放到周末去总结回顾吧明天估计也得这样。
