Skip to content

Commit 146e81e

Browse files
awangdevawangdev
committed
3.15
1 parent 3c33ef0 commit 146e81e

17 files changed

Lines changed: 768 additions & 358 deletions

‎Java/Binary Tree Inorder Traversal.java‎

100644100755
Lines changed: 67 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
E
22

33
法一:
4-
Recursive: Divide and Conquer, with helper method
4+
Recursive: Divide and Conquer, with helper(dfs) method
55

66
法二:
77
Stack:
@@ -39,6 +39,70 @@
3939
4040
*/
4141

42+
/*
43+
recap 3.15.2016
44+
Recursive
45+
*/
46+
public class Solution {
47+
public List<Integer> inorderTraversal(TreeNode root) {
48+
List<Integer> rst = new ArrayList<Integer>();
49+
if (root == null) {
50+
return rst;
51+
}
52+
dfs(rst, root);
53+
return rst;
54+
}
55+
56+
public void dfs(List<Integer> rst, TreeNode node) {
57+
if (node.left != null) {
58+
dfs(rst, node.left);
59+
}
60+
rst.add(node.val);
61+
if (node.right != null) {
62+
dfs(rst, node.right);
63+
}
64+
}
65+
}
66+
67+
68+
69+
70+
/*
71+
recap 3.15.2016
72+
Iterative
73+
stack: add left till end; consume top, if has right, add right; push right.left till end of right's left node.
74+
*/
75+
public class Solution {
76+
public List<Integer> inorderTraversal(TreeNode root) {
77+
List<Integer> rst = new ArrayList<Integer>();
78+
if (root == null) {
79+
return rst;
80+
}
81+
Stack<TreeNode> stack = new Stack<TreeNode>();
82+
TreeNode node = root;
83+
//Initialize
84+
while (node != null) {
85+
stack.push(node);
86+
node = node.left;
87+
}
88+
//iteratively add && process via inorder traversal
89+
while (!stack.isEmpty()) {
90+
node = stack.pop();
91+
rst.add(node.val);
92+
if (node.right != null) {//process right, but put right's left children on top of stack
93+
node = node.right;
94+
while (node != null) {
95+
stack.push(node);
96+
node = node.left;
97+
}
98+
}
99+
100+
}
101+
return rst;
102+
}
103+
}
104+
105+
42106
/*
43107
1. Use a helper method, recursively add to rst
44108
*/
@@ -81,10 +145,6 @@ public void helper(ArrayList<Integer> rst, TreeNode node) {
81145
*/
82146

83147
public class Solution {
84-
/**
85-
* @param root: The root of binary tree.
86-
* @return: Inorder in ArrayList which contains node values.
87-
*/
88148
public ArrayList<Integer> inorderTraversal(TreeNode root) {
89149
ArrayList<Integer> rst = new ArrayList<Integer>();
90150
if (root == null) {
@@ -114,4 +174,6 @@ public ArrayList<Integer> inorderTraversal(TreeNode root) {
114174

115175

116176

177+
178+
117179
```

‎Java/Binary Tree Level Order Traversal II.java‎

100644100755
File mode changed.

‎Java/Binary Tree Level Order Traversal.java‎

100644100755
File mode changed.

‎Java/Binary Tree Postorder Traversal.java‎

100644100755
File mode changed.

‎Java/Binary Tree Preorder Traversal.java‎

100644100755
File mode changed.

‎Java/Building Outline.java‎

Lines changed: 123 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,29 @@
1+
H
2+
3+
又叫做skyline
4+
5+
看网上的解答做， 思路很漂亮。 （http://codechen.blogspot.com/2015/06/leetcode-skyline-problem.html?_sm_au_=isVmHvFmFs40TWRt）
6+
7+
跟scan line的approach类似:
8+
1. 把所有点分出来， 每个点有index x, 再加上一个height.
9+
2. 在这个list上排序，根据index和height（注意用负数标记building start point,这样保证start在end 之前。）. 叫做 heightPoints
10+
3. 在processs时候用max-heap (reversed priorityqueue)，在ieteraete heightPoints 来存最大的height . 遇到peek,就是一个合理的解
11+
处理1：因为start,end的height都存在了heightPoints里面，这里就是用来check end of bulding的，然后把height 从queue里面remove.
12+
处理2：重复x 上面的许多height? priorityqueue给了我们最高，这okay了；那么其他的重复点，用一个int prev来mark之前做过的，一旦重复，跳过。
13+
14+
想法非常natural。 大题目，脑子乱。
15+
看了解答再去想，挺naturally doable的。
16+
17+
```
118
/*
2-
Given N buildings in a x-axis，each building is a rectangle and can be represented by a triple (start, end, height)，where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building. Buildings may overlap if you see them from far away，find the outline of them。
3-
An outline can be represented by a triple, (start, end, height), where start is the start position on x-axis of the outline, end is the end position on x-axis and height is the height of the outline.
19+
LintCode description:
20+
Given N buildings in a x-axis，each building is a rectangle and can be represented by a triple (start, end, height)，
21+
where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building.
22+
Buildings may overlap if you see them from far away，find the outline of them。
23+
An outline can be represented by a triple, (start, end, height),
24+
where start is the start position on x-axis of the outline,
25+
end is the end position on x-axis and height is the height of the outline.
26+
427
Example
528
Given 3 buildings：
629
[
@@ -19,32 +42,114 @@
1942
Tags Expand
2043
LintCode Copyright Heap
2144
*/
45+
46+
/*LeetCode description
47+
A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Now suppose you are given the locations and height of all the buildings as shown on a cityscape photo (Figure A), write a program to output the skyline formed by these buildings collectively (Figure B).
48+
49+
Buildings Skyline Contour
50+
The geometric information of each building is represented by a triplet of integers [Li, Ri, Hi], where Li and Ri are the x coordinates of the left and right edge of the ith building, respectively, and Hi is its height. It is guaranteed that 0 ≤ Li, Ri ≤ INT_MAX, 0 < Hi ≤ INT_MAX, and Ri - Li > 0. You may assume all buildings are perfect rectangles grounded on an absolutely flat surface at height 0.
51+
52+
For instance, the dimensions of all buildings in Figure A are recorded as: [ [2 9 10], [3 7 15], [5 12 12], [15 20 10], [19 24 8] ] .
53+
54+
The output is a list of "key points" (red dots in Figure B) in the format of [ [x1,y1], [x2, y2], [x3, y3], ... ] that uniquely defines a skyline. A key point is the left endpoint of a horizontal line segment. Note that the last key point, where the rightmost building ends, is merely used to mark the termination of the skyline, and always has zero height. Also, the ground in between any two adjacent buildings should be considered part of the skyline contour.
55+
56+
For instance, the skyline in Figure B should be represented as:[ [2 10], [3 15], [7 12], [12 0], [15 10], [20 8], [24, 0] ].
57+
58+
Notes:
59+
60+
The number of buildings in any input list is guaranteed to be in the range [0, 10000].
61+
The input list is already sorted in ascending order by the left x position Li.
62+
The output list must be sorted by the x position.
63+
There must be no consecutive horizontal lines of equal height in the output skyline. For instance, [...[2 3], [4 5], [7 5], [11 5], [12 7]...] is not acceptable; the three lines of height 5 should be merged into one in the final output as such: [...[2 3], [4 5], [12 7], ...]
64+
65+
Hide Tags Divide and Conquer Binary Indexed Tree Heap Segment Tree
66+
67+
*/
68+
2269
/*
23-
Thoughts:
24-
Well, based on JiuZhang, http://www.jiuzhang.com/solutions/building-outline/, implement a HashHeap.
25-
**HashHeap. Super long implementation: http://www.jiuzhang.com/solutions/hash-heap/
70+
Thoughts
71+
Based idea here:http://codechen.blogspot.com/2015/06/leetcode-skyline-problem.html?_sm_au_=isVmHvFmFs40TWRt
72+
Here is the thinking process, 3.15.2016
73+
74+
The class HeightPoint{int x, int height} is very similar to scan line Point{int x, int flag}. However the usage is a bit different.
75+
Sort all of the heightPoints by index && by height.
76+
Use nagtive height for start point to make sure start appears before end point, tho they share same height
77+
We use an extra priorityQueue to store the height being processed (note, this queue, decending order, max in front)
78+
When having a negative height(start point), add into queue
79+
At each point, find heightest point (common sense!) and mark it on map: the overlapping point at this index will be skipped because the rest are not high enough.
80+
How to process the rest redundant point?
81+
Here introduce a 'prev' variable that stores last processed value. If same height appears right before curr, don't add to result; it's added during this continuous line.
82+
How to maintain the queue?
83+
Once a height > 0 appears, remove that height from queue.
84+
OKay, let's break it down:
85+
because we sort HeightPoint object by index and height, start height will appear before end height of same building, for sure.
86+
So whenever positive height appears, the same bulding must have been marked, so can safely remove the height instance from queue.
87+
Well, in HeightPoint object, start height is negative for sorting purpose. When adding into queue, use it's absolute value : )
2688
*/
89+
public class Solution {
90+
public class HeightPoint{
91+
int x, height;
92+
public HeightPoint(int x, int height) {
93+
this.x = x;
94+
this.height = height;
95+
}
96+
}
97+
public List<int[]> getSkyline(int[][] buildings) {
98+
List<int[]> rst = new ArrayList<int[]>();
99+
if (buildings == null || buildings.length == 0 || buildings[0].length == 0) {
100+
return rst;
101+
}
27102

103+
//Init the list sorted by index && height
104+
List<HeightPoint> heightPoints = new ArrayList<HeightPoint>();
105+
for (int i = 0; i < buildings.length; i++) {
106+
heightPoints.add(new HeightPoint(buildings[i][0], -buildings[i][2]));
107+
heightPoints.add(new HeightPoint(buildings[i][1], buildings[i][2]));
108+
}
109+
Collections.sort(heightPoints, new Comparator<HeightPoint>() {
110+
public int compare(HeightPoint p1, HeightPoint p2) {
111+
if (p1.x == p2.x) {
112+
return p1.height - p2.height;
113+
} else {
114+
return p1.x - p2.x;
115+
}
116+
}
117+
});
28118

119+
//Process height points
120+
//reversed priorityqueue, becase for same pos x, we always want the highest point
121+
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(1000, Collections.reverseOrder());
122+
queue.offer(0);
123+
int prev = queue.peek();
29124

125+
for (HeightPoint p : heightPoints) {
126+
if (p.height < 0) {
127+
queue.offer(-p.height);
128+
} else {
129+
queue.remove(p.height);
130+
}
30131

132+
int currPeak = queue.peek();
133+
if (currPeak != prev) {
134+
rst.add(new int[] {p.x, currPeak});
135+
prev = currPeak;
136+
}
137+
}
31138

32-
/****
33-
Attempt1, may not be correct.
34-
Thoughts:
35-
PriorityQueue<Point>, sort by start.
36-
1. Keep track of max height.
37-
2. Find max height.
38-
3. Poll() queue. Whenever there is a jump(up or down) at current node, close a interval.
39-
4. When closing interval, set prev = new node.h
40-
****/
139+
return rst;
140+
}
141+
}
41142

42143

43-
/**
144+
145+
/*
146+
Thoughts:
147+
Well, based on JiuZhang, http://www.jiuzhang.com/solutions/building-outline/, implement a HashHeap.
148+
**HashHeap. Super long implementation: http://www.jiuzhang.com/solutions/hash-heap/
44149
45150
What is HashHeap Exactly? Document below:
46151
47-
**/
152+
*/
48153
class HashHeap {
49154
//Heap is a arraylist, which stores the actaul Integer values. It stores the real data
50155
ArrayList<Integer> heap;
@@ -227,3 +332,5 @@ void siftdown(int id) {
227332
}
228333
}
229334
}
335+
336+
```

‎Java/Construct Binary Tree from Inorder and Postorder Traversal.java‎

Lines changed: 1 addition & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -60,11 +60,7 @@ Because the ending element is cut off previously to serve as root, we need to do
6060

6161

6262
public class Solution {
63-
/**
64-
*@param inorder : A list of integers that inorder traversal of a tree
65-
*@param postorder : A list of integers that postorder traversal of a tree
66-
*@return : Root of a tree
67-
*/
63+
6864
public TreeNode buildTree(int[] inorder, int[] postorder) {
6965
if (inorder.length != postorder.length) {
7066
return null;

‎Java/Course Schedule II.java‎

100644100755
File mode changed.

‎Java/Course Schedule.java‎

100644100755
File mode changed.

‎Java/Insert Interval.java‎

100644100755
Lines changed: 86 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,23 @@
11
E
22

3-
O(n) 直接找到可以insert newInterval的位子. Insert。
3+
4+
方法1：Scan Line
5+
Interval 拆点，PriorityQueue排点。
6+
Merge时用count==0作判断点。
7+
8+
PriorityQueue: O(logN). 扫n点，总共：O(nLogn)
9+
10+
11+
方法2：
12+
O(n) 直接找到可以insert newInterval的位子. Insert。 这里已经给了sorted intervals by start point. 所以O(n)
413

514
然后loop to merge entire interval array
615

716
另外: 因为interval已经sort, 本想用Binary Search O(logn). 但是找到interval insert position， merge还是要用 O(n)。
817
比如刚好newInterval cover entire list....
18+
19+
20+
921
```
1022

1123
/*
@@ -35,6 +47,79 @@
3547

3648

3749

50+
/*
51+
Thoughts:
52+
What's the difference from merge intervals?
53+
1. Create Class point (x, flag)
54+
2. sort point in min-heap
55+
3. when count increase and decreases to 0, that means we can close an interval
56+
*/
57+
58+
public class Solution {
59+
60+
class Point {
61+
int x;
62+
int flag;
63+
public Point(int x, int flag) {
64+
this.x = x;
65+
this.flag = flag;
66+
}
67+
}
68+
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
69+
List<Interval> rst = new ArrayList<Interval>();
70+
if (intervals == null && newInterval == null) {
71+
return rst;
72+
} else if (intervals == null) {
73+
rst.add(newInterval);
74+
return rst;
75+
} else if (newInterval == null) {
76+
return intervals;
77+
}
78+
79+
PriorityQueue<Point> queue = new PriorityQueue<Point>(1, new Comparator<Point>(){
80+
public int compare(Point a, Point b){
81+
return a.x - b.x;
82+
}
83+
});
84+
85+
for (Interval range: intervals) {
86+
queue.add(new Point(range.start, 1));
87+
queue.add(new Point(range.end, -1));
88+
}
89+
90+
queue.add(new Point(newInterval.start, 1));
91+
queue.add(new Point(newInterval.end, -1));
92+
93+
int count = 0;
94+
int startNew = 0;
95+
int endNew = 0;
96+
while (!queue.isEmpty()) {
97+
Point p = queue.poll();
98+
if (count == 0) {
99+
startNew = p.x;
100+
}
101+
count += p.flag;
102+
103+
while (!queue.isEmpty() && p.x == queue.peek().x) {
104+
p = queue.poll();
105+
count += p.flag;
106+
}
107+
108+
if (count == 0) {
109+
endNew = p.x;
110+
Interval addInterval = new Interval(startNew, endNew);
111+
rst.add(addInterval);
112+
}
113+
114+
}//end while
115+
116+
return rst;
117+
118+
}
119+
}
120+
121+
122+
38123
/*
39124
O(n)
40125
Thoughts:

0 commit comments

Comments
 (0)