Skip to content

Commit 72fc4b4

Browse files
awangdevawangdev
committed
day7
1 parent c5ebbaf commit 72fc4b4

17 files changed

Lines changed: 1150 additions & 221 deletions

‎Java/Add and Search Word.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -10,7 +10,8 @@ void addWord(word)
1010
1111
bool search(word)
1212
13-
search(word) can search a literal word or a regular expression string containing only letters a-z or .. A . means it can represent any one letter.
13+
search(word) can search a literal word or a regular expression string containing only letters a-z or ..
14+
A . means it can represent any one letter.
1415
1516
Example
1617
addWord("bad")

‎Java/Binary Search Tree Iterator.java‎

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
理解binary search tree inorder traversal的规律。
2+
都是先找left.left.left ....left. 为top。
3+
然后再找parent,然后再right.
4+
5+
这个题目里面找到rst之后，首先考虑这个rst.right
6+
其实rst在这里虽然是most left node, 但对于rst.right来说，其实它也是parent.
7+
所以每次把left全部弄一边的时候，parent node其实也都是顾及到了的。
8+
```
9+
/*
10+
Design an iterator over a binary search tree with the following rules:
11+
12+
Elements are visited in ascending order (i.e. an in-order traversal)
13+
next() and hasNext() queries run in O(1) time in average.
14+
Have you met this question in a real interview? Yes
15+
Example
16+
For the following binary search tree, in-order traversal by using iterator is [1, 6, 10, 11, 12]
17+
18+
10
19+
/ \
20+
1 11
21+
\ \
22+
6 12
23+
Challenge
24+
Extra memory usage O(h), h is the height of the tree.
25+
26+
Super Star: Extra memory usage O(1)
27+
28+
Tags Expand
29+
Binary Tree LintCode Copyright Non Recursion Binary Search Tree Google LinkedIn Facebook
30+
*/
31+
32+
/*
33+
Thoughts://http://blog.csdn.net/u014748614/article/details/46800891
34+
Put all left nodes into stack. Then top of stack must be the first element in in-order-traversal.
35+
We never add right node into stack directly, but ever time before returnning the rst node, we take care of rst.right right away.
36+
That is, find next() when rst.right as root.
37+
very smart use of a 'currnt' node.
38+
It's like a pointer on the tree, but only operates when that current node is not null, and under condition of having left child.
39+
*/
40+
41+
/**
42+
* Definition of TreeNode:
43+
* public class TreeNode {
44+
* public int val;
45+
* public TreeNode left, right;
46+
* public TreeNode(int val) {
47+
* this.val = val;
48+
* this.left = this.right = null;
49+
* }
50+
* }
51+
* Example of iterate a tree:
52+
* BSTIterator iterator = new BSTIterator(root);
53+
* while (iterator.hasNext()) {
54+
* TreeNode node = iterator.next();
55+
* do something for node
56+
* }
57+
*/
58+
public class BSTIterator {
59+
public Stack<TreeNode> stack = new Stack<TreeNode>();
60+
public TreeNode current;
61+
//@param root: The root of binary tree.
62+
public BSTIterator(TreeNode root) {
63+
current = root;
64+
}
65+
66+
//@return: True if there has next node, or false
67+
public boolean hasNext() {
68+
return current != null || !stack.isEmpty();
69+
}
70+
71+
//@return: return next node
72+
public TreeNode next() {
73+
while (current != null) {
74+
stack.push(current);
75+
current = current.left;
76+
}
77+
TreeNode rst = stack.pop();
78+
current = rst.right;
79+
return rst;
80+
}
81+
}
82+
83+
84+
85+
86+
87+
88+
89+
90+
91+
92+
```

‎Java/Generate Parentheses.java‎

