发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/21/2013-09-21-CODE 46 Scramble String/

访问原文「CODE 46. Scramble String」

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":
great
/ \
gr eat
/ \ / \
g r e at
/ \
a t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and
swap its two children, it produces a scrambled string "rgeat".
rgeat
/ \
rg eat
/ \ / \
r g e at
/ \
a t

We say that "rgeat" is
a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at",
it produces a scrambled string "rgtae".
rgtae
/ \
rg tae
/ \ / \
r g ta e
/ \
t a

We say that "rgtae" is
a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public boolean isScramble(String s1, String s2) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == s1 && null == s2) {
		return true;
	} else if ((null == s1 && null != s2) || (null != s1 && null == s2)) {
		return false;
	} else if (s1.length() != s2.length()) {
		return false;
	} else if (s1.equals(s2)) {
		return true;
	}
	char[] c1 = s1.toCharArray();
	char[] c2 = s2.toCharArray();
	int length = s1.length();
	boolean[][][] is = new boolean[length][length][length];
	for (int i = 0; i < s1.length(); i++) {
		for (int j = 0; j < s2.length(); j++) {
			is[0][i][j] = (c1[i] == c2[j]);
		}
	}
	for (int k = 1; k < length; k++) {
		for (int m = length - k - 1; m >= 0; m--) {
			for (int n = length - k - 1; n >= 0; n--) {
				boolean r = false;
				for (int j = 1; j <= k && !r; j++) {
					if ((is[j - 1][m][n] && is[k - j][j + m][j + n])
							|| (is[j - 1][m][n + k + 1 - j] && is[k - j][m
									+ j][n])) {
						r = true;
					}
				}
				is[k][m][n] = r;
			}
		}
	}
	return is[length - 1][0][0];
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/21/2013-09-21-CODE 37 Unique Binary Search Trees II/

访问原文「CODE 37. Unique Binary Search Trees II」

Given n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
For example,
Given n = 3, your program should return all 5 unique BST’s shown below.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public ArrayList<TreeNode> generateTrees(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (n <= 0) {
		ArrayList<TreeNode> node = new ArrayList<TreeNode>();
		node.add(null);
		return node;
	}
	return dfs(1, n);
}
ArrayList<TreeNode> dfs(int start, int end) {
	if (end - start < 0) {
		return null;
	} else if (end - start == 0) {
		ArrayList<TreeNode> node = new ArrayList<TreeNode>();
		node.add(new TreeNode(start));
		return node;
	}
	ArrayList<TreeNode> node = new ArrayList<TreeNode>();
	for (int i = start; i <= end; i++) {
		ArrayList<TreeNode> leftNodes = dfs(start, i - 1);
		ArrayList<TreeNode> rightNodes = dfs(i + 1, end);
		if (null != leftNodes || null != rightNodes) {
			if (null == leftNodes) {
				for (TreeNode rightNode : rightNodes) {
					TreeNode newNode = new TreeNode(i);
					newNode.right = rightNode;
					node.add(newNode);
				}
			} else if (null == rightNodes) {
				for (TreeNode leftNode : leftNodes) {
					TreeNode newNode = new TreeNode(i);
					newNode.left = leftNode;
					node.add(newNode);
				}
			} else {
				for (TreeNode leftNode : leftNodes) {
					for (TreeNode rightNode : rightNodes) {
						TreeNode newNode = new TreeNode(i);
						newNode.left = leftNode;
						newNode.right = rightNode;
						node.add(newNode);
					}
				}
			}
		} else {
			TreeNode newNode = new TreeNode(i);
			node.add(newNode);
		}
	}
	return node;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/21/2013-09-21-CODE 38 Unique Binary Search Trees/

访问原文「CODE 38. Unique Binary Search Trees」

Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
For example,
Given n = 3, there are a total of 5 unique BST’s.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int numTrees(int n) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (n <= 0) {
		return 0;
	}
	return dfs(1, n);
}
int dfs(int start, int end) {
	if (end - start <= 0) {
		return 1;
	} else if (end - start == 1) {
		return 2;
	} else if (end - start == 2) {
		return 5;
	}
	int sum = 0;
	for (int i = start; i <= end; i++) {
		sum += dfs(start, i - 1) * dfs(i + 1, end);
	}
	return sum;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 36 Interleaving String/

访问原文「CODE 36. Interleaving String」

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = "aabcc",
s2 = "dbbca",
When s3 = "aadbbcbcac", return true.
When s3 = "aadbbbaccc", return false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public boolean isInterleave(String s1, String s2, String s3) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == s1 && null == s2 && null == s3) {
		return true;
	} else if (null == s1 && null == s2 && null != s3) {
		return false;
	} else if (null == s1) {
		if (s2.equals(s3)) {
			return true;
		} else {
			return false;
		}
	} else if (null == s2) {
		if (s1.equals(s3)) {
			return true;
		} else {
			return false;
		}
	} else if (null != s1 && null != s2 && null != s3) {
		if (s3.length() != s1.length() + s2.length()) {
			return false;
		}
	}
	boolean[][] is = new boolean[s1.length() + 1][s2.length() + 1];
	is[0][0] = true;
	for (int i = 1; i < s1.length() + 1; i++) {
		if (s1.charAt(i - 1) == s3.charAt(i - 1)) {
			is[i][0] = true && is[i - 1][0];
		}
	}
	for (int i = 1; i < s2.length() + 1; i++) {
		if (s2.charAt(i - 1) == s3.charAt(i - 1)) {
			is[0][i] = true & is[0][i - 1];
		}
	}
	for (int i = 1; i < s1.length() + 1; i++) {
		for (int j = 1; j < s2.length() + 1; j++) {
			boolean b1 = false;
			boolean b2 = false;
			if (s3.charAt(i + j - 1) == s1.charAt(i - 1)) {
				b1 = is[i - 1][j];
			}
			if (s3.charAt(i + j - 1) == s2.charAt(j - 1)) {
				b2 = is[i][j - 1];
			}
			is[i][j] = b1 || b2;
		}
	}
	return is[s1.length()][s2.length()];
	// return dfs(s1, s2, s3, 0, 0, 0);
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 35 Validate Binary Search Tree/

