Skip to content

Commit 11459d2

Browse files
awangdevawangdev
committed
binary search, bit, palindrome
1 parent 910aa89 commit 11459d2

9 files changed

Lines changed: 1077 additions & 427 deletions

‎Java/Copy Books.java‎

Lines changed: 88 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,14 @@
1-
R
1+
H
22
1518424818
3-
tags: DP
3+
tags: DP, Binary Search
44

5+
#### 方法1: Binary Search
6+
- 根据: 每个人花的多少时间(time)来做binary search: 每个人花多久时间, 可以在K个人之内, 用最少的时间完成?
7+
- time variable的范围不是index, 也不是page大小. 而是[minPage, pageSum]
8+
- validation 的时候注意3种情况: 人够用 k>=0, 人不够所以结尾减成k<0, 还有一种是time(每个人最多花的时间)小于当下的页面, return -1
9+
- O(nLogM). n = pages.length; m = sum of pages.
10+
11+
#### 方法2: DP
512
k个人copy完i本书.
613
定义Integer.MAX_VALUE的地方需要注意.
714
Review: 为什么有i level的iteration? Chapter4.1
@@ -20,6 +27,85 @@
2027
2128
*/
2229

30+
/*
31+
Thoughts:
32+
Stupid way of asking 'slowest copier to finish at earliest time'. It does not make sense.
33+
The question does not provide speed, what does 'slow/fast' mean?
34+
The question does not distinguish each copier, what does 'earliest' time mean?
35+
36+
Given the sample results, it's asking:
37+
what's the minimum time can be used to finish all books with given k people.
38+
39+
- 1 book cannot be split to give to multiple people
40+
- cannot sort the book array
41+
42+
A person at minimum needs to finish 1 book, and a person at maximum can read all books.
43+
should find x in [min, max] such that all books can be finished.
44+
The person can read at most x mins, but don't over-read if next book in the row can't be covered within x mins.
45+
46+
It's find to not use up all copiers.
47+
*/
48+
public class Solution {
49+
public int copyBooks(int[] pages, int k) {
50+
if (pages == null || pages.length == 0) {
51+
return 0;
52+
}
53+
int m = pages.length;
54+
int min = Integer.MAX_VALUE;
55+
int sum = 0;
56+
57+
// Find minimum read mins
58+
for (int page : pages) {
59+
min = Math.min(min, page);
60+
sum += page;
61+
}
62+
63+
int start = min;
64+
int end = sum;
65+
while (start + 1 < end) {
66+
int mid = start + (end - start) / 2; // mid: total time spent per person
67+
int validation = validate(pages, mid, k);
68+
if (validation < 0) {
69+
start = mid;
70+
} else {
71+
end = mid;
72+
}
73+
}
74+
75+
if (validate(pages, start, k) >= 0) {
76+
return start;
77+
} else {
78+
return end;
79+
}
80+
}
81+
82+
/*
83+
Validate if all copies are utilized to finish.
84+
Return 0 if k used to finish books.
85+
Return negative needing more copier, which means value is too small.
86+
Return postivie, if value is too big, and copies are not utilized.
87+
*/
88+
private int validate(int[] pages, int totalTimePerPerson, int k) {
89+
int temp = 0;
90+
for (int i = 0; i < pages.length; i++) {
91+
temp += pages[i];
92+
if (temp == totalTimePerPerson) {
93+
temp = 0;
94+
k--;
95+
} else if (temp < totalTimePerPerson) {
96+
if (i + 1 >= pages.length || temp + pages[i + 1] > totalTimePerPerson) {
97+
// no next page; or not enough capacity to read next page
98+
temp = 0;
99+
k--;
100+
}
101+
// else: (i + 1 < pages.length && temp + pages[i + 1] <= totalTimePerPerson)
102+
} else {
103+
return -1;
104+
}
105+
}
106+
return k;
107+
}
108+
}
23109