Lines changed: 134 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,134 @@
1+
递归。
2+
看thought.取或者不取(, )
3+
```
4+
/*
5+
Generate Parentheses
6+
7+
Given n pairs of parentheses,
8+
write a function to generate all combinations of well-formed parentheses.
9+
10+
Example
11+
Given n = 3, a solution set is:
12+
13+
"((()))", "(()())", "(())()", "()(())", "()()()"
14+
15+
Tags Expand
16+
String Backtracking Recursion Zenefits Google
17+
18+
*/
19+
20+
/*
21+
Thoughts:
22+
//http://fisherlei.blogspot.com/2012/12/leetcode-generate-parentheses.html
23+
Either put ( or )
24+
can only put ( when # of ( < n
25+
can only put ) when # of ) < # of (
26+
If # of single '(' > 0, then we can put ')'
27+
If n > 0, we can split: 1. close it with ')'; or 2. add '('
28+
when n-- becomese = 0 and #p = 0, rst.add
29+
30+
*/
31+
public class Solution {
32+
/**
33+
* @param n n pairs
34+
* @return All combinations of well-formed parentheses
35+
*/
36+
ArrayList<String> rst = new ArrayList<String>();
37+
public ArrayList<String> generateParenthesis(int n) {
38+
if (n <= 0) {
39+
return rst;
40+
}
41+
ArrayList<String> list = new ArrayList<String>();
42+
helper(list, 0, 0, n);
43+
return rst;
44+
}
45+
46+
public void helper(ArrayList<String> list, int left, int right, int n) {
47+
if (left == n && right == n) {
48+
StringBuffer sb = new StringBuffer();
49+
for (String s : list) {
50+
sb.append(s);
51+
}
52+
rst.add(sb.toString());
53+
return;
54+
}
55+
if (left < n) {
56+
list.add("(");
57+
helper(list, left + 1, right, n);
58+
list.remove(list.size() - 1);
59+
}
60+
if (right < left) {
61+
list.add(")");
62+
helper(list, left, right + 1, n);
63+
list.remove(list.size() - 1);
64+
}
65+
}
66+
}
67+
68+
69+
/*
70+
//
71+
1st attempt, timeout.
72+
Thoughts:
73+
n = 0, null
74+
n = 1, trivial: ()
75+
Do i-- from n. For each i >= 2
76+
it can choose: close a paren
77+
open another paren
78+
front = (
79+
end = )
80+
helper(front, end, int n)
81+
if (n == 1) {
82+
front + "()" + end
83+
rst.add // check duplicate
84+
}
85+
86+
*/
87+
public class Solution {
88+
/**
89+
* @param n n pairs
90+
* @return All combinations of well-formed parentheses
91+
*/
92+
public ArrayList<String> rst = new ArrayList<String>();
93+
public ArrayList<String> generateParenthesis(int n) {
94+
if (n <= 0) {
95+
return rst;
96+
} else if (n == 1){
97+
rst.add("()");
98+
return rst;
99+
}
100+
helper("", "", n);
101+
Collections.sort(rst);
102+
return rst;
103+
}
104+
//3
105+
public void helper(String front, String end, int n) {
106+
if (n == 1) {
107+
String rt = front + "()" + end;
108+
if (!rst.contains(rt)){
109+
rst.add(rt);
110+
}
111+
return;
112+
}
113+
n--;
114+
115+
helper(front + "(", ")" + end, n);
116+
helper(front + "()", end, n);
117+
helper(front, "()" + end, n);
118+
helper(front + end + "(", ")", n);
119+
helper(front + end, "()", n);
120+
helper(front + end + "()", "", n);
121+
helper("(", ")" + front + end, n);
122+
helper("()", front + end, n);
123+
helper("","()" + front + end, n);
124+
helper("(",front+end+")",n);
125+
helper("(" + front+end,")",n);
126+
helper("(" + front, end + ")",n);
127+
helper("("+front+end+")", "", n);
128+
helper("", "("+front+end+")", n);
129+
130+
}
131+
132+
}
133+
134+
```

0 commit comments

Comments
 (0)