访问原文「CODE 35. Validate Binary Search Tree」

Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:

  • The left subtree of a node contains only nodes with keys less than the node’s key.
  • The right subtree of a node contains only nodes with keys greater than the node’s key.
  • Both the left and right subtrees must also be binary search trees.

confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean isValidBST(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return true;
	}
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode pre = new TreeNode(Integer.MIN_VALUE);
	TreeNode now = root;
	while (!stack.isEmpty() || null != now) {
		if (null == now) {
			now = stack.pop();
			if (pre.val >= now.val) {
				return false;
			}
			pre = now;
			now = now.right;
		} else {
			stack.push(now);
			now = now.left;
		}
	}
	return true;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 26 Binary Tree Level Order Traversal II/

访问原文「CODE 26. Binary Tree Level Order Traversal II」

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).
For example:
Given binary tree {3,9,20,#,#,15,7},

  3
 / \
9  20
  /  \
 15   7

return its bottom-up level order traversal as:

[
  [15,7]
  [9,20],
  [3],
]

confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public ArrayList<ArrayList<Integer>> levelOrderBottom(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return new ArrayList<ArrayList<Integer>>();
	}
	ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	ArrayList<Integer> layerVals = new ArrayList<Integer>();
	queue.offer(root);
	int layerNumber = 1;
	while (!queue.isEmpty()) {
		TreeNode node = queue.poll();
		layerVals.add(node.val);
		layerNumber--;
		if (null != node.left) {
			queue.offer(node.left);
		}
		if (null != node.right) {
			queue.offer(node.right);
		}
		if (layerNumber == 0) {
			layerNumber = queue.size();
			ArrayList<Integer> layerValsCpy = new ArrayList<Integer>();
			layerValsCpy.addAll(layerVals);
			results.add(0, layerValsCpy);
			layerVals.clear();
		}
	}
	return results;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 34 Recover Binary Search Tree/

访问原文「CODE 34. Recover Binary Search Tree」

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure.
Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?
confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public void recoverTree(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	ArrayList<TreeNode> list = inorder(root);
	TreeNode err1 = null;
	TreeNode err2 = null;
	for (int i = 0; i < list.size() - 1; i++) {
		if (list.get(i).val > list.get(i + 1).val) {
			if (null == err1) {
				err1 = list.get(i);
			} else {
				err2 = list.get(i + 1);
				break;
			}
		}
	}
	if (null != err1 && null != err2) {
		int tmp = err1.val;
		err1.val = err2.val;
		err2.val = tmp;
	} else if (null != err1) {
		int index = list.indexOf(err1);
		int tmp = list.get(index + 1).val;
		list.get(index + 1).val = err1.val;
		err1.val = tmp;
	}
}
ArrayList<TreeNode> inorder(TreeNode node) {
	if (null == node.left && null == node.right) {
		ArrayList<TreeNode> list = new ArrayList<TreeNode>();
		list.add(node);
		return list;
	}
	ArrayList<TreeNode> list = null;
	if (null != node.left) {
		list = inorder(node.left);
	}
	if (null == list) {
		list = new ArrayList<TreeNode>();
	}
	list.add(node);
	if (null != node.right) {
		ArrayList<TreeNode> listRight = inorder(node.right);
		list.addAll(listRight);
	}
	return list;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 33 Same Tree/

访问原文「CODE 33. Same Tree」

Given two binary trees, write a function to check if they are equal or not.
Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean isSameTree(TreeNode p, TreeNode q) {
	// Start typing your Java solution below
	// DO NOT write main() function
	return dfs(p, q);
}
boolean dfs(TreeNode left, TreeNode right) {
	if ((null != left && null == right) || (null == left)
			&& (null != right)) {
		return false;
	} else if (left == null && right == null) {
		return true;
	} else if (left.val != right.val) {
		return false;
	}
	boolean leftResult = dfs(left.left, right.left);
	boolean rightResult = dfs(left.right, right.right);
	return (leftResult && rightResult) ? true : false;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 32 Symmetric Tree/

访问原文「CODE 32. Symmetric Tree」

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree is symmetric:
1
/ \
2 2
/ \ / \
3 4 4 3

But the following is not:

  1
 / \
2   2
 \   \
 3    3

Note:
Bonus points if you could solve it both recursively and iteratively.
confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean isSymmetric(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return true;
	}
	return dfs(root.left, root.right);
}
boolean dfs(TreeNode left, TreeNode right) {
	if ((null != left && null == right) || (null == left)
			&& (null != right)) {
		return false;
	} else if (left == null && right == null) {
		return true;
	} else if (left.val != right.val) {
		return false;
	}
	boolean leftResult = dfs(left.left, right.right);
	boolean rightResult = dfs(left.right, right.left);
	return (leftResult && rightResult) ? true : false;
}

发表于   |   分类于 ，   |   ❤

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2013/09/20/2013-09-20-CODE 31 Binary Tree Level Order Traversal/

访问原文「CODE 31. Binary Tree Level Order Traversal」

Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},

  3
 / \
9  20
  /  \
 15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

confused what "{1,#,2,3}" means? >
read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.
Here’s an example:

  1
 / \
2   3
   /
  4
   \
    5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
	// Start typing your Java solution below
	// DO NOT write main() function
	if (null == root) {
		return new ArrayList<ArrayList<Integer>>();
	}
	ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
	Queue<TreeNode> queue = new LinkedList<TreeNode>();
	ArrayList<Integer> layerVals = new ArrayList<Integer>();
	queue.offer(root);
	int layerNumber = 1;
	while (!queue.isEmpty()) {
		TreeNode node = queue.poll();
		layerVals.add(node.val);
		layerNumber--;
		if (null != node.left) {
			queue.offer(node.left);
		}
		if (null != node.right) {
			queue.offer(node.right);
		}
		if (layerNumber == 0) {
			layerNumber = queue.size();
			ArrayList<Integer> layerValsCpy = new ArrayList<Integer>();
			layerValsCpy.addAll(layerVals);
			results.add(layerValsCpy);
			layerVals.clear();
		}
	}
	return results;
}