Skip to content

Commit d3f8c49

Browse files
awangdevawangdev
committed
2.26.2016
1 parent ecd8853 commit d3f8c49

34 files changed

Lines changed: 1368 additions & 1659 deletions

‎Java/Add and Search Word.java‎

100644100755
Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,13 @@
11
M
22

3-
Trie结构, prefix tree.
4-
节点里面有char, isEnd, HashMap<Character, TrieNode>
5-
记得怎么造trie：无增有移，没node就加，有node就移动。
6-
寻找word也一样逻辑：无错有移。
3+
Trie结构, prefix tree的变形： '.'可以代替任何字符，那么就要iterate这个node所有的children.
74

5+
节点里面有char, isEnd, HashMap<Character, TrieNode>
6+
Build trie = Insert word:没node就加，有node就移动。
7+
Search word:没有node就报错. 到结尾return true
8+
9+
这题因为'.'可以代替任何possible的字符，没一种都是一个新的path，所以recursive做比较好些。
10+
(iterative就要queue了,麻烦点)
811

912
```
1013
/*

‎Java/Alien Dictionary.java‎

100644100755
Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
H
22

3-
Not Done yet
3+
Not Done yet。 Topological sort.
44

55
```
66

‎Java/Building Outline.java‎

100644100755
File mode changed.

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

Lines changed: 0 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -46,11 +46,6 @@
4646

4747