24110
/*
25111
Thoughts:

‎Java/Find the Duplicate Number.java‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
M
22
1520924985
3-
tags: Array, Two Pointer, Binary Search
3+
tags: Array, Two Pointers, Binary Search
44

55
- 注意不要思维定式: 以为mid是index
66
- 这里mid其实是binary search on value [1, n] 的一个value.

‎Java/Game of Life.java‎

Lines changed: 170 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,31 @@
1+
M
2+
1521012714
3+
tags: Array
4+
5+
#### basic
6+
- 简单的implementation, 把count function写清楚就好.
7+
- time: O(mn), extra space: O(mn)
8+
- 注意结尾要一个个board[i][j]copy
9+
10+
#### follow up
11+
unlimited border? 可能需要分割board. 用大框分割, 每次换行的时候, 重复计算2行就好了. see details below.
12+
13+
#### improvement: do it in place!
14+
- time: O(mn), extra space: O(1)
15+
- bit manipulation: 用第二个bit来存previous value.
16+
- 因为我们只考虑 0 和 1 而已, 所以可以这样取巧. 但是并不scalable.
17+
- 如果需要存multiple state, 可能需要移动更多位, 或者用一个 state map
18+
- 注意 bit manipulation 的细节: <<1, >>1, 还有 mast的用法: |, &
19+
20+
21+
```
122
/*
2-
According to the Wikipedia's article:
3-
"The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
23+
According to the Wikipedia's article: "The Game of Life, also known simply as Life,
24+
is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
425
526
Given a board with m by n cells, each cell has an initial state live (1) or dead (0).
6-
Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules
7-
(taken from the above Wikipedia article):
27+
Each cell interacts with its eight neighbors (horizontal, vertical, diagonal)
28+
using the following four rules (taken from the above Wikipedia article):
829
930
Any live cell with fewer than two live neighbors dies, as if caused by under-population.
1031
Any live cell with two or three live neighbors lives on to the next generation.
@@ -16,27 +37,158 @@ Write a function to compute the next state (after one update) of the board given
1637
Could you solve it in-place? Remember that the board needs to be updated at the same time:
1738
You cannot update some cells first and then use their updated values to update other cells.
1839
In this question, we represent the board using a 2D array.
19-
In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array.
20-
How would you address these problems?
40+
In principle, the board is infinite, which would cause problems
41+
when the active area encroaches the border of the array. How would you address these problems?
2142
Credits:
22-
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
23-
24-
Hide Company Tags Google TinyCo
25-
Hide Tags Array
26-
Hide Similar Problems (M) Set Matrix Zeroes
2743
2844
*/
2945

3046
/*
31-
Thoughts:
32-
https://segmentfault.com/a/1190000003819277
33-
http://my.oschina.net/Tsybius2014/blog/514447
34-
build state machine.
35-
take mod of 2 at the end.
47+
Thoughts
48+
1:
49+
< 2 => 0 => STATE = 2
50+
> 3 => 0 => STATE = 2
51+
==2, ==3 => 1 => 1
52+
53+
O(mn)
3654
*/
3755

