-
第 81 樓 / webdriver
- 時間: 2014-9-28 03:19算法問題推薦解法來了...
1. recursive solution. O(n) space. get inorder list first.
2. recursive solution. O(n) space. with only auxiliary two pointers.
3. Morris inorder traversal. O(1) space. with only auxiliary two pointers.
解法（Java）
代碼:
import java.util.ArrayList;
public class RecoverBinarySearchTree {
public void recoverTree(TreeNode root) {
if (root == null)
return;
ArrayList<TreeNode> nodes = new ArrayList<TreeNode>();
findWrongNode(root, nodes);
TreeNode a = null, b = null;
int i = 0;
for (i = 0; i < nodes.size() - 1; i++) {
if (nodes.get(i).val > nodes.get(i + 1).val) {
a = nodes.get(i);
break;
}
}
for (int j = i + 1; j < nodes.size() - 1; j++) {
if (nodes.get(j).val > nodes.get(j + 1).val) {
b = nodes.get(j + 1);
break;
}
}
if (b == null)
b = nodes.get(i + 1);
int t = a.val;
a.val = b.val;
b.val = t;
}
private void findWrongNode(TreeNode root, ArrayList<TreeNode> nodes) {
if (root == null)
return;
findWrongNode(root.left, nodes);
nodes.add(root);
findWrongNode(root.right, nodes);
}
} -
-
- 時間: 2014-9-28 03:22S算法問題: Regular Expression Matching
問題描述:
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") ? false
isMatch("aa","aa") ? true
isMatch("aaa","aa") ? false
isMatch("aa", "a*") ? true
isMatch("aa", ".*") ? true
isMatch("ab", ".*") ? true
isMatch("aab", "c*a*b") ? true -
-
- 時間: 2014-9-28 03:23算法問題推薦解法來了...
Both of the two solutions are from leetcode.com/2011/09/r...ching.html .
解法（Java）
代碼: public class RegularExpressionMatching {
public boolean isMatch(String s, String p) {
return isMatch(s, 0, p, 0);
}
private boolean isMatch(String s, int i, String p, int j) {
int ls = s.length();
int lp = p.length();
if (j == lp) {
return i == ls;
}
if ((j < lp - 1 && p.charAt(j + 1) != '*') || j == lp - 1) {
return (i < ls && s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') && isMatch(s, i + 1, p, j + 1);
}
while ((i < ls && s.charAt(i) == p.charAt(j)) || (p.charAt(j) == '.' && i < ls)) {
if (isMatch(s, i, p, j + 2))
return true;
i++;
}
return isMatch(s, i, p, j + 2);
}
}
-
- 時間: 2014-9-28 03:24
-
- 時間: 2014-9-28 03:25算法問題推薦解法來了...
...
解法（Java）
代碼: public class RemoveDuplicatesFromSortedArrayII {
public int removeDuplicates(int[] A) {
int length = A.length;
if (length < 3)
return length;
int slow = 0, fast = 1, idx = 0;
while (fast < length) {
while (fast < length && A[fast] == A[slow]) {
fast++;
}
if (fast - slow <= 2) {
while (slow < fast) {
A[idx++] = A[slow++];
}
} else {
A[idx++] = A[slow++];
A[idx++] = A[slow++];
slow = fast;
}
fast++;
}
while (slow < length) {
A[idx++] = A[slow++];
}
return idx;
}
} -
- 時間: 2014-9-28 03:27S算法問題: Remove Duplicates from Sorted Array
問題描述:
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2]. -
- 時間: 2014-9-28 03:28算法問題推薦解法來了...
Update 7/16/2013: Let j start from 0 for better understanding.
解法（Java）
代碼:
public class RemoveDuplicatesfromSortedArray {
public int removeDuplicates(int[] A) {
if (A.length == 0)
return 0;
else if (A.length == 1)
return 1;
else {
int ret = 1;
int p = 0;
for (int p1 = 1; p1 < A.length; p1++) {
if (A[p1 - 1] != A[p1]) {
ret++;
A[++p] = A[p1];
}
}
return ret;
}
}
} -
- 時間: 2014-9-28 03:30
-
- 時間: 2014-9-28 03:31算法問題推薦解法來了...
1. iterative 2. recursive
解法（Java）
代碼:
public class RemoveDuplicatesfromSortedListII {
public ListNode deleteDuplicates(ListNode head) {
if (head == null)
return head;
ListNode start = new ListNode(0);
start.next = head;
ListNode slow = start;
ListNode fast = head;
while (fast.next != null) {
if (slow.next.val != fast.next.val) {
if (slow.next.next == fast.next) {
slow = slow.next;
} else {
slow.next = fast.next;
}
}
fast = fast.next;
}
if (slow.next.next != fast.next) {
slow.next = fast.next;
}
return start.next;
}
} -
- 時間: 2014-9-28 03:34
Leetcode Hacking Practice -- Solution in Java Part 2
