history Docker java设计模式 idea Markdown events methods ros 打印 autocomplete menu bower 郑州网站建设 webpack视频 pmp视频教程下载 linux内存管理 jquery延时 pytorch安装教程 oracle自增长 移动端上传图片插件 mysql组合索引 js数组截取前5个 linux启动数据库 mysql删除表 python输入输出 python查找指定字符 javascanner java数据库 java使用正则表达式 java的socket通信 mathcad下载 mac地址修改器 pyh 在线手册 奥法隐藏外观 还原软件哪个好 虚拟声卡驱动 金水疑云 氤氲之息哪里爆率高 语音转文字转换器 ps怎么做漂亮艺术字
当前位置: 首页 > 学习教程  > 编程语言

leetcode57. 插入区间

2020/11/4 14:56:09 文章标签:

文章目录题目:57. 插入区间基本思想:遍历的同时进行区间合并题目:57. 插入区间 给出一个无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠&#xff08…

文章目录

    • 题目:57. 插入区间
    • 基本思想:遍历的同时进行区间合并

题目:57. 插入区间

给出一个无重叠的 ,按照区间起始端点排序的区间列表。

在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

示例 1:

输入:intervals = [[1,3],[6,9]], newInterval = [2,5]
输出:[[1,5],[6,9]]

示例 2:

输入:intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出:[[1,2],[3,10],[12,16]]
解释:这是因为新的区间 [4,8][3,5],[6,7],[8,10] 重叠

注意:输入类型已在 2019 年 4 月 15 日更改。请重置为默认代码定义以获取新的方法签名。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/insert-interval
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

基本思想:遍历的同时进行区间合并

这道题思想上倒不难,有一些小细节需要考虑到。

将当前区间分为几种情况进行处理。

  • 新增区间小于当前区间,例如:[4,8] ,[1,2](新增区间),直接将新增区间插入到结果中,然后依次将后续的区间插入结果中
  • 新增区间包含在当前区间中,例如:[4,8] ,[3,6](新增区间),直接返回给定区间
  • 新增区间需要和当前区间合并,这里需要分两种判断情况,新增区间在前还是当前区间在前。
    例如1:新增区间在前,[4,8],[0,5](新增区间),判断条件是保证5在4和8之间
    例如2:当前区间在后,[4,8],[5,10](新增区间),判断条件是保证5在4和8之间
    合并后,再依次判断接下来的区间和已处理的区间是否有重叠

特别注意:整个过程需要标记下新增区间是否已处理,未处理需要增加到结果中

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> res;
        bool flag = false;//用来标记新增区间是否处理
        for(int i = 0; i < intervals.size(); ++i){
            //新增区间不重叠,直接将新增区间加入结果中,然后将后续区间依次加入结果中
            if(newInterval[1] < intervals[i][0]){
                flag = true;
                res.push_back(newInterval);
                int j = i;
                while(j < intervals.size()){
                    res.push_back(intervals[j]);
                    ++j;
                }
                return res;
            }
            //新增区间包含在当前区间中
            if(newInterval[0] >= intervals[i][0] && newInterval[1] <= intervals[i][1]){
                return intervals;
            }
            //新增区间需要和当前区间合并
            if((newInterval[0] <= intervals[i][1] && newInterval[1] >= intervals[i][0]) || (newInterval[1] >= intervals[i][0] && newInterval[1] <= intervals[i][1])){
                flag = true;
                res.push_back({min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])});
                //依次判断后面的区间是否和res中的最后一个区间合并
                int j = i + 1;
                while(j < intervals.size()){
                    if(intervals[j][0] <= res.back()[1]){//合并
                        res.back()[1] = max(res.back()[1], intervals[j][1]);
                    }
                    else{
                        res.push_back(intervals[j]);
                    }
                    ++j;
                }
                return res;
            }
            //新增区间大于当前区间,需要将当前区间放在结果中
            if(newInterval[0] > intervals[i][1]){
                res.push_back(intervals[i]);
            }
        }
        if(!flag){
            res.push_back(newInterval);
        }
        return res;
    }
};

思想类似,但是更简洁:

  • 当前区间在插入区间的左侧,直接将当前区间插入结果中即可
  • 当前区间在插入区间的右侧,需要判断下插入区间是否已插入,如果未插入则将其插入,并将当前区间插入
  • 当前区间和插入区间有交集,则需更新插入区间为当前区间和插入区间的并集

特别注意:这里flag的作用是保证新增区间插入到结果中并且只插入一次

class Solution:
    def insert(self, intervals: List[List[int]],
               newInterval: List[int]) -> List[List[int]]:
        flag = False
        res = []
        for interval in intervals:
            # 在插入区间的右侧,且没有交集,这里需要判断下新增区间是否已插入到结果中
            if interval[0] > newInterval[1]:
                if not flag:
                    res.append(newInterval)
                    flag = True
                res.append(interval)

            # 在插入区间的左侧
            elif interval[1] < newInterval[0]:
                res.append(interval)

            # 需要和插入区间合并
            else:
                newInterval[0] = min(newInterval[0], interval[0])
                newInterval[1] = max(newInterval[1], interval[1])

        if not flag:
            res.append(newInterval)

        return res


本文链接: http://www.dtmao.cc/news_show_350284.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?