leetcode第57题

2022-09-26 90

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 和上一道可以说是一个问题，只不过这个是给一个已经合并好的列表，然后给一个新的节点依据规则加入到合并好的列表。解法一对应 56 题的解法一，没看的话，可以先过去看一下。这个问题其实就是我们解法中的一个子问题没看的话，可以先过去看一下。这个问题其实就是我们解法中的一个子问题，所以直接加过来就行了

和上一道可以说是一个问题，只不过这个是给一个已经合并好的列表，然后给一个新的节点依据规则加入到合并好的列表。

解法一

对应 56 题的解法一，没看的话，可以先过去看一下。这个问题其实就是我们解法中的一个子问题没看的话，可以先过去看一下。这个问题其实就是我们解法中的一个子问题，

所以直接加过来就行了

publicList<Interval>insert(List<Interval>intervals, IntervalnewInterval) { 
Intervalstart=null;
Intervalend=null;
inti_start=newInterval.start;
inti_end=newInterval.end;
intsize=intervals.size();
List<Interval>in=newArrayList<>(); 
//遍历合并好的列表for (intj=0; j<size; j++) {
if (i_start>=intervals.get(j).start&&i_start<=intervals.get(j).end) {
start=intervals.get(j);
                }
if (i_end>=intervals.get(j).start&&i_end<=intervals.get(j).end) {
end=intervals.get(j);
                }
if (i_start<intervals.get(j).start&&i_end>intervals.get(j).end) {
in.add(intervals.get(j));
                } 
            }
if (in.size() !=0) { 
for (intindex=0; index<in.size(); index++) {
intervals.remove(in.get(index));
                } 
            }
Intervalinterval=null;
//根据不同的情况，生成新的节点if (equals(start, end)) {
ints=start==null?i_start : start.start;
inte=end==null?i_end : end.end;
interval=newInterval(s, e); 
            } elseif (start!=null&&end!=null) {
interval=newInterval(start.start, end.end); 
            }elseif (start==null) {
interval=newInterval(i_start, i_end); 
            }
if (start!=null) {
intervals.remove(start);
            }
if (end!=null) {
intervals.remove(end);
            }
//不同之处是生成的节点，要遍历原节点，根据 start 插入到对应的位置，虽然题目没说，但这里如果不按顺序插入的话，leetcode 过不了。for(inti=0;i<intervals.size();i++){
if(intervals.get(i).start>interval.start){
intervals.add(i,interval);
returnintervals;
                }
            }
intervals.add(interval);
returnintervals;
        }
privatebooleanequals(Intervalstart, Intervalend) { 
if (start==null&&end==null) {
returnfalse;
    }
if (start==null||end==null) {
returntrue;
    }
if (start.start==end.start&&start.end==end.end) {
returntrue;
    }
returnfalse;
}

时间复杂度：O（n）。

空间复杂度： O（n），里边的 in 变量用来存储囊括的节点时候耗费的。

我们其实可以利用迭代器，一边遍历，一边删除，这样就不需要 in 变量了。

publicList<Interval>insert(List<Interval>intervals, IntervalnewInterval) {
Intervalstart=null;
Intervalend=null;
inti_start=newInterval.start;
inti_end=newInterval.end;  
//利用迭代器遍历for (Iterator<Interval>it=intervals.iterator(); it.hasNext();) {
Intervalinter=it.next();
if (i_start>=inter.start&&i_start<=inter.end) {
start=inter;
            }
if (i_end>=inter.start&&i_end<=inter.end) {
end=inter;
            }
if (i_start<inter.start&&i_end>inter.end) {
it.remove();
            }
        }
Intervalinterval=null;
if (equals(start, end)) {
ints=start==null?i_start : start.start;
inte=end==null?i_end : end.end;
interval=newInterval(s, e);
        } elseif (start!=null&&end!=null) {
interval=newInterval(start.start, end.end);
        } elseif (start==null) {
interval=newInterval(i_start, i_end);
        }
if (start!=null) {
intervals.remove(start);
        }
if (end!=null) {
intervals.remove(end);
        }
for (inti=0; i<intervals.size(); i++) {
if (intervals.get(i).start>interval.start) {
intervals.add(i, interval);
returnintervals;
            }
        }
intervals.add(interval);
returnintervals; 
    }
privatebooleanequals(Intervalstart, Intervalend) { 
if (start==null&&end==null) {
returnfalse;
    }
if (start==null||end==null) {
returntrue;
    }
if (start.start==end.start&&start.end==end.end) {
returntrue;
    }
returnfalse;
}