Skip to content

Commit 904ba02

Browse files
awangdevawangdev
committed
3.20.2016
1 parent 9d7d6c8 commit 904ba02

13 files changed

+777
-616
lines changed

‎Java/Hash Function.java

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,12 @@
88
Hash的用法是：给一个string key, 转换成数字，从而把size变得更小。
99
真实的implementation还要处理collision, 可能需要design hash function 等等。
1010

11+
12+
每一步都：
13+
hashRst = hashRst * 33 + (int)(key[i]);
14+
hashRst = hashRst % HASH_SIZE;
15+
原因是，hashRst会变得太大，所以不能算完再%...
16+
1117
```
1218
/*
1319
In data structure Hash, hash function is used to convert a string(or any other type)
@@ -19,7 +25,7 @@ In data structure Hash, hash function is used to convert a string(or any other t
1925
2026
hashcode("abcd") = (ascii(a) * 33^3 + ascii(b) * 33^2 + ascii(c) *33^1 + ascii(d)*33^0) % HASH_SIZE
2127
22-
= (97* 333 + 98 * 332 + 99 * 33 +100) % HASH_SIZE
28+
= (97* 33^3 + 98 * 33^2 + 99 * 33 +100) % HASH_SIZE
2329
2430
= 3595978 % HASH_SIZE
2531

‎Java/HashWithArray.java

100644100755
Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,7 @@
1+
E
2+
3+
4+
```
15
/*
26
Self Test:
37
Implement HashTable with just array and integer.
@@ -62,8 +66,4 @@ public int get(int key) {
6266

6367

6468

65-
66-
67-
68-
69-
69+
```

‎Java/IndexMatch.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
E
2+
3+
有序, 假设有这样的数字:target.
4+
target 左边的数字，一定不比index大，target右边的数字，一定比index大。
5+
这样可以binary search.O(logn)
6+
7+
```
8+
/*
9+
来自网上uber面经：给一个有序数组（不含重复），返回任意一个数字，这个数字的值和它的数组下标相等
10+
11+
可能的follow up:
12+
1. 如果含有重复数字怎么办？
13+
如果有序，也没问题，还是binary search
14+
15+
2. 另一种follow up:找这样数字的边界.
16+
如果存在，那么和index match的一定在一块.
17+
找到任何一个candiate, 找边界，也可以binary search,只是match的condition不同罢了。
18+
19+
*/
20+
//Binary search.
21+
import java.io.*;
22+
import java.util.*;
23+
class Solution {
24+
25+
public int indexMatch(int[] nums) {
26+
if (nums == null || nums.length == 0) {
27+
return -1;
28+
}
29+
30+
int start = 0;
31+
int end = nums.length - 1;
32+
while (start + 1 < end) {
33+
int mid = start + (end - start)/2;
34+
if (nums[mid] == mid) {
35+
return mid;
36+
} else if (nums[mid] < mid) {
37+
start = mid;
38+
} else {//nums[mid] > mid
39+
end = mid;
40+
}
41+
}
42+
43+
return -1;
44+
}
45+
46+
public static void main(String[] args) {
47+
System.out.println("START");
48+
int[] input = {-1, 0, 1, 3, 5, 8, 9};//return 3
49+
Solution sol = new Solution();
50+
int rst = sol.indexMatch(input);
51+
System.out.println(rst);
52+
}
53+
}
54+
```

‎Java/LRU Cache.java

Lines changed: 7 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,10 @@
1414
2. 用双向的pointer: pre和next, 当需要除掉任何一个node的时候，只要知道要除掉哪一个，
1515
直接把node.pre和node.next耐心连起来就好了，node就自然而然的断开不要了。
1616

17-
一旦知道怎么解决了，就不是很特别，并不是难写的算法。
17+
一旦知道怎么解决了，就不是很特别，并不是难写的算法:
18+
moveToHead()
19+
insertHead()
20+
remove()
1821

1922
```
2023
/*
@@ -92,12 +95,7 @@ public void set(int key, int value) {
9295
map.put(key, node);
9396
}
9497
}
95-
96-
public void moveToTail(DoubleLinkedListNode node) {
97-
remove(node);
98-
insertTail(node);
99-
}
100-
98+
10199
public void moveToHead(DoubleLinkedListNode node) {
102100
remove(node);
103101
insertHead(node);
@@ -111,22 +109,13 @@ public void insertHead(DoubleLinkedListNode node) {
111109
node.next = next;
112110
next.prev = node;
113111
}
114-
115-
public void insertTail(DoubleLinkedListNode node) {
116-
DoubleLinkedListNode prev = tail.prev;
117-
prev.next = node;
118-
node.prev = prev;
119-
node.next = tail;
120-
tail.prev = node;
121-
}
122-
112+
123113
public void remove(DoubleLinkedListNode node) {
124114
DoubleLinkedListNode front = node.prev;
125115
DoubleLinkedListNode end = node.next;
126116
front.next = end;
127117
end.prev = front;
128-
}
129-
118+
}
130119
}
131120
/*
132121
First Attempt: time exceeds

‎Java/Meeting Rooms II.java

100644100755
Lines changed: 36 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,14 @@
1-
开会王，还是可以用PriorityQueue + 一个Class来解决。
2-
这里有尝试了一下用一个sorted Array + HashMap： 也还行，但是handle edge的时候,HashMap 要小心，因为相同时间start和end的map key 就会重复了。
1+
M
2+
3+
4+
方法1:PriorityQueue + 一个Class来解决。Ｏ(nlogn)
5+
6+
方法2:这里有尝试了一下用一个sorted Array + HashMap： 也还行，但是handle edge的时候,HashMap 要小心，因为相同时间start和end的map key 就会重复了。
37

48
```
59
/*
6-
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
10+
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei),
11+
find the minimum number of conference rooms required.
712
813
For example
914
Given [[0, 30],[5, 10],[15, 20]],
@@ -74,43 +79,42 @@ public int minMeetingRooms(Interval[] intervals) {
7479

7580
// Similar to Meeting Room I, using Point class and Priorityqueue
7681
// Creating a customized class, but makes the problem a bit easier to think.
77-
7882
public class Solution {
79-
class Point {
80-
int pos;
81-
int flag;
82-
public Point(int pos, int flag) {
83-
this.pos = pos;
84-
this.flag = flag;
85-
}
86-
}
83+
class Point {
84+
int pos, flag;
85+
public Point(int pos, int flag) {
86+
this.pos = pos;
87+
this.flag = flag;
88+
}
89+
}
8790
public int minMeetingRooms(Interval[] intervals) {
8891
if (intervals == null || intervals.length == 0) {
89-
return true;
92+
return 0;
9093
}
91-
PriorityQueue<Point> queue = new PriorityQueue<Point>(
92-
new Comparator<Point>(){
93-
public int compare(Point a, Point b){
94-
return (a.pos - b.pos);
95-
}
96-
}
97-
);
98-
for (Interval range : intervals) {
99-
queue.add(new Point(range.start, 1));
100-
queue.add(new Point(range.end, -1));
94+
95+
PriorityQueue<Point> queue = new PriorityQueue<Point>(2, new Comparator<Point>() {
96+
public int compare(Point p1, Point p2) {
97+
return p1.pos - p2.pos;
98+
}
99+
});
100+
101+
for (int i = 0; i < intervals.length; i++) {
102+
queue.offer(new Point(intervals[i].start, 1));
103+
queue.offer(new Point(intervals[i].end, -1));
101104
}
102105
int count = 0;
103-
int max = 0;
106+
int rst = 0;
104107
while (!queue.isEmpty()) {
105-
Point p = queue.poll();
106-
count += p.flag;
107-
while(!queue.isEmpty() && p.pos == queue.peek().pos) {
108-
p = queue.poll();
109-
count += p.flag;
110-
}
111-
max = Math.max(max, count);
108+
Point p = queue.poll();
109+
count += p.flag;
110+
while (!queue.isEmpty() && p.pos == queue.peek().pos) {
111+
p = queue.poll();
112+
count += p.flag;
113+
}
114+
rst = Math.max(count, rst);
112115
}
113-
return max;
116+
117+
return rst;
114118
}
115119
}
116120
```

‎Java/Meeting Rooms.java

100644100755
Lines changed: 43 additions & 33 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,22 @@
1-
扫描线是个好厨师。
2-
注意接头点要考虑所有开会结会的情况，不要恰巧漏掉相接的点。
3-
这开会的dude是个超人。瞬间移动接上下一个会议。
1+
E
2+
3+
Scan line, class Point{pos, flag}, PriorityQueue排序。计算count
4+
5+
注意接头点要考虑所有开会结会的情况，不要恰巧漏掉相接的点。
6+
开会的是超人。瞬间移动接上下一个会议。
7+
48
```
59
/*
610
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
711
812
For example,
913
Given [[0, 30],[5, 10],[15, 20]],
1014
return false.
15+
16+
Hide Company Tags Facebook
17+
Hide Tags Sort
18+
Hide Similar Problems (H) Merge Intervals (M) Meeting Rooms II
19+
1120
*/
1221

