Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit14fc236

Browse files
committed
feat: add 057
1 parent736db6e commit14fc236

File tree

3 files changed

+120
-1
lines changed

3 files changed

+120
-1
lines changed

‎README.md

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -67,7 +67,7 @@
6767
|43|[Multiply Strings][043]|Math, String|
6868
|49|[Group Anagrams][049]|Hash Table, String|
6969
|50|[Pow(x, n)][050]|Math, Binary Search|
70-
|56|[Merge Intervals][056]|Math, Binary Search|
70+
|56|[Merge Intervals][056]|Array, Sort|
7171
|554|[Brick Wall][554]|Hash Table|
7272

7373

@@ -80,6 +80,7 @@
8080
|23|[Merge k Sorted Lists][023]|Linked List, Divide and Conquer, Heap|
8181
|25|[Reverse Nodes in k-Group][025]|Linked List|
8282
|44|[Reverse Nodes in k-Group][044]|String, Dynamic Programming, Backtracking, Greedy|
83+
|57|[Insert Interval][057]|Array, Sort|
8384

8485

8586

@@ -140,3 +141,4 @@
140141
[023]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/023/README.md
141142
[025]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/025/README.md
142143
[044]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/044/README.md
144+
[057]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/057/README.md

‎note/057/README.md

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
#[Insert Interval][title]
2+
3+
##Description
4+
5+
Given a set of*non-overlapping* intervals, insert a new interval into the intervals (merge if necessary).
6+
7+
You may assume that the intervals were initially sorted according to their start times.
8+
9+
**Example 1:**
10+
Given intervals`[1,3],[6,9]`, insert and merge`[2,5]` in as`[1,5],[6,9]`.
11+
12+
**Example 2:**
13+
Given`[1,2],[3,5],[6,7],[8,10],[12,16]`, insert and merge`[4,9]` in as`[1,2],[3,10],[12,16]`.
14+
15+
This is because the new interval`[4,9]` overlaps with`[3,5],[6,7],[8,10]`.
16+
17+
**Tags:** Array, Sort
18+
19+
20+
##思路
21+
22+
题意是给你一组有序区间，和一个待插入区间，让你待插入区间插入到前面的区间中，我们分三步走：
23+
1. 首先把有序区间中小于待插入区间的部分加入到结果中；
24+
2. 其次是插入待插入区间，如果有交集的话取两者交集的端点值；
25+
3. 最后把有序区间中大于待插入区间的部分加入到结果中；
26+
27+
```java
28+
/**
29+
* Definition for an interval.
30+
* public class Interval {
31+
* int start;
32+
* int end;
33+
* Interval() { start = 0; end = 0; }
34+
* Interval(int s, int e) { start = s; end = e; }
35+
* }
36+
*/
37+
classSolution {
38+
publicList<Interval>insert(List<Interval>intervals,IntervalnewInterval) {
39+
if (intervals.isEmpty())returnCollections.singletonList(newInterval);
40+
List<Interval> ans=newArrayList<>();
41+
int i=0, len= intervals.size();
42+
for (; i< len;++i) {
43+
Interval interval= intervals.get(i);
44+
if (interval.end< newInterval.start) ans.add(interval);
45+
elsebreak;
46+
}
47+
for (; i< len;++i) {
48+
Interval interval= intervals.get(i);
49+
if (interval.start<= newInterval.end) {
50+
newInterval.start=Math.min(newInterval.start, interval.start);
51+
newInterval.end=Math.max(newInterval.end, interval.end);
52+
}elsebreak;
53+
}
54+
ans.add(newInterval);
55+
for (; i< len;++i) {
56+
ans.add(intervals.get(i));
57+
}
58+
return ans;
59+
}
60+
}
61+
```
62+
63+
64+
##结语
65+
66+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
67+
68+
69+
70+
[title]:https://leetcode.com/problems/insert-interval
71+
[ajl]:https://github.com/Blankj/awesome-java-leetcode
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
packagecom.blankj.medium._057;
2+
3+
importcom.blankj.structure.Interval;
4+
5+
importjava.util.ArrayList;
6+
importjava.util.Collections;
7+
importjava.util.List;
8+
9+
/**
10+
* <pre>
11+
* author: Blankj
12+
* blog : http://blankj.com
13+
* time : 2017/10/24
14+
* desc :
15+
* </pre>
16+
*/
17+
publicclassSolution {
18+
publicList<Interval>insert(List<Interval>intervals,IntervalnewInterval) {
19+
if (intervals.isEmpty())returnCollections.singletonList(newInterval);
20+
List<Interval>ans =newArrayList<>();
21+
inti =0,len =intervals.size();
22+
for (;i <len; ++i) {
23+
Intervalinterval =intervals.get(i);
24+
if (interval.end <newInterval.start)ans.add(interval);
25+
elsebreak;
26+
}
27+
for (;i <len; ++i) {
28+
Intervalinterval =intervals.get(i);
29+
if (interval.start <=newInterval.end) {
30+
newInterval.start =Math.min(newInterval.start,interval.start);
31+
newInterval.end =Math.max(newInterval.end,interval.end);
32+
}elsebreak;
33+
}
34+
ans.add(newInterval);
35+
for (;i <len; ++i) {
36+
ans.add(intervals.get(i));
37+
}
38+
returnans;
39+
}
40+
41+
publicstaticvoidmain(String[]args) {
42+
Solutionsolution =newSolution();
43+
Interval.print(solution.insert(Interval.createTestData("[1,3],[6,9]"),newInterval(2,5)));
44+
Interval.print(solution.insert(Interval.createTestData("[1,2],[3,5],[6,7],[8,10],[12,16]"),newInterval(4,9)));
45+
}
46+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp