Skip to content

Commit 19c9630

Browse files
awangdevawangdev
committed
fm
1 parent d568148 commit 19c9630

62 files changed

Lines changed: 3096 additions & 2321 deletions

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎Java/3 Sum.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -68,7 +68,7 @@ public List<List<Integer>> threeSum(int[] nums) {
6868
final Integer[] intarr = {nums[start], nums[end], nums[i]};
6969
result.add(Arrays.asList(intarr));
7070
start++;
71-
while (start < end && nums[start - 1] == nums[start]) {
71+
while (start < end && nums[start - 1] == nums[start]) { // skip duplicates
7272
start++;
7373
}
7474
} else if (nums[start] + nums[end] + nums[i] < 0) {

‎Java/Binary Search Tree Iterator.java‎

Lines changed: 21 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -2,37 +2,30 @@
22
1518626557
33
tags: Stack, Tree, Design, BST
44

5+
Build iterator to print ascending elemnts of BST. Inorder traversal BST. Need to maintain O(1) time, O(h) space.
6+
57
画一下, BST in order traversal. 用stack记录最小值, 放在top. O(h) space.
68
每次消耗TreeNode, 都看看rightNode(其实就是下一个最小的candidate), 并且一条龙stack叠上rightNode所有的left子孙.
79

8-
Previous Notes:
9-
用O(h)空间的做法：
10-
11-
理解binary search tree inorder traversal的规律：
12-
先找left.left.left ....left 到底，这里是加进stack.
13-
然后考虑parent,然后再right.
14-
15-
例如这题：
16-
stack里面top，也就是tree最左下角的node先考虑,取名rst.
17-
其实这个rst拿出来以后, 它也同时是最底层left null的parent，算考虑过了最底层的parent。
18-
最后就考虑最底层的parent.right, 也就是rst.right.
19-
20-
注意:
21-
next()其实有个while loop, 很可能是O(h).题目要求average O(1),所以也是okay的.
22-
23-
24-
用O(1)空间的做法：不存stack, 时刻update current为最小值。
25-
26-
找下一个最小值,如果current有right child：
27-
和用stack时的iteration类似,那么再找一遍current.right的left-most child,就是最小值了。
28-
29-
如果current没有right child:
30-
那么就要找current node的右上parent, search in BinarySearchTree from root.
31-
32-
注意：
33-
一定要确保找到的parent满足parent.left == current.
34-
反而言之，如果current是parent的 right child, 那么下一轮就会重新process parent。
35-
但是有错:binary search tree里面parent是小于right child的，也就是在之前一步肯定visit过，如此便会死循环。
10+
#### Stack
11+
- 用O(h)空间的做法：
12+
- 理解binary search tree inorder traversal的规律：
13+
- 先找left.left.left ....left 到底，这里是加进stack; 然后考虑parent,然后再right.
14+
15+
#### Details 例如这题:
16+
- stack里面top，也就是tree最左下角的node先考虑,取名rst.
17+
- 其实这个rst拿出来以后, 它也同时是最底层left null的parent，算考虑过了最底层的parent。
18+
- 最后就考虑最底层的parent.right, 也就是rst.right.
19+
- 注意: next()其实有个while loop, 很可能是O(h).题目要求average O(1),所以也是okay的.
20+
21+
22+
#### 用O(1)空间的做法: 不存stack, 时刻update current为最小值。
23+
- 找下一个最小值,如果current有right child: 和用stack时的iteration类似,那么再找一遍current.right的left-most child,就是最小值了。
24+
- 如果current没有right child: 那么就要找current node的右上parent, search in BinarySearchTree from root.
25+
- 注意:
26+
- 一定要确保找到的parent满足parent.left == current.
27+
- 反而言之，如果current是parent的 right child, 那么下一轮就会重新process parent。
28+
- 但是有错:binary search tree里面parent是小于right child的，也就是在之前一步肯定visit过，如此便会死循环。
3629

3730

3831
```

‎Java/Clone Graph.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1519966780
3-
tags: DFS, BFS, Graph
3+
tags: DFS, BFS, Graph, Hash Table
44

55
给一个graph node, 每个node有list of neighbors. 复制整个graph, return new head node.
66

‎Java/Contiguous Array.java‎

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,15 @@
22
1531902072
33
tags: Hash Table
44

5-
TODO: how aout without chaning the input nums?
5+
find the maximum length of a contiguous subarray with `equal number of 0 and 1`
6+
7+
#### Hash Table
8+
- Trick: equal number of 0 and 1, also can be reflected as equal number of -1, 1.
9+
- 有正负数, 就可以用 `map<preSum, index>` 这一招, 来找到之前存在过的preSum 的index, 来track max length
10+
- Template:
11+
- 1. init preSum = 0, `map.put(0, -1)`
12+
- 2. maintain `max = Math.max(max, i - map.get(preSum))`
13+
- 3. keep updating map with new presum `map.put(preSum, i)`
614

715
```
816
/*

‎Java/Continuous Subarray Sum.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1522910259
3-
tags: Math, DP, Coordinate DP, Subarray
3+
tags: Math, DP, Coordinate DP, Subarray, PreSum
44

55
给一个非负数的数列和数字k(可正负, 可为0). 找到连续子序列(长度超过2), 使得这个subarray的sum 是 k的倍数. 问: 是否可能?
66

‎Java/Decode Ways II.java‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -26,9 +26,11 @@
2626
'B' -> 2
2727
...
2828
'Z' -> 26
29-
Beyond that, now the encoded string can also contain the character '*', which can be treated as one of the numbers from 1 to 9.
29+
Beyond that, now the encoded string can also contain the character '*',
30+
which can be treated as one of the numbers from 1 to 9.
3031
31-
Given the encoded message containing digits and the character '*', return the total number of ways to decode it.
32+
Given the encoded message containing digits and the character '*',
33+
return the total number of ways to decode it.
3234
3335
Also, since the answer may be very large, you should return the output mod 109 + 7.
3436

‎Java/Encode and Decode TinyURL.java‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,22 @@ public String decode(String shortUrl) {
3535
}
3636
}
3737

38+
// Use hashcode, and store integer key
39+
public class Codec {
40+
final String PREFIX = "http://tinyurl.com/";
41+
final Map<Integer, String> map = new HashMap<>();
42+
// Encodes a URL to a shortened URL.
43+
public String encode(String longUrl) {
44+
map.put(longUrl.hashCode(), longUrl);
45+
return PREFIX + longUrl.hashCode();
46+
}
47+
48+
// Decodes a shortened URL to its original URL.
49+
public String decode(String shortUrl) {
50+
return map.get(Integer.parseInt(shortUrl.replace(PREFIX, "")));
51+
}
52+
}
53+
3854
// Your Codec object will be instantiated and called as such:
3955
// Codec codec = new Codec();
4056
// codec.decode(codec.encode(url));

‎Java/Excel Sheet Column Title.java‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,29 @@
2929
Thoughts:
3030
26 bits => num / 26 = 1 => 'A' on that digit
3131
*/
32+
// insert
33+
class Solution {
34+
public String convertToTitle(int n) {
35+
if (n <= 0) {
36+
return null;
37+
}
38+
39+
StringBuilder sb = new StringBuilder();
40+
while (n > 0) {
41+
int remain = n % 26;
42+
n = n / 26;
43+
if (remain == 0) {
44+
sb.insert(0, "Z");
45+
n--;
46+
} else {
47+
sb.insert(0, (char)('A' + remain - 1));
48+
}
49+
}
50+
return sb.toString();
51+
}
52+
}
53+
54+
// append
3255
class Solution {
3356
public String convertToTitle(int n) {
3457
if (n <= 0) {

‎Java/Kth Largest Element in an Array.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1531896299
3-
tags: Divide and Conquer, Heap
3+
tags: Divide and Conquer, Heap, Quick Sort
44

55
```
66
/**

‎Java/Meeting Rooms II.java‎

Lines changed: 39 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -4,11 +4,17 @@
44

55
给一串数字pair, 代表会议的开始/结束时间. 找同时又多少个会议发生(需要多少件房间)
66

7-
#### 方法1
7+
#### PriorityQueue, Sweep Line
88
- PriorityQueue + 一个Class来解决.Ｏ(nlogn)
99
- 跟 Number of Airpline in the sky是同一道题
10+
- 跟 Merge Interval 解法一个路子.
1011

11-
#### 方法2: 尝试了一下用一个sorted Array + HashMap
12+
13+
#### Sort Array, count room, endIndex
14+
- 这个方法相对抽象: sort start times, end times, 然后开始过start time
15+
- 一旦start time less < end[endIndex], 那么房间count就++.
16+
17+
#### sorted Array + HashMap
1218
也还行，但是handle edge的时候,HashMap 要小心，因为相同时间start和end的map key 就会重复了。
1319

1420
```
@@ -25,15 +31,6 @@
2531
*/
2632

2733

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-
*/
3734
/*
3835
Thoughts:
3936
Counts the num of concurrent meetings.
@@ -56,11 +53,7 @@ public int minMeetingRooms(Interval[] intervals) {
5653
}
5754
int count = 0;
5855
int max = 0;
59-
PriorityQueue<Point> queue = new PriorityQueue<Point>(new Comparator<Point>() {
60-
public int compare(Point a, Point b) {
61-
return a.pos - b.pos;
62-
}
63-
});
56+
PriorityQueue<Point> queue = new PriorityQueue<Point>(Comparator.comparing(p -> p.pos));
6457

6558
for (Interval interval: intervals) {
6659
queue.offer(new Point(interval.start, 1));
@@ -82,6 +75,36 @@ public int compare(Point a, Point b) {
8275
}
8376
}
8477

78+
79+
// O(nlogn)
80+
class Solution {
81+
public int minMeetingRooms(Interval[] intervals) {
82+
if (intervals == null || intervals.length == 0) {
83+
return 0;
84+
}
85+
int n = intervals.length;
86+
int start[] = new int[n], end[] = new int[n];
87+
for(int i=0; i < n; i++) {
88+
start[i] = intervals[i].start;
89+
end[i] = intervals[i].end;
90+
}
91+
92+
Arrays.sort(start);
93+
Arrays.sort(end);
94+
95+
int rooms = 0;
96+
int indexEnd = 0;
97+
for(int i = 0; i < n; i++) {
98+
if (start[i] < end[indexEnd]) {
99+
rooms++;
100+
} else {
101+
indexEnd++;
102+
}
103+
}
104+
return rooms;
105+
}
106+
}
107+
85108
/*
86109
Thoughts: This seems to be: how many concurrent meetings do we have?
87110
Just return the count that we used in Meeting I.

0 commit comments

Comments
 (0)