Skip to content

Commit a8a9cf4

Browse files
awangdevawangdev
committed
crush m
1 parent b8112db commit a8a9cf4

62 files changed

Lines changed: 7564 additions & 5364 deletions

Some content is hidden

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

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

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,10 @@
11
M
2+
tags: Stack, Tree, BFS
23

3-
简单的level traversal.根据level奇数偶数而add到不同位子.
4+
#### Queue
5+
- 简单的level traversal.根据level奇数偶数而add到不同位子.
6+
- Option1: based on level % 2, insert to front/end of list
7+
- Option2: based on level, insert right/left of node into queue
48

59
```
610
/*

‎Java/ColorGrid.java‎

Lines changed: 12 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,14 @@
11
M
2+
1527959005
3+
tags: Hash Table, Design
24

3-
用HashMap， 理解题目规律，因为重复的计算可以被覆盖，所以是个优化题。
4-
5-
消灭重合点:
6-
如果process当下col, 其实要减去过去所有加过的row的交接点。。。
7-
再分析，就是每次碰到row 取一个单点, sumRow += xxx。
8-
然后process当下col时候， sum += colValue * N - sumRow. 就等于把交叉所有row（曾经Process过的row）的点减去了。很方便。
9-
10-
最后read in 是O(P), process也是O(P).
5+
#### basic implementation
6+
- 用HashMap， 理解题目规律，因为重复的计算可以被覆盖，所以是个优化题。没有什么太大的悬念和意义.
7+
- 消灭重合点:
8+
- 如果process当下col, 其实要减去过去所有加过的row的交接点。。。
9+
- 再分析，就是每次碰到row 取一个单点, sumRow += xxx。
10+
- 然后process当下col时候， sum += colValue * N - sumRow. 就等于把交叉所有row（曾经Process过的row）的点减去了。很方便。
11+
- 最后read in 是O(P), process也是O(P).
1112

1213

1314
```
@@ -16,7 +17,9 @@
1617
HackerRank.
1718
You are given an N×NN×N grid. Each cell has the color white (color 0) in the beginning.
1819
19-
Each row and column has a certain color associated with it. Filling a row or column with a new color VV means changing all the cells of that row or column to VV (thus overriding the previous colors of the cells).
20+
Each row and column has a certain color associated with it.
21+
Filling a row or column with a new color VV means changing all the cells of
22+
that row or column to VV (thus overriding the previous colors of the cells).
2023
2124
Now, given a sequence of PP such operations, calculate the sum of the colors in the final grid.
2225

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

Lines changed: 8 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,12 @@
11
M
2-
3-
写个Inorder和Postorder的例子。利用他们分left/right subtree的规律解题。
4-
5-
Postorder array 的末尾， 就是当下层的root.
6-
在Inorder array 里面找到这个root,就刚好把左右两边分割成left/right tree。
7-
8-
这题比较tricky地用了一个helper做recursive。 特别要注意处理index的变化, precisely考虑开头结尾
9-
10-
可惜有个不可避免的O(n) find element in array.
2+
tags: Array, Tree, DFS
3+
4+
#### DFS
5+
- 写个Inorder和Postorder的例子。利用他们分left/right subtree的规律解题。
6+
- Postorder array 的末尾， 就是当下层的root.
7+
- 在Inorder array 里面找到这个root,就刚好把左右两边分割成left/right tree。
8+
- 这题比较tricky地用了一个helper做recursive。 特别要注意处理index的变化, precisely考虑开头结尾
9+
- 可惜有个不可避免的O(n) find element in array.
1110

