如何让一个网站排名掉,前端网页设计师,做科技公司的网站公司,怎么创建自己的网站平台本文章代码以c为例#xff01;
一、力扣第435题#xff1a;无重叠区间
题目#xff1a;
给定一个区间的集合 intervals #xff0c;其中 intervals[i] [starti, endi] 。返回 需要移除区间的最小数量#xff0c;使剩余区间互不重叠 。 示例 1:
输入: intervals [[1,…本文章代码以c为例
一、力扣第435题无重叠区间
题目
给定一个区间的集合 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] 来使剩下的区间没有重叠。示例 3:
输入: intervals [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间因为它们已经是无重叠的了。提示:
1 intervals.length 105intervals[i].length 2-5 * 104 starti endi 5 * 104
思路
相信很多同学看到这道题目都冥冥之中感觉要排序但是究竟是按照右边界排序还是按照左边界排序呢
其实都可以。主要就是为了让区间尽可能的重叠。
我来按照右边界排序从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
此时问题就是要求非交叉区间的最大个数。
这里记录非交叉区间的个数还是有技巧的如图 区间123456都按照右边界排好序。
当确定区间 1 和 区间2 重叠后如何确定是否与 区间3 也重贴呢
就是取 区间1 和 区间2 右边界的最小值因为这个最小值之前的部分一定是 区间1 和区间2 的重合部分如果这个最小值也触达到区间3那么说明 区间 123都是重合的。
接下来就是找大于区间1结束位置的区间是从区间4开始。那有同学问了为什么不从区间5开始别忘了已经是按照右边界排序的了。
区间4结束之后再找到区间6所以一共记录非交叉区间的个数是三个。
总共区间个数为6减去非交叉区间的个数3。移除区间的最小数量就是3。
C代码如下
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;}
};时间复杂度O(nlog n) 有一个快排空间复杂度O(n)有一个快排最差情况(倒序)时需要n次递归调用。因此确实需要O(n)的栈空间
大家此时会发现如此复杂的一个问题代码实现却这么简单
# 补充
# 补充1
左边界排序可不可以呢
也是可以的只不过 左边界排序我们就是直接求 重叠的区间count为记录重叠区间数。
class Solution {
public:static bool cmp (const vectorint a, const vectorint b) {return a[0] b[0]; // 改为左边界排序}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count 0; // 注意这里从0开始因为是记录重叠区间int end intervals[0][1]; // 记录区间分割点for (int i 1; i intervals.size(); i) { if (intervals[i][0] end) end intervals[i][1]; // 无重叠的情况else { // 重叠情况 end min(end, intervals[i][1]);count;}}return count;}
};其实代码还可以精简一下 用 intervals[i][1] 替代 end变量只判断 重叠情况就好
class Solution {
public:static bool cmp (const vectorint a, const vectorint b) {return a[0] b[0]; // 改为左边界排序}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int count 0; // 注意这里从0开始因为是记录重叠区间for (int i 1; i intervals.size(); i) {if (intervals[i][0] intervals[i - 1][1]) { //重叠情况intervals[i][1] min(intervals[i - 1][1], intervals[i][1]);count;}}return count;}
};
# 补充2
本题其实和452.用最少数量的箭引爆气球
(opens new window)非常像弓箭的数量就相当于是非交叉区间的数量只要把弓箭那道题目代码里射爆气球的判断条件加个等号认为[01][12]不是相邻区间然后用总区间数减去弓箭数量 就是要移除的区间数量了。
把452.用最少数量的箭引爆气球
(opens new window)代码稍做修改就可以AC本题。
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 result 1; // points 不为空至少需要一支箭for (int i 1; i intervals.size(); i) {if (intervals[i][0] intervals[i - 1][1]) {result; // 需要一支箭}else { // 气球i和气球i-1挨着intervals[i][1] min(intervals[i - 1][1], intervals[i][1]); // 更新重叠气球最小右边界}}return intervals.size() - result;}
};这里按照 左边界排序或者按照右边界排序都可以AC原理是一样的。
class Solution {
public:// 按照区间左边界排序static bool cmp (const vectorint a, const vectorint b) {return a[0] b[0]; // 左边界排序}int eraseOverlapIntervals(vectorvectorint intervals) {if (intervals.size() 0) return 0;sort(intervals.begin(), intervals.end(), cmp);int result 1; // points 不为空至少需要一支箭for (int i 1; i intervals.size(); i) {if (intervals[i][0] intervals[i - 1][1]) {result; // 需要一支箭}else { // 气球i和气球i-1挨着intervals[i][1] min(intervals[i - 1][1], intervals[i][1]); // 更新重叠气球最小右边界}}return intervals.size() - result;}
};
二、力扣第763题划分字母区间
题目
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段同一字母最多出现在一个片段中。
注意划分结果需要满足将所有划分结果按顺序连接得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。 示例 1
输入s ababcbacadefegdehijhklij
输出[9,7,8]
解释
划分结果为 ababcbaca、defegde、hijhklij 。
每个字母最多出现在一个片段中。
像 ababcbacadefegde, hijhklij 这样的划分是错误的因为划分的片段数较少。
示例 2
输入s eccbbbbdec
输出[10]提示
1 s.length 500s 仅由小写英文字母组成
思路
一想到分割字符串就想到了回溯但本题其实不用回溯去暴力搜索。
题目要求同一字母最多出现在一个片段中那么如何把同一个字母的都圈在同一个区间里呢
如果没有接触过这种题目的话还挺有难度的。
在遍历的过程中相当于是要找每一个字母的边界如果找到之前遍历过的所有字母的最远边界说明这个边界就是分割点了。此时前面出现过所有字母最远也就到这个边界了。
可以分为如下两步
统计每一个字符最后出现的位置从头遍历字符并更新字符的最远出现下标如果找到字符最远出现位置下标和当前下标相等了则找到了分割点
如图 明白原理之后代码并不复杂如下
class Solution {
public:vectorint partitionLabels(string S) {int hash[27] {0}; // i为字符hash[i]为字符出现的最后位置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;}
};时间复杂度O(n)空间复杂度O(1)使用的hash数组是固定大小
# 总结
这道题目leetcode标记为贪心算法说实话我没有感受到贪心找不出局部最优推出全局最优的过程。就是用最远出现距离模拟了圈字符的行为。
但这道题目的思路是很巧妙的所以有必要介绍给大家做一做感受一下。
# 补充
这里提供一种与452.用最少数量的箭引爆气球
(opens new window)、435.无重叠区间
(opens new window)相同的思路。
统计字符串中所有字符的起始和结束位置记录这些区间(实际上也就是435.无重叠区间 (opens new window)题目里的输入)将区间按左边界从小到大排序找到边界将区间划分成组互不重叠。找到的边界就是答案。
class Solution {
public:static bool cmp(vectorint a, vectorint b) {return a[0] b[0];}// 记录每个字母出现的区间vectorvectorint countLabels(string s) {vectorvectorint hash(26, vectorint(2, INT_MIN));vectorvectorint hash_filter;for (int i 0; i s.size(); i) {if (hash[s[i] - a][0] INT_MIN) {hash[s[i] - a][0] i;}hash[s[i] - a][1] i;}// 去除字符串中未出现的字母所占用区间for (int i 0; i hash.size(); i) {if (hash[i][0] ! INT_MIN) {hash_filter.push_back(hash[i]);}}return hash_filter;}vectorint partitionLabels(string s) {vectorint res;// 这一步得到的 hash 即为无重叠区间题意中的输入样例格式区间列表// 只不过现在我们要求的是区间分割点vectorvectorint hash countLabels(s);// 按照左边界从小到大排序sort(hash.begin(), hash.end(), cmp);// 记录最大右边界int rightBoard hash[0][1];int leftBoard 0;for (int i 1; i hash.size(); i) {// 由于字符串一定能分割因此,// 一旦下一区间左边界大于当前右边界即可认为出现分割点if (hash[i][0] rightBoard) {res.push_back(rightBoard - leftBoard 1);leftBoard hash[i][0];}rightBoard max(rightBoard, hash[i][1]);}// 最右端res.push_back(rightBoard - leftBoard 1);return res;}
};三、力扣第56题合并区间
题目
以数组 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] 可被视为重叠区间。 提示
1 intervals.length 104intervals[i].length 20 starti endi 104
思路
本题的本质其实还是判断重叠区间问题。
大家如果认真做题的话话发现和我们刚刚讲过的452. 用最少数量的箭引爆气球
(opens new window) 和 435. 无重叠区间
(opens new window) 都是一个套路。
这几道题都是判断区间重叠区别就是判断区间重叠后的逻辑本题是判断区间重贴后要进行区间合并。
所以一样的套路先排序让所有的相邻区间尽可能的重叠在一起按左边界或者右边界排序都可以处理逻辑稍有不同。
按照左边界从小到大排序之后如果 intervals[i][0] intervals[i - 1][1] 即intervals[i]的左边界 intervals[i - 1]的右边界则一定有重叠。本题相邻区间也算重贴所以是
这么说有点抽象看图注意图中区间都是按照左边界排序之后了 知道如何判断重复之后剩下的就是合并了如何去模拟合并区间呢
其实就是用合并区间后左边界和右边界作为一个新的区间加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
C代码如下
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {vectorvectorint result;if (intervals.size() 0) return result; // 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b){return a[0] b[0];});// 第一个区间就可以放进结果集里后面如果重叠在result上直接合并result.push_back(intervals[0]); for (int i 1; i intervals.size(); i) {if (result.back()[1] intervals[i][0]) { // 发现重叠区间// 合并区间只更新右边界就好因为result.back()的左边界一定是最小值因为我们按照左边界排序的result.back()[1] max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠 }}return result;}
};时间复杂度: O(nlogn)空间复杂度: O(logn)排序需要的空间开销 day36补