4848
public class Solution {
49-
/**
50-
*@param preorder : A list of integers that preorder traversal of a tree
51-
*@param inorder : A list of integers that inorder traversal of a tree
52-
*@return : Root of a tree
53-
*/
5449
public TreeNode buildTree(int[] preorder, int[] inorder) {
5550
if (preorder.length != inorder.length) {
5651
return null;

‎Java/Convert Expression to Polish Notation.java‎

Lines changed: 84 additions & 77 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,11 @@
1+
H
2+
13
还是Expression Tree (Min-Tree).
4+
25
根据题意，Tree出来以后，来个Pre-order-traversal.
6+
7+
Note: label需要是String.虽然 Operator是长度为1的char, 但是数字可为多位。
8+
39
```
410
/*
511
Given an expression string array, return the Polish notation of this expression. (remove the parentheses)
@@ -25,93 +31,94 @@
2531
*/
2632

2733
public class Solution {
28-
class TreeNode {
29-
String s;
30-
int val;
31-
TreeNode left;
32-
TreeNode right;
33-
public TreeNode(int val, String s) {
34-
this.val = val;
35-
this.s = s;
36-
this.left = null;
37-
this.right = null;
38-
}
39-
}
40-
41-
public TreeNode build(String[] expression) {
42-
if (expression == null || expression.length == 0) {
43-
return null;
44-
}
45-
Stack<TreeNode> stack = new Stack<TreeNode>();
46-
int base = 0;
47-
int val = 0;
48-
49-
for (int i = 0; i < expression.length; i++) {
50-
if (expression[i].equals("(")) {
51-
base += 10;
52-
continue;
53-
}
54-
if (expression[i].equals(")")) {
55-
base -= 10;
56-
continue;
57-
}
58-
val = getWeight(base, expression[i]);
59-
TreeNode node = new TreeNode(val, expression[i]);
60-
while (!stack.isEmpty() && node.val <= stack.peek().val) {
61-
node.left = stack.pop();
62-
}
63-
if (!stack.isEmpty()) {
64-
stack.peek().right = node;
65-
}
66-
stack.push(node);
67-
}
68-
if (stack.isEmpty()) {
69-
return null;
70-
}
71-
TreeNode rst = stack.pop();
72-
while (!stack.isEmpty()) {
73-
rst = stack.pop();
74-
}
75-
return rst;
76-
}
77-
78-
public int getWeight(int base, String s) {
79-
if (s.equals("+") || s.equals("-")) {
80-
return base + 1;
81-
}
82-
if (s.equals("*") || s.equals("/")) {
83-
return base + 2;
84-
}
85-
return Integer.MAX_VALUE;
86-
}
34+
class TreeNode {
35+
String s;
36+
int val;
37+
TreeNode left;
38+
TreeNode right;
39+
public TreeNode(int val, String s) {
40+
this.val = val;
41+
this.s = s;
42+
this.left = null;
43+
this.right = null;
44+
}
45+
}
46+
47+
public TreeNode build(String[] expression) {
48+
if (expression == null || expression.length == 0) {
49+
return null;
50+
}
51+
Stack<TreeNode> stack = new Stack<TreeNode>();
52+
int base = 0;
53+
int val = 0;
54+
55+
for (int i = 0; i < expression.length; i++) {
56+
if (expression[i].equals("(")) {
57+
base += 10;
58+
continue;
59+
}
60+
if (expression[i].equals(")")) {
61+
base -= 10;
62+
continue;
63+
}
64+
val = getWeight(base, expression[i]);
65+
TreeNode node = new TreeNode(val, expression[i]);
66+
while (!stack.isEmpty() && node.val <= stack.peek().val) {
67+
node.left = stack.pop();
68+
}
69+
if (!stack.isEmpty()) {
70+
stack.peek().right = node;
71+
}
72+
stack.push(node);
73+
}
74+
if (stack.isEmpty()) {
75+
return null;
76+
}
77+
TreeNode rst = stack.pop();
78+
while (!stack.isEmpty()) {
79+
rst = stack.pop();
80+
}
81+
return rst;
82+
}
83+
84+
public int getWeight(int base, String s) {
85+
if (s.equals("+") || s.equals("-")) {
86+
return base + 1;
87+
}
88+
if (s.equals("*") || s.equals("/")) {
89+
return base + 2;
90+
}
91+
return Integer.MAX_VALUE;
92+
}
8793

8894
/**
8995
* @param expression: A string array
9096
* @return: The Polish notation of this expression
9197
*/
9298
public ArrayList<String> convertToPN(String[] expression) {
93-
ArrayList<String> rst = new ArrayList<String>();
94-
if (expression == null || expression.length == 0) {
95-
return rst;
96-
}
97-
TreeNode root = build(expression);
98-
preTraversal(rst, root);
99-
100-
return rst;
99+
ArrayList<String> rst = new ArrayList<String>();
100+
if (expression == null || expression.length == 0) {
101+
return rst;
102+
}
103+
TreeNode root = build(expression);
104+
preTraversal(rst, root);
105+
106+
return rst;
101107
}
102108

103109
public void preTraversal(ArrayList<String> rst, TreeNode node){
104-
if (node == null) {
105-
return;
106-
}
107-
if (node.left == null && node.right == null) {
108-
rst.add(node.s);
109-
return;
110-
}
111-
rst.add(node.s);
112-
preTraversal(rst, node.left);
113-
preTraversal(rst, node.right);
110+
if (node == null) {
111+
return;
112+
}
113+
if (node.left == null && node.right == null) {
114+
rst.add(node.s);
115+
return;
116+
}
117+
rst.add(node.s);
118+
preTraversal(rst, node.left);
119+
preTraversal(rst, node.right);
114120
}
115121
}
116122

123+
117124
```

‎Java/Convert Expression to Reverse Polish Notation.java‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,11 @@
1-
用build expression tree开头。
1+
H
2+
3+
build expression tree。
4+
25
这个里面把TreeNode就当做成我们需要的node,里面扩展成有left/right child的node.
3-
这题，目的是建造tree,然后来个post-traversal就行了。
6+
7+
建造Expression Tree,然后根据　Reverse Polish Notation 的定义，来个post-traversal就行了。
8+
49
```
510
/*
611
Given an expression string array, return the Reverse Polish notation of this expression. (remove the parentheses)

‎Java/Course Schedule II.java‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,7 @@
1+
M
2+
13
详细的中文分析，看Course Schedule I
4+
25
```
36
/*
47
There are a total of n courses you have to take, labeled from 0 to n - 1.

‎Java/Course Schedule.java‎

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,5 @@
1+
M
2+
13
有点绕，但是做过一次就明白一点。
24
是topological sort的题目。一般都是给有dependency的东西排序。
35

@@ -26,7 +28,8 @@
2628
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2729
2830
2, [[1,0],[0,1]]
29-
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1.
31+
There are a total of 2 courses to take. To take course 1 you should have finished course 0,
32+
and to take course 0 you should also have finished course 1.
3033
So it is impossible.
3134
3235
Note:

‎Java/Expression Evaluation.java‎

Lines changed: 11 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,15 @@
1-
Build Expression Tree的另外一个变形。
2-
做的还是PostTraversal。先eval left, right, 然后eval符号。
1+
H
2+
3+
Build Expression Tree的另外一个变形，依然Min Tree.
4+
5+
build好Min Tree以后，做PostTraversal. Divde and Conquer：
6+
先recursively找到 left和right的大小， 然后evaluate中间的符号。
7+
8+
Note:
9+
1. Handle数字时，若left&&right Child全Null,那必定是我们weight最大的数字node了。
10+
2. 若有个child是null,那就return另外一个node。
11+
3. prevent Integer overflow　during operation:过程中用个Long，最后结局在cast back to int.
312

4-
注意Handle数字时，若左右Child全Null,那必定是我们weight最大的数字node了。
5-
若有个child是null,那就return另外一个node。
6-
还要注意：
7-
过程中用个Long吧，最后结局在cast back to int.
813
```
914
/*
1015
Given an expression string array, return the final result of this expression

‎Java/Expression Tree Build.java‎

Lines changed: 51 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,59 @@
11
H
22

33
和Max-tree一样，感谢http://blog.welkinlan.com/2015/06/29/max-tree-lintcode-java/
4-
这个题目是Min-tree， 头上最小，Logic 和max-tree如出一辙。
5-
注意虚拟的形态：treeNode,作用就是为了有个weight，好排序。
6-
要想想，Java这个strict mom，如果换做JavaScript, 直接在expressionTreeNode上面附加一个object就完了，哪还用什么另外一个TreeNode class.
7-
O(n)
4+
5+
这个题目是Min-tree， 头上最小，Logic 和max-tree如出一辙
6+
7+
注意treeNode,为了帮助ExpressionTreeNode 排序。它加了一个weight based on expression，协助build Min-Tree 排序。
8+
9+
Space: O(n)
10+
Time on average: O(n).
811

912
```
13+
/*
14+
15+
The structure of Expression Tree is a binary tree to evaluate certain expressions.
16+
All leaves of the Expression Tree have an number string value.
17+
All non-leaves of the Expression Tree have an operator string value.
18+
19+
Now, given an expression array, build the expression tree of this expression, return the root of this expression tree.
20+
21+
Example
22+
For the expression (2*6-(23+7)/(1+2)) (which can be represented by ["2" "*" "6" "-" "(" "23" "+" "7" ")" "/" "(" "1" "+" "2" ")"]).
23+
The expression tree will be like
24+
25+
[ - ]
26+
/ \
27+
[ * ] [ / ]
28+
/ \ / \
29+
[ 2 ] [ 6 ] [ + ] [ + ]
30+
/ \ / \
31+
[ 23 ][ 7 ] [ 1 ] [ 2 ] .
32+
After building the tree, you just need to return root node [-].
33+
34+
Clarification
35+
See wiki:
36+
Expression Tree
37+
38+
Tags Expand
39+
LintCode Copyright Stack Binary Tree
40+
41+
42+
*/
43+
44+
/**
45+
* Definition of ExpressionTreeNode:
46+
* public class ExpressionTreeNode {
47+
* public String symbol;
48+
* public ExpressionTreeNode left, right;
49+
* public ExpressionTreeNode(String symbol) {
50+
* this.symbol = symbol;
51+
* this.left = this.right = null;
52+
* }
53+
* }
54+
*/
55+
56+
1057
public class Solution {
1158
class TreeNode {
1259
int val;

0 commit comments

Comments
 (0)