1211
```
1312
/*

‎Java/Container With Most Water.java‎

Lines changed: 15 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,20 @@
11
M
2+
1527960660
3+
tags: Two Pointers, Array
4+
5+
#### Two Pointers
6+
- 木桶理论。盛水的最高取决于最低的那面墙。
7+
- 左右两墙，往中间跑动。
8+
- 另:若一面墙已经小于另外一面，就要移动，换掉矮墙（可能下一面更高，或更低)
9+
- 但决不能换掉当下的高墙，因为低墙已经limit的盛水的上限，若高墙移动，导致两墙之间距离减少，就注定水量更少了。（弄啥来，不能缺心眼啊）
210

3-
类似木桶理论。盛水的最高取决于最低的那面墙。
4-
左右两墙，往中间跑动。
5-
另，若一面墙已经小于另外一面，就要移动，换掉矮墙（可能下一面更高，或更低）；但决不能换掉当下的高墙，因为低墙已经limit的盛水的上限，若高墙移动，导致两墙之间距离减少，就注定水量更少了。（弄啥来，不能缺心眼啊）
611
```
712
/*
8-
Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
13+
Given n non-negative integers a1, a2, ..., an,
14+
where each represents a point at coordinate (i, ai).
15+
n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).
16+
Find two lines, which together with x-axis forms a container,
17+
such that the container contains the most water.
918
1019
Example
1120
Given [1,3,2], the max area of the container is 2.
@@ -27,10 +36,6 @@
2736
On the other hand, if lett wall > right wall, right--.
2837
*/
2938
public class Solution {
30-
/**
31-
* @param heights: an array of integers
32-
* @return: an integer
33-
*/
3439
public int maxArea(int[] heights) {
3540
if (heights == null || heights.length == 0) {
3641
return 0;
@@ -39,7 +44,8 @@ public int maxArea(int[] heights) {
3944
int right = heights.length - 1;
4045
int maxWater = Integer.MIN_VALUE;
4146
while (left < right) {
42-
maxWater = Math.max(maxWater, (right-left) * (heights[left] < heights[right] ? heights[left] : heights[right]));
47+
int lowWall = heights[left] < heights[right] ? heights[left] : heights[right];
48+
maxWater = Math.max(maxWater, (right - left) * lowWall);
4349
if (heights[left] < heights[right]) {
4450
left++;
4551
} else {

‎Java/Convert Binary Search Tree to Doubly Linked List.java‎

Lines changed: 23 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1,14 +1,17 @@
11
M
2-
tags: BST
2+
1527961955
3+
tags: Tree, Linked List
34

4-
会iterative traverse Binary Search Tree就好（Stack && handle left-dig-down）, 然后create Doubly-ListNode 时候注意就好.
5+
#### Inorder Traversal, Linked List
6+
- 会iterative traverse Binary Search Tree（Stack && handle left-dig-down）
7+
- create Doubly-ListNode, 注意用一个dNode作为tail node of the list
58

6-
注意inorder traversal在check right node的事后，
7-
不论right == null or != null, 每次都要强行move to right.
8-
9-
如果不node = node.right,
10-
很可能发生窘境：
11-
node alays = stack.top(), 然后stack.top()一直是一开始把left 全部遍历的内容。所以就会infinite loop, 永远在左边上下上下。
9+
##### Iterative inorder traversal
10+
- 在check right node的事后，
11+
- 不论right == null or != null, 每次都要强行move to right.
12+
- 如果不node = node.right,
13+
- 很可能发生窘境：
14+
- node always = stack.top(), 然后stack.top()一直是一开始把left 全部遍历的内容。所以就会infinite loop, 永远在左边上下上下。
1215

1316
```
1417
/*
@@ -56,9 +59,9 @@
5659
Inorder with 1 stack: peek add left till end, pop and add, then push right node.
5760
5861
Everytime when pop out a node and add, make it a new boubllistnode
59-
dNode.next = curr
60-
curr.pre = dNode.next
61-
dNode = dNode.next
62+
tail.next = curr
63+
curr.pre = tail.next
64+
tail = tail.next
6265
6366
boarder case: if null, return a null.
6467
*/
@@ -68,25 +71,27 @@ public DoublyListNode bstToDoublyList(TreeNode root) {
6871
return null;
6972
}
7073
//Init stack
71-
Stack<TreeNode> stack = new Stack<TreeNode>();
74+
Stack<TreeNode> stack = new Stack<>();
7275
TreeNode node = root;
7376
stack.push(node);
77+
7478
//Create DoublyListNode header
7579
DoublyListNode dummy = new DoublyListNode(0);
76-
DoublyListNode dNode = dummy;
77-
80+
DoublyListNode tail = dummy;
7881

7982
while(!stack.isEmpty()) {
83+
// Add left till leaf
8084
while (node != null && node.left != null) {
8185
stack.push(node.left);
8286
node = node.left;
8387
}
84-
//add node
88+
89+
//add node, and doubly link with prev node
8590
node = stack.pop();
8691
DoublyListNode curr = new DoublyListNode(node.val);
87-
dNode.next = curr;
88-
curr.prev = dNode;
89-
dNode = dNode.next;
92+
tail.next = curr;
93+
curr.prev = tail;
94+
tail = tail.next;
9095

9196
//check right node and add to stack
9297
node = node.right;
@@ -96,20 +101,7 @@ public DoublyListNode bstToDoublyList(TreeNode root) {
96101
}
97102

98103
return dummy.next;
99-
100104
}
101105
}
102106

103-
104-
105-
106-
107-
108-
109-
110-
111-
112-
113-
114-
115107
```

‎Java/Copy List with Random Pointer.java‎

Lines changed: 10 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,14 @@
11
M
2+
1527962398
3+
tags: Hash Table, Linked List
24

3-
Basic Implementation, 其中用了一下HashMap:
5+
deep copy linked list. linked list 上有random pointer to other nodes.
46

5-
遍历head.next .... null.
6-
每一步都check map里面有没有head。没有？加上。
7-
每一步都check map里面有没有head.random。没有？加上。
7+
#### HashMap
8+
- Basic Implementation
9+
- use node and dummy to hold new list, 遍历head.next .... null.
10+
- 每一步都check map里面有没有head. 没有? 加上
11+
- 每一步都check map里面有没有head.random. 没有? 加上
812

913
```
1014
/*
@@ -31,7 +35,6 @@ Hide Similar Problems (M) Clone Graph
3135
*/
3236

3337
/*
34-
Recap: 12.10.2015
3538
Iterative through the list.
3639
Use a dummyHead and return dummyHead.next at the end.
3740
In each iteration, check if Head is already exist, or make a new one
@@ -41,7 +44,7 @@ Hide Similar Problems (M) Clone Graph
4144
border case: if head == null, return null
4245
*/
4346

44-
public class Solution {
47+
class Solution {
4548
public RandomListNode copyRandomList(RandomListNode head) {
4649
if (head == null) {
4750
return null;
@@ -51,7 +54,7 @@ public RandomListNode copyRandomList(RandomListNode head) {
5154
RandomListNode dummy = node;
5255

5356
//HashMap to mark node
54-
HashMap<RandomListNode, RandomListNode> map = new HashMap<RandomListNode, RandomListNode>();
57+
HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
5558

5659
while(head != null) {
5760
//process head. (we already know head!=null)

‎Java/Count of Smaller Number.java‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
1-
M
1+
R
2+
tags: Segment Tree, Binary Search
23

34
和平时的segment tree问题不同。 0 ～ n-1代表实际数字。是造一个based on real value的segment tree.
45
Modify时，把array里面的value带进去，找到特定的位子（leaf）,然后count+1.
@@ -39,6 +40,10 @@ Give you an integer array (index from 0 to n-1, where n is the size of this arra
3940
Challenge
4041
Could you use three ways to do it.
4142
43+
1. Just loop
44+
2. Sort and binary search
45+
3. Build Segment Tree and Search.
46+
4247
Just loop
4348
Sort and binary search
4449
Build Segment Tree and Search.

‎Java/Delete Digits.java‎

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,13 @@
11
M
2+
Tags: Greedy, Priority Queue
23

3-
数位靠前的，权值更大. 所以硬来把靠前的相对更大的（跟following digit相比）去掉。
4+
#### Priority Queue
5+
- TODO: parse into node(index, digitValue)
6+
- find the top k, and remove from char array
7+
- O(nlogn) time
8+
9+
#### Greedy
10+
- 数位靠前的，权值更大. 所以硬来把靠前的相对更大的（跟following digit相比）去掉。
411

512
```
613
/*

‎Java/Encode and Decode Strings.java‎

Lines changed: 20 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,20 +1,19 @@
11
M
2+
1527968983
3+
tags: String
24

3-
方法1:
4-
用数字+"#"+string来encode.
5-
基于我们自己定的规律, 在decode的里面不需要过多地去check error input, assume所有input都是规范的.
6-
decode就是找"#",然后用"#"前的数字截取后面的string.
5+
如题.
76

8-
9-
10-
Old Solution:
11-
Cast character into int. 串联起来, seperate by "LINE".
12-
handle empty list [], or just null: 要把Null特别mark一下为‘NULL’, 这样decode时才能check到。 adminadmin
7+
#### String
8+
- 'word.length()#word' 这样encode, 可以避免遇到#
9+
- 基于我们自己定的规律, 在decode的里面不需要过多地去check error input, assume所有input都是规范的.
10+
- decode就是找"#",然后用"#"前的数字截取后面的string.
1311

1412

1513
```
1614
/*
17-
Design an algorithm to encode a list of strings to a string. The encoded string is then sent over the network and is decoded back to the original list of strings.
15+
Design an algorithm to encode a list of strings to a string.
16+
The encoded string is then sent over the network and is decoded back to the original list of strings.
1817
1918
Machine 1 (sender) has the function:
2019
@@ -38,20 +37,19 @@ vector<string> decode(string s) {
3837
Implement the encode and decode methods.
3938
4039
Note:
41-
The string may contain any possible characters out of 256 valid ascii characters. Your algorithm should be generalized enough to work on any possible characters.
42-
Do not use class member/global/static variables to store states. Your encode and decode algorithms should be stateless.
43-
Do not rely on any library method such as eval or serialize methods. You should implement your own encode/decode algorithm.
40+
The string may contain any possible characters out of 256 valid ascii characters.
41+
Your algorithm should be generalized enough to work on any possible characters.
4442
43+
Do not use class member/global/static variables to store states.
44+
Your encode and decode algorithms should be stateless.
4545
46-
Tags: String
47-
Similar Problems: (E) Count and Say, (M) Serialize and Deserialize Binary Tree
48-
46+
Do not rely on any library method such as eval or serialize methods.
47+
You should implement your own encode/decode algorithm.
4948
*/
5049

5150

5251
/*
53-
Recap 3.28.2016
54-
Use number+"#" to mark a string. Append them all.
52+
Use word.length() + "#" + word to mark a string. Append them all.
5553
*/
5654
public class Codec {
5755

@@ -69,7 +67,7 @@ public String encode(List<String> strs) {
6967

7068
// Decodes a single string to a list of strings.
7169
public List<String> decode(String s) {
72-
List<String> strs = new ArrayList<String>();
70+
List<String> strs = new ArrayList<>();
7371
if (s == null || s.length() == 0) {
7472
return strs;
7573
}
@@ -78,9 +76,9 @@ public List<String> decode(String s) {
7876
int ind = s.indexOf("#", start);
7977
int leng = Integer.parseInt(s.substring(start, ind));
8078

81-
start = ind + 1 + leng;
82-
strs.add(s.substring(ind + 1, start));
83-
79+
int end = ind + 1 + leng;
80+
strs.add(s.substring(ind + 1, end));
81+
start = end;
8482
}
8583
return strs;
8684
}

‎Java/Fast Power.java‎

Lines changed: 8 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,14 @@
11
M
2+
1527969371
3+
tags: DFS, Divide and Conquer
24

3-
a^n可以被拆解成(a*a*a*a....*a)， 是乘机形式，而%是可以把每一项都mod一下的。所以就拆开来take mod.
5+
如题: Calculate the a^n % b where a, b and n are all 32bit integers.
46

5-
这里用个二分的方法，recursively二分下去，直到n/2为0或者1，然后分别对待.
6-
7-
注意1: 二分后要conquer，乘积可能大于Integer.MAX_VALUE, 所以用个long.
8-
9-
注意2: 要处理n%2==1的情况，二分时候自动省掉了一份，要乘一下。
7+
#### Divide and Conquer
8+
- a^n可以被拆解成(a*a*a*a....*a)， 是乘机形式，而%是可以把每一项都mod一下的。所以就拆开来take mod.
9+
- 这里用个二分的方法，recursively二分下去，直到n/2为0或者1，然后分别对待.
10+
- 注意1: 二分后要conquer，乘积可能大于Integer.MAX_VALUE, 所以用个long.
11+
- 注意2: 要处理n%2==1的情况，二分时候自动省掉了一份 a，要乘一下。
1012

1113

1214
```
@@ -36,10 +38,6 @@
3638
Note: when n is odd number, it cannot be evenly divided into n/2 and n/2. This case needs special treatment: n = n/2 + n/2 + 1;
3739
*/
3840
class Solution {
39-
/*
40-
* @param a, b, n: 32bit integers
41-
* @return: An integer
42-
*/
4341
public int fastPower(int a, int b, int n) {
4442
if (n == 0) {
4543
return 1 % b;

0 commit comments

Comments
 (0)