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

Commit736db6e

Browse files
committed
feat: add 056
1 parent2fcfda7 commit736db6e

File tree

4 files changed

+174
-0
lines changed

4 files changed

+174
-0
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -67,6 +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|
7071
|554|[Brick Wall][554]|Hash Table|
7172

7273

@@ -131,6 +132,7 @@
131132
[043]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/043/README.md
132133
[049]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/049/README.md
133134
[050]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/050/README.md
135+
[056]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/056/README.md
134136
[554]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/554/README.md
135137

136138
[004]:https://github.com/Blankj/awesome-java-leetcode/blob/master/note/004/README.md

‎note/056/README.md

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
#[Merge Intervals][title]
2+
3+
##Description
4+
5+
Given a collection of intervals, merge all overlapping intervals.
6+
7+
For example,
8+
Given`[1,3],[2,6],[8,10],[15,18]`,
9+
return`[1,6],[8,10],[15,18]`.
10+
11+
**Tags:** Array, Sort
12+
13+
14+
##思路
15+
16+
题意是给你一组区间，让你把区间合并成没有交集的一组区间。我们可以把区间按`start`进行排序，然后遍历排序后的区间，如果当前的`start`小于前者的`end`，那么说明这两个存在交集，我们取两者中较大的`end`即可；否则的话直接插入到结果序列中即可。
17+
18+
```java
19+
/**
20+
* Definition for an interval.
21+
* public class Interval {
22+
* int start;
23+
* int end;
24+
* Interval() { start = 0; end = 0; }
25+
* Interval(int s, int e) { start = s; end = e; }
26+
* }
27+
*/
28+
classSolution {
29+
publicList<Interval>merge(List<Interval>intervals) {
30+
if (intervals==null|| intervals.size()<=1)return intervals;
31+
intervals.sort(newComparator<Interval>() {
32+
@Override
33+
publicintcompare(Intervalo1,Intervalo2) {
34+
if (o1.start< o2.start)return-1;
35+
if (o1.start> o2.start)return1;
36+
return0;
37+
}
38+
});
39+
List<Interval> ans=newArrayList<>();
40+
int start= intervals.get(0).start;
41+
int end= intervals.get(0).end;
42+
for (Interval interval: intervals) {
43+
if (interval.start<= end) {
44+
end=Math.max(end, interval.end);
45+
}else {
46+
ans.add(newInterval(start, end));
47+
start= interval.start;
48+
end= interval.end;
49+
}
50+
}
51+
ans.add(newInterval(start, end));
52+
return ans;
53+
}
54+
}
55+
```
56+
57+
58+
##结语
59+
60+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
61+
62+
63+
64+
[title]:https://leetcode.com/problems/merge-intervals
65+
[ajl]:https://github.com/Blankj/awesome-java-leetcode
Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
packagecom.blankj.medium._056;
2+
3+
importcom.blankj.structure.Interval;
4+
5+
importjava.util.ArrayList;
6+
importjava.util.Comparator;
7+
importjava.util.List;
8+
9+
/**
10+
* <pre>
11+
* author: Blankj
12+
* blog : http://blankj.com
13+
* time : 2017/10/19
14+
* desc :
15+
* </pre>
16+
*/
17+
publicclassSolution {
18+
publicList<Interval>merge(List<Interval>intervals) {
19+
if (intervals ==null ||intervals.size() <=1)returnintervals;
20+
intervals.sort(newComparator<Interval>() {
21+
@Override
22+
publicintcompare(Intervalo1,Intervalo2) {
23+
if (o1.start <o2.start)return -1;
24+
if (o1.start >o2.start)return1;
25+
return0;
26+
}
27+
});
28+
List<Interval>ans =newArrayList<>();
29+
intstart =intervals.get(0).start;
30+
intend =intervals.get(0).end;
31+
for (Intervalinterval :intervals) {
32+
if (interval.start <=end) {
33+
end =Math.max(end,interval.end);
34+
}else {
35+
ans.add(newInterval(start,end));
36+
start =interval.start;
37+
end =interval.end;
38+
}
39+
}
40+
ans.add(newInterval(start,end));
41+
returnans;
42+
}
43+
44+
publicstaticvoidmain(String[]args) {
45+
Solutionsolution =newSolution();
46+
Interval.print(solution.merge(Interval.createTestData("[1,3],[2,6],[8,10],[15,18]")));
47+
}
48+
}
Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
packagecom.blankj.structure;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.List;
5+
6+
/**
7+
* <pre>
8+
* author: Blankj
9+
* blog : http://blankj.com
10+
* time : 2017/10/19
11+
* desc :
12+
* </pre>
13+
*/
14+
publicclassInterval {
15+
publicintstart;
16+
publicintend;
17+
18+
publicInterval() {
19+
start =0;
20+
end =0;
21+
}
22+
23+
publicInterval(ints,inte) {
24+
start =s;
25+
end =e;
26+
}
27+
28+
/**
29+
* 创建测试数据
30+
*
31+
* @param data [[X,X],[X,X],[X,X]]
32+
* @return {@link List<Interval>}
33+
*/
34+
publicstaticList<Interval>createTestData(Stringdata) {
35+
List<Interval>list =newArrayList<>();
36+
String[]d =data.substring(1,data.length() -1).split("],\\[");
37+
for (Strings :d) {
38+
String[]sub =s.split(",");
39+
list.add(newInterval(Integer.valueOf(sub[0]),Integer.valueOf(sub[1])));
40+
}
41+
returnlist;
42+
}
43+
44+
publicstaticvoidprint(List<Interval>list) {
45+
if (list ==null) {
46+
System.out.println("null");
47+
return;
48+
}
49+
StringBuildersb =newStringBuilder();
50+
for (Intervalinterval :list) {
51+
sb.append("[")
52+
.append(interval.start)
53+
.append(",")
54+
.append(interval.end)
55+
.append("],");
56+
}
57+
System.out.println(sb.substring(0,sb.length() -1));
58+
}
59+
}

0 commit comments

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