模板建站和仿站,wordpress主题demo导入,专做海岛游的网站,做fitting的网站一些关于区间的力扣题目 228. 汇总区间56. 合并区间57. 插入区间 228. 汇总区间
题目链接#xff1a;228.汇总区间 题目内容#xff1a; 看题目真是没懂这个题到底是要干啥……实际上题目要求的恰好覆盖数组中所有数字的最小有序区间范围列表#xff0c;这个最小是指一个区… 一些关于区间的力扣题目 228. 汇总区间56. 合并区间57. 插入区间 228. 汇总区间
题目链接228.汇总区间 题目内容 看题目真是没懂这个题到底是要干啥……实际上题目要求的恰好覆盖数组中所有数字的最小有序区间范围列表这个最小是指一个区间范围小。比如能够覆盖{2,3,4,6}的区间可以是[2,6]但是5在区间内却不在数组内因此这个区间不是最小的可以缩小成[2,4]和[6,6]这才是满足题意恰好覆盖所有数字的最小区间。 理解题意后解法就很简单了为了保证区间能够覆盖所有数组中的数字同时又不存在在区间内但不在数组内的数字那就只能考虑用数组内的连续数字来组成区间。什么意思呢就是把数组内连续的数字组成一个区间单独的数字单独一个区间。比如上面的{2,3,4,6}其中{2,3,4}就是连续的组成一个区间[2,4]6是单独的需要一个区间[6, 6]。由于数组本身是有序的那么就找连续递增的数字组成一个区间nums[j] nums[j-1]。 代码如下C
class Solution {
public:vectorstring summaryRanges(vectorint nums) {vectorstring ans;int start 0, end 1;while(end nums.size()){//end是连续区间结束后的数字if(end nums.size() || nums[end] ! nums[end - 1] 1){if(start end - 1)//如果start和end-1相等说明这是只有一个数字的独立区间ans.emplace_back(to_string(nums[start]));else//start到end-1是连续区间ans.emplace_back(to_string(nums[start])-to_string(nums[end-1]));start end; //下一段区间的开始 }end; }return ans;}
};56. 合并区间
题目链接56. 合并区间 题目内容 先看看给的例子理解题意 题目要求我们合并重叠的区间那什么算是重叠的区间呢在区间是按照左端点升序排序的前提下前面一个区间d1的右端点与后面一个区间d2的左端点有交集即d1.right ≥ d2.left就说明两个区间重叠至于d2.right与d1.right的大小关系是不重要的 d1和d2有交集将两个区间合并成[ min(d1.leftd2.left)max(d1.rightd2.right) ]。 所以首先要做的是将区间数组按照区间的左端点排序之后开始判断前后两个区间是否有重叠。判断是否重叠只需要将答案区间数组中最后一个区间和待加入的区间比较因为当前答案数组的最后一个区间的left是比待加入的区间left更小的答案区间数组中的区间是没有重叠的那么答案数组中的最后一个区间的left肯定是大于再前面一个区间的right的待加入区间的left肯定是比答案数组中倒数第二个区间的right更大的。代码如下C
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {if(intervals.size() 0)return intervals;sort(intervals.begin(), intervals.end()); //排序左端点升序vectorvectorint ans; //最终无重叠的区间数组for(int i 0; i intervals.size(); i){//对于第一个区间和不重叠的区间直接加入if(ans.size() 0 || ans.back()[1] intervals[i][0])ans.emplace_back(intervals[i]);else//有重叠的区间最后一个区间的right要修改为两个重叠区间更大的rightans.back()[1] max(intervals[i][1], ans.back()[1]);}return ans;}
};57. 插入区间
题目链接57. 插入区间 题目内容 这道题其实和上一题是差不多的。给的区间已经按照左端点排序好了先查找到待插入的区间应该插入的位置然后插入再合并重叠的区间即可。如果一个区间d.right newin.left的话很显然这个区间d是和newin是不重叠的在其左边如果一个区间d.left newin.right的话很显然这个区间d在其右边是不重叠的。除上述两种情况外那就是有重叠的部分和一个区间重叠后合并的区间left min(newin.leftd.left)只有第一个开始重叠的地方需要更新left之后right max(newin.rightd.right)。以下例举了部分情况 实际上还有在最前面、最后面插入的情况不需要额外讨论一样按照上述三种情况去判断就好了最前面和最后面只是插入的位置和重叠位置有些特殊。实现代码如下C
class Solution {
public:vectorvectorint insert(vectorvectorint intervals, vectorint newInterval) {vectorvectorint ans;int idx 0;//先把在插入区间左边的区间直接加入答案数组中while(idx intervals.size() intervals[idx][1] newInterval[0]){ans.emplace_back(intervals[idx]);idx;}//如果已经在最后了或者是空的直接插入if(idx intervals.size()) {ans.emplace_back(newInterval);return ans;}//否则idx对应的区间和待插入区间是有重叠的更新leftelse{newInterval[0] min(intervals[idx][0], newInterval[0]);}//开始查找重叠部分直到找到在待插入区间右边的区间while(idx intervals.size() intervals[idx][0] newInterval[1]){ //有重叠就更新right newInterval[1] max(intervals[idx][1], newInterval[1]); idx; } //插入区间ans.emplace_back(newInterval);//之后的区间全在待插入区间的右边直接加入while(idx intervals.size())ans.emplace_back(intervals[idx]);return ans;}
};