38-
public class Solution {
56+
// time O(mn * 8) = O(mn), Space(mn)
57+
class Solution {
58+
public void gameOfLife(int[][] board) {
59+
if (board == null || board.length == 0 || board[0] == null || board[0].length ==0) {
60+
return;
61+
}
62+
int m = board.length;
63+
int n = board[0].length;
64+
int[][] newBoard = new int[m][n];
65+
66+
for (int i = 0; i < m; i++) {
67+
for (int j = 0; j < n; j++) {
68+
int countNeighbor = count(board, i , j);
69+
if (board[i][j] == 1) {
70+
newBoard[i][j] = (countNeighbor < 2 || countNeighbor > 3) ? 0 : 1;
71+
} else { // board[i][j] == 0
72+
newBoard[i][j] = count(board, i, j) == 3 ? 1 : 0;
73+
}
74+
}
75+
}
76+
// copy
77+
for (int i = 0; i < m; i++) {
78+
for (int j = 0; j < n; j++) {
79+
board[i][j] = newBoard[i][j];
80+
}
81+
}
82+
}
83+
84+
int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};
85+
int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};
86+
87+
// optimize: no need to count all.
88+
private int count(int[][] board, int x, int y) {
89+
int count = 0;
90+
for (int i = 0; i < dx.length; i++) {
91+
int mX = x + dx[i];
92+
int mY = y + dy[i];
93+
if (mX >= 0 && mX < board.length && mY >= 0 && mY < board[0].length) {
94+
count += board[mX][mY];
95+
}
96+
}
97+
return count;
98+
}
99+
}
100+
101+
102+
/*
103+
Use 2nd bit as storage for previous status '0' or '1'
104+
0 => 00
105+
1 => 10
106+
107+
This solution is not quite scalable because it only works with '0' and '1'
108+
109+
We could implement state map if having multiple conditions.
110+
*/
111+
class Solution {
39112
public void gameOfLife(int[][] board) {
113+
if (board == null || board.length == 0 || board[0] == null || board[0].length ==0) {
114+
return;
115+
}
116+
int m = board.length;
117+
int n = board[0].length;
118+
119+
// Shift: use 2nd bit to store previous condition
120+
for (int i = 0; i < m; i++) {
121+
for (int j = 0; j < n; j++) {
122+
board[i][j] = board[i][j] << 1;
123+
}
124+
}
40125

126+
// Count and calculate
127+
for (int i = 0; i < m; i++) {
128+
for (int j = 0; j < n; j++) {
129+
int countNeighbor = count(board, i , j);
130+
131+
// Access 2nd bit for previous value
132+
if ((board[i][j] >> 1) == 1) {
133+
board[i][j] = (countNeighbor >= 2 && countNeighbor <= 3) ? board[i][j] | 1 : board[i][j];
134+
} else { // board[i][j] == 0
135+
board[i][j] = count(board, i, j) == 3 ? board[i][j] | 1 : board[i][j];
136+
}
137+
}
138+
}
139+
140+
// Filter out 2nd bit and only 1st bit as result
141+
for (int i = 0; i < m; i++) {
142+
for (int j = 0; j < n; j++) {
143+
board[i][j] = board[i][j] & 1; // remove 2nd bit, which stores previous value
144+
}
145+
}
146+
}
147+
148+
int[] dx = {0, 0, 1, -1, -1, -1, 1, 1};
149+
int[] dy = {1, -1, 0, 0, -1, 1, -1, 1};
150+
151+
// optimize: no need to count all.
152+
private int count(int[][] board, int x, int y) {
153+
int count = 0;
154+
for (int i = 0; i < dx.length; i++) {
155+
int mX = x + dx[i];
156+
int mY = y + dy[i];
157+
if (mX >= 0 && mX < board.length && mY >= 0 && mY < board[0].length) {
158+
count += (board[mX][mY] >> 1);
159+
}
160+
}
161+
return count;
41162
}
42-
}
163+
}
164+
165+
/*
166+
167+
Unlimited? board太大, 一个电脑放不下, 怎么分割?
168+
定一个大框
169+
每次移动大框的时候, 留着重复2就行了.
170+
x x x x x x x x x x
171+
x x x x x x x x x x
172+
x x x x x x x x x x
173+
x x x x x x x x x x
174+
x x x x x x x x x x
175+
x x x x x x x x x x
176+
x x x x x x x x x x
177+
x x x x x x x x x x
178+
x x x x x x x x x x
179+
x x x x x x x x x x
180+
181+
a a a a a a a a a a
182+
y y y y y y y y y y
183+
x x x x x x x x x x
184+
x x x x x x x x x x
185+
x x x x x x x x x x
186+
x x x x x x x x x x
187+
x x x x x x x x x x
188+
x x x x x x x x x x
189+
x x x x x x x x x x
190+
x x x x x x x x x x
191+
x x x x x x x x x x
192+
x x x x x x x x x x
193+
*/
194+
```

0 commit comments

Comments
 (0)