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

Commit0f07b84

Browse files
committed
218 (1) with heap solution TODO
1 parent76c96b9 commit0f07b84

File tree

6 files changed

+513
-0
lines changed

6 files changed

+513
-0
lines changed
Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
/**
2+
***************************************************************************
3+
* Description:
4+
*
5+
*
6+
***************************************************************************
7+
* @tag : Divide and Conquer; Heap
8+
* {@link https://leetcode.com/problems/the-skyline-problem/ }
9+
*/
10+
package_218_TheSkylineProblem;
11+
12+
importjava.util.List;
13+
14+
/** see test {@link _218_TheSkylineProblem.PraticeTest } */
15+
publicclassPractice {
16+
17+
publicList<int[]>getSkyline(int[][]buildings) {
18+
// TODO Auto-generated method stub
19+
returnnull;
20+
}
21+
22+
}
Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
/**
2+
* Time : O(NlgN) ; Space: O()
3+
* @tag : Divide and Conquer; Heap
4+
* @by : Steven Cooks
5+
* @date: Sep 18, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
*
10+
***************************************************************************
11+
* {@link https://leetcode.com/problems/the-skyline-problem/ }
12+
* {@link http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/ }
13+
* {@link https://leetcode.com/discuss/40963/share-my-divide-and-conquer-java-solution-464-ms }
14+
*/
15+
package_218_TheSkylineProblem;
16+
17+
importjava.util.ArrayList;
18+
importjava.util.LinkedList;
19+
importjava.util.List;
20+
21+
/** see test {@link _218_TheSkylineProblem.SolutionTest } */
22+
publicclassSolution {
23+
24+
// divide and conquer
25+
publicList<int[]>getSkyline(int[][]buildings) {
26+
List<int[]>res =newArrayList<>();
27+
if (buildings.length ==0) {
28+
returnres;
29+
}
30+
intp =0;
31+
intq =buildings.length -1;
32+
returnrecurSkyline(buildings,p,q);
33+
}
34+
35+
// construct sky line for buildings[p : q]
36+
privateLinkedList<int[]>recurSkyline(int[][]buildings,intp,intq) {
37+
if (p ==q) {
38+
LinkedList<int[]>skyline =newLinkedList<>();
39+
skyline.add(newint[] {buildings[p][0],buildings[p][2] });
40+
skyline.add(newint[] {buildings[p][1],0 });
41+
returnskyline;
42+
}else {
43+
intmid =p + (q -p) /2;
44+
returnmerge(recurSkyline(buildings,p,mid),recurSkyline(buildings,mid +1,q));
45+
}
46+
}
47+
48+
// merge sky line 1 and sky line 2
49+
privateLinkedList<int[]>merge(LinkedList<int[]>s1,LinkedList<int[]>s2) {
50+
LinkedList<int[]>res =newLinkedList<>();
51+
inth1 =0;// height from s1
52+
inth2 =0;// height from s2
53+
while (s1.size() >0 &&s2.size() >0) {
54+
// key point is { x, h }
55+
intx =0;inth =0;
56+
if (s1.getFirst()[0] <s2.getFirst()[0]) {
57+
x =s1.getFirst()[0];
58+
h1 =s1.getFirst()[1];
59+
h =Math.max(h1,h2);
60+
s1.removeFirst();
61+
}elseif (s1.getFirst()[0] >s2.getFirst()[0]) {
62+
x =s2.getFirst()[0];
63+
h2 =s2.getFirst()[1];
64+
h =Math.max(h1,h2);
65+
s2.removeFirst();
66+
}else {
67+
x =s1.getFirst()[0];
68+
h1 =s1.getFirst()[1];
69+
h2 =s2.getFirst()[1];
70+
h =Math.max(h1,h2);
71+
s1.removeFirst();
72+
s2.removeFirst();
73+
}
74+
if (res.size() ==0 ||h !=res.getLast()[1]) {
75+
// ignore key points that at the same level
76+
res.add(newint[] {x,h });
77+
}
78+
}
79+
res.addAll(s1);
80+
res.addAll(s2);
81+
returnres;
82+
}
83+
84+
}
Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
/**
2+
* Time : O(NlgN) ; Space: O()
3+
* @tag : Divide and Conquer; Heap
4+
* @by : Steven Cooks
5+
* @date: Sep 18, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
*
10+
***************************************************************************
11+
* {@link https://leetcode.com/problems/the-skyline-problem/ }
12+
* {@link http://www.geeksforgeeks.org/divide-and-conquer-set-7-the-skyline-problem/ }
13+
*/
14+
package_218_TheSkylineProblem;
15+
16+
importjava.util.ArrayList;
17+
importjava.util.Comparator;
18+
importjava.util.List;
19+
importjava.util.PriorityQueue;
20+
importjava.util.Queue;
21+
22+
/** see test {@link _218_TheSkylineProblem.SolutionHeapTest } */
23+
publicclassSolutionHeap {
24+
25+
privateclassEdge {
26+
intx;
27+
intheight;
28+
inttype;// left edge is type 0, right edge is type 1
29+
30+
publicEdge(intx,intheight,inttype) {
31+
this.x =x;
32+
this.height =height;
33+
this.type =type;
34+
}
35+
36+
@Override
37+
publicStringtoString() {
38+
return"[" +x +"," +height +"," +type +"]";
39+
}
40+
}
41+
42+
//TODO
43+
publicList<int[]>getSkyline(int[][]buildings) {
44+
List<int[]>res =newArrayList<>();
45+
if (buildings.length ==0) {
46+
returnres;
47+
}
48+
Queue<Edge>edges =newPriorityQueue<>(newComparator<Edge>() {
49+
@Override
50+
publicintcompare(Edgee1,Edgee2) {
51+
returne1.x -e2.x;
52+
}
53+
});
54+
for (inti =0;i <buildings.length;i++) {
55+
int[]triplet =buildings[i];
56+
edges.offer(newEdge(triplet[0],triplet[2],0));
57+
edges.offer(newEdge(triplet[1],triplet[2],1));
58+
}
59+
edges.offer(newEdge(0,0,0));
60+
edges.offer(newEdge(Integer.MAX_VALUE,0,1));
61+
62+
while (edges.size() >=2) {
63+
Edgee1 =edges.poll();
64+
Edgee2 =edges.peek();
65+
if (e1.type ==0 &&e2.type ==0) {
66+
if (e1.height <e2.height) {
67+
int[]key = {e2.x,e2.height };
68+
res.add(key);
69+
}
70+
}elseif (e1.type ==0 &&e2.type ==1) {
71+
if (e1.height <e2.height) {
72+
int[]key = {e2.x,e1.height };
73+
res.add(key);
74+
}
75+
}elseif (e1.type ==1 &&e2.type ==1) {
76+
if (e1.height >e2.height) {
77+
int[]key = {e1.x,e2.height };
78+
res.add(key);
79+
}
80+
}
81+
}
82+
83+
returnres;
84+
}
85+
86+
}
Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
package_218_TheSkylineProblem;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importjava.util.ArrayList;
6+
importjava.util.Arrays;
7+
importjava.util.List;
8+
9+
importorg.junit.After;
10+
importorg.junit.Before;
11+
importorg.junit.Rule;
12+
importorg.junit.Test;
13+
importorg.junit.rules.Timeout;
14+
15+
publicclassPracticeTest {
16+
17+
/** Test method for {@link _218_TheSkylineProblem.Practice } */
18+
Practicesolution;
19+
20+
@Rule
21+
publicTimeoutglobalTimeout =newTimeout(200);
22+
23+
@Before
24+
publicvoidsetUp()throwsException {
25+
solution =newPractice();
26+
}
27+
28+
@After
29+
publicvoidtearDown()throwsException {
30+
solution =null;
31+
}
32+
33+
@Test
34+
publicvoidTest0() {
35+
int[][]buildings = { };
36+
List<List<Integer>>actuals =toList(solution.getSkyline(buildings));
37+
List<List<Integer>>expecteds =newArrayList<>();
38+
assertEquals(expecteds,actuals);
39+
}
40+
41+
@Test
42+
publicvoidTest1() {
43+
int[][]buildings = {
44+
{2,9,10 },
45+
{3,7,15 },
46+
{5,12,12 },
47+
{15,20,10 },
48+
{19,24,8 }
49+
};
50+
List<List<Integer>>actuals =toList(solution.getSkyline(buildings));
51+
List<List<Integer>>expecteds =newArrayList<>();
52+
expecteds.add(Arrays.asList(2,10));
53+
expecteds.add(Arrays.asList(3,15));
54+
expecteds.add(Arrays.asList(7,12));
55+
expecteds.add(Arrays.asList(12,0));
56+
expecteds.add(Arrays.asList(15,10));
57+
expecteds.add(Arrays.asList(20,8));
58+
expecteds.add(Arrays.asList(24,0));
59+
assertEquals(expecteds,actuals);
60+
}
61+
62+
@Test
63+
publicvoidTest3() {
64+
int[][]buildings = {
65+
{2,9,10 },
66+
{3,4,4},
67+
{4,5,4},
68+
};
69+
List<List<Integer>>actuals =toList(solution.getSkyline(buildings));
70+
List<List<Integer>>expecteds =newArrayList<>();
71+
expecteds.add(Arrays.asList(2,10));
72+
expecteds.add(Arrays.asList(9,0));
73+
assertEquals(expecteds,actuals);
74+
}
75+
76+
@Test
77+
publicvoidTest4() {
78+
int[][]buildings = {
79+
{1,4,10 },
80+
{2,5,18},
81+
};
82+
List<List<Integer>>actuals =toList(solution.getSkyline(buildings));
83+
List<List<Integer>>expecteds =newArrayList<>();
84+
expecteds.add(Arrays.asList(1,10));
85+
expecteds.add(Arrays.asList(2,18));
86+
expecteds.add(Arrays.asList(5,0));
87+
assertEquals(expecteds,actuals);
88+
}
89+
90+
privateList<List<Integer>>toList(List<int[]>lists) {
91+
List<List<Integer>>res =newArrayList<>();
92+
for (int[]list :lists) {
93+
res.add(toList(list));
94+
}
95+
returnres;
96+
}
97+
98+
privateList<Integer>toList(int[]nums) {
99+
List<Integer>res =newArrayList<>();
100+
for (intnum :nums) {
101+
res.add(num);
102+
}
103+
returnres;
104+
}
105+
106+
107+
}

0 commit comments

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