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

Commit45b9d4d

Browse files
committed
merge
1 parentf9435b5 commit45b9d4d

File tree

3 files changed

+112
-1
lines changed

3 files changed

+112
-1
lines changed

‎array/Interval.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
packageAlgorithms.array;
2+
3+
publicclassInterval {
4+
intstart;
5+
intend;
6+
7+
Interval() {
8+
start =0;
9+
end =0;
10+
}
11+
12+
Interval(ints,inte) {
13+
start =s;
14+
end =e;
15+
}
16+
}

‎array/Merge.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
packageAlgorithms.array;
2+
3+
importjava.util.ArrayList;
4+
importjava.util.Collections;
5+
importjava.util.Comparator;
6+
importjava.util.Iterator;
7+
importjava.util.List;
8+
9+
/**
10+
* Definition for an interval.
11+
* public class Interval {
12+
* int start;
13+
* int end;
14+
* Interval() { start = 0; end = 0; }
15+
* Interval(int s, int e) { start = s; end = e; }
16+
* }
17+
*/
18+
publicclassMerge {
19+
publicList<Interval>merge(List<Interval>intervals) {
20+
List<Interval>ret =newArrayList<Interval>();
21+
if (intervals ==null ||intervals.size() ==0) {
22+
returnret;
23+
}
24+
25+
Collections.sort(intervals,newComparator<Interval>() {
26+
publicintcompare(Intervalo1,Intervalo2) {
27+
// sort the intervals by the start.
28+
returno1.start -o2.start;
29+
}
30+
});
31+
32+
// 作为最后一个插入的区间
33+
Intervallast =intervals.get(0);
34+
35+
// 这里要考虑性能。使用iterator的话，对linkedlist会更快.
36+
Iterator<Interval>itor =intervals.iterator();
37+
while (itor.hasNext()) {
38+
Intervalcur =itor.next();
39+
// cur 在last的右边
40+
if (cur.start >last.end) {
41+
// 将cur作为新的last.
42+
ret.add(last);
43+
last =cur;
44+
// cur与last有重合的部分，合并之
45+
}else {
46+
ints =last.start;
47+
inte =Math.max(last.end,cur.end);
48+
last =newInterval(s,e);
49+
}
50+
}
51+
52+
// 把最后一个区间加上
53+
ret.add(last);
54+
55+
returnret;
56+
}
57+
}

‎hash/LongestConsecutive.java

Lines changed: 39 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,11 @@
11
packageAlgorithms.hash;
22

33
importjava.util.HashMap;
4+
importjava.util.HashSet;
45

56
publicclassLongestConsecutive {
6-
publicintlongestConsecutive(int[]num) {
7+
// Solution 1: use hashmap.
8+
publicintlongestConsecutive1(int[]num) {
79
if (num ==null) {
810
return0;
911
}
@@ -54,4 +56,40 @@ public int longestConsecutive(int[] num) {
5456

5557
returnmax;
5658
}
59+
60+
// solution 2: use Hashset.
61+
publicintlongestConsecutive(int[]num) {
62+
if (num ==null) {
63+
return0;
64+
}
65+
66+
HashSet<Integer>set =newHashSet<Integer>();
67+
for (inti:num) {
68+
set.add(i);
69+
}
70+
71+
intmax =0;
72+
for (inti:num) {
73+
intcnt =1;
74+
set.remove(i);
75+
76+
inttmp =i -1;
77+
while (set.contains(tmp)) {
78+
set.remove(tmp);
79+
cnt++;
80+
tmp--;
81+
}
82+
83+
tmp =i +1;
84+
while (set.contains(tmp)) {
85+
set.remove(tmp);
86+
cnt++;
87+
tmp++;
88+
}
89+
90+
max =Math.max(max,cnt);
91+
}
92+
93+
returnmax;
94+
}
5795
}

0 commit comments

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