Kaidul Islam
BAN USERThe wildcard positions have to be filled with all possible combination of 0 and 1. This can be done by backtracking but the best way is to check all numbers from 0 to 2^(total wildcard) - 1 and set 0 or 1 by checking its bit pattern.
Complexity is O(2^n) in worst case.
vector<string> wildcardFillUp(string bitStream) {
vector<string> result;
vector<int> positions;
int cnt = 0;
int len = bitStream.length();
for(int i = 0; i < len; ++i) {
if(bitStream[i] == '?') {
positions.push_back(i);
++cnt;
}
}
int n = (1 << cnt) - 1;
for(int i = 0; i <= n; ++i) {
for(int idx = 0, k = cnt - 1; k >= 0; --k) {
bool isSet = (bool) (i & (1 << k));
bitStream[positions[idx++]] = isSet ? '1' : '0';
}
result.push_back(bitStream);
}
return result;
}
Hi Felipe,
Thanks for your trial. your inserted tree is not a BST. if 10 is a root, 9 can't be its right child. Right child has to be greater than root.
simple and nice solution!
- Kaidul Islam May 05, 2015Use Morris Traversal. The idea is -
1. Initialize root as current
2. while current is not NULL
a) if current has no left child
- print current and set current = current.right
b) else
- set current as rightmost node of left child
Source Code:
void inorderWithConstantSpace(TreeNode *root) {
if(!root) return root;
TreeNode *current = root;
while(current) {
if(current->left) {
TreeNode *leftChild = current->left;
TreeNode *tmp = leftChild;
TreeNode *rightMost;
while(leftChild) {
rightMost = leftChild;
leftChild = leftChild->right;
}
rightMost->right = current;
current->left = nullptr;
current = tmp;
} else {
printf("%d ", current->value);
current = current->right;
}
}
}
double findKth(int A[], int m, int B[], int n, int k) {
if (m > n) return findKth(B, n, A, m, k);
if (m == 0) return B[k - 1];
if (k == 1) return min(A[0], B[0]);
int aMid = min(k / 2, m);
int bMid = k - aMid;
if (A[aMid - 1] <= B[bMid - 1]) {
return findKth(A + aMid, m - aMid, B, n, k - aMid);
}
return findKth(A, m, B + bMid, n - bMid, k - bMid);
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
int total = m + n;
if(total & 1) return findKth(A, m, B, n, total / 2 + 1);
return (findKth(A, m, B, n, total / 2);
}
The overall time complexity is
O(log(n + n))
which is
O(logn)
.
- Kaidul Islam October 14, 2014string encodedString(string input) {
int n = input.length();
if(n < 2) return input;
char prev = input[0];
int count = 1;
string result = "";
for(int i = 1; i < n; ++i) {
if(input[i] == prev) {
++count;
} else {
result = result + prev;
if(count > 1) result = result + (char)(count + 48);
prev = input[i];
count = 1;
}
}
result = result + prev;
if(count > 1) result = result + (char)(count + 48);
return result;
}
bool isPlaindrome(string str) {
int n = str.length();
for(int i = 0, j = n - 1; i < j; ++i, --j) {
if(str[i] != str[j]) return false;
}
return true;
}
- Kaidul Islam October 07, 2017