1322
/**
@@ -22,46 +31,47 @@
2231

2332
/*
2433
Thought:
25-
Use scane line.
34+
Use scan line.
2635
Note: special care for edge point: make sure to process all connecting point before shuouting the result.
2736
*/
2837

29-
public class Solution {
30-
class Point {
31-
int pos;
32-
int flag;
33-
public Point(int pos, int flag) {
34-
this.pos = pos;
35-
this.flag = flag;
36-
}
37-
}
38+
//use scan line
39+
public class Solution {
40+
class Point {
41+
int pos, flag;
42+
public Point(int pos, int flag) {
43+
this.pos = pos;
44+
this.flag = flag;
45+
}
46+
}
3847
public boolean canAttendMeetings(Interval[] intervals) {
3948
if (intervals == null || intervals.length == 0) {
40-
return true;
49+
return true;
4150
}
42-
PriorityQueue<Point> queue = new PriorityQueue<Point>(
43-
new Comparator<Point>(){
44-
public int compare(Point a, Point b){
45-
return (a.pos - b.pos);
46-
}
47-
}
48-
);
49-
for (Interval range : intervals) {
50-
queue.add(new Point(range.start, 1));
51-
queue.add(new Point(range.end, -1));
51+
52+
PriorityQueue<Point> queue = new PriorityQueue<Point>(2, new Comparator<Point>() {
53+
public int compare(Point p1, Point p2) {
54+
return p1.pos - p2.pos;
55+
}
56+
});
57+
58+
for (int i = 0; i < intervals.length; i++) {
59+
queue.offer(new Point(intervals[i].start, 1));
60+
queue.offer(new Point(intervals[i].end, -1));
5261
}
5362
int count = 0;
5463
while (!queue.isEmpty()) {
55-
Point p = queue.poll();
56-
count += p.flag;
57-
while(!queue.isEmpty() && p.pos == queue.peek().pos) {
58-
p = queue.poll();
59-
count += p.flag;
60-
}
61-
if (count > 1) {
62-
return false;
63-
}
64+
Point p = queue.poll();
65+
count += p.flag;
66+
while (!queue.isEmpty() && p.pos == queue.peek().pos) {
67+
p = queue.poll();
68+
count += p.flag;
69+
}
70+
if (count > 1) {
71+
return false;
72+
}
6473
}
74+
6575
return true;
6676
}
6777
}

‎Java/Subset.java

100644100755
Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,17 @@
11
M
22

33
最基本的递归题目。
4-
坑：记得一开头sort一下 nums。 因为要升序。
4+
坑：记得一开头sort一下 nums。 因为要升序。那么整体就是O(nlogn)
55

66
注意：用level/index来track到哪一步。最后一level就add into rst
77

88
方法1: subset的概念，取或者不取,backtracking. 当level/index到底，return 一个list.
99

1010
方法2: 用for loop backtracking. 记得：每个dfs recursive call是一种独特可能，先加进rst。
1111

12+
13+
recap:时间久了忘记dfs的两种路子. for loop dfs/backtracking vs. regular dfs
14+
1215
```
1316
/*
1417
Given a set of distinct integers, return all possible subsets.

0 commit comments

Comments
 (0)