china.taoqin
BAN USEROptimization:
1. combine consecutive '?' and '*' in the very beginning;
2. flag the result of match(x,y) to reduce the redundant calculating in recursive process.
Java Code :
public class SimpleMatcher{
public String regex;
public String content;
public static boolean match(int regexPos, int contentPos) {
if (regexPos = regex.length() && contentPos == content.length()) {
return true;
} else if (regexPos < regex.length() && contentPos < content.length()) {
char regexChar = regex.charAt(regexPos);
if (regexChar == '?') {
return match(regexPos + 1, contentPos + 1);
} else if (regexChar == '*') {
for (int i = 0; i <= content.length() - contentPos; i++) {
if (match(regexPos + 1, contentPos + i)) {
return true;
}
}
return false;
} else if (regexChar == content.charAt(contentPos)) {
return match(regexPos + 1, contentPos + 1));
}
}
return false;
}
public static void main(String[] args) {
SimpleMatcher matcher = new SimpleMatcher();
matcher.regex = "";
matcher.content = "";
matcher.match(0, 0);
}
}
Using the array2, construct BST O(nlogn + nlogn).
Sorry:)
1. Sort the node by the first value and keep it in array 1, coz the mid-order reversal of a binary search tree is a fully sorted array.
2. Sort the node by the second value and keep it in array 2.
So the process becomes to keep finding the node in array 1 which has the smallest value in array 2, the left-side of that node in array 1 is its left subtree and the right-side is the right subtree.
Recursive alogrithm in array 1 would be more complex in time because for each part it is necessary to find the node which has the smallest second value in the sub-part.
But if you recursively construct the tree via array 2 and take a note of parrent node, the time complexity should be O(nlogn + n) = O(nlogn) totally.
Resursive solution
int CheckSumOfNoSiblings(Node node) {
if (node->left == null && node->right != null)
return CheckSumOfNoSiblings(node->right) + 1;
if (node->right == null && node->left != null)
return CheckSumOfNoSiblings(node->left) + 1;
if (node->left != null && node->right != null)
return CheckSumOfNoSiblings(node->left) + CheckSumOfNoSiblings(node->right);
return 0;
}
Dont need to seperate it into two scenarios. Consider a-b = abs(k),and create two pointers from both sides of sorted array, moving towards each other. If k is negative, just switch the value of a,b.
- china.taoqin June 14, 2011