Jason Ding
BAN USERIterative solution:
double pow(double x, int n) {
if(x==0) return 0;
if(n==0) return 1;
long long exp = abs(double(n));
double r=1;
while(exp){
if(exp&1)
r*=x;
exp>>=1;
x*=x;
}
if(n<0) return 1.0/r;
return r;
}
recursive solution:
double pow(double x, int n) {
if(x==0) return 0;
if(n==0) return 1;
double r = pow(x, n/2);
r*=r;
if(n%2==1)
r*=x;
if(n%2==-1)
r/=x;
return r;
}
void generator(vector<string> &ret, string s, size_t cur){
if(cur==s.size()){
ret.push_back(s);
return;
}
if(s[cur]=='?'){
s[cur]='0';
generator(ret, s, cur+1);
s[cur]='1';
generator(ret, s, cur+1);
}
else
generator(ret, s, cur+1);
}
void wrapperFillQuestionMark(){
vector<string> ret;
generator(ret, "a?b?c?", 0);
for(auto it = ret.begin(); it!=ret.end(); ++it)
cout << *it << endl;
}
@varun merge can be done in place, so this is a O(1) space solution if we do not consider function call stack.
- Jason Ding June 04, 2014Here is a O(log n) time solution.
void printSuccessor(TreeNode* root, int target){
if(!root) return;
TreeNode* cur = root;
int successor = target-1;
//find node with value = target
while(cur){
if(cur->val=target)
break;
//as you go down, store the value which is >target
if(cur->val<target)
cur=cur->right;
else{
successor = cur->val;
cur=cur->left;
}
}
if(cur && cur->right){ //find node with value = target and this node has right child
cur = cur->right;
if(cur->left)
cur=cur->left;
successor = cur->val;
}
if(successor>=target)
cout << successor << endl;
}
void helper(const vector<vector<int>> &matrix, int x, int y){
int m = matrix.size();
while(x>=0 && y<m){
cout << matrix[x][y] << “\t”;
--x;
++y;
}
cout << endl;
}
void printDiagonally(vector<vector<int>> matrix){
if(matrix.empty() || matrix[0].empty())
return;
int m = matrix.size(), n = matrix[0].size();
for(int i=0; i<n; ++i)
helper(matrix, 0, i);
for(int i=1; i<m; ++i)
helper(matrix, i, n-1);
}
This can be done in O(nlogn) using divide and conquer
The basic idea of the algorithm is as follows:
1. We recursively solve two smaller arrays of size n/2 to get F and B
2. Compute f= a[0]*a[1]*…*a[n/2-1]; b = a[n/2]*a[n/2+1]*…*a[n-1]
3. Multiply each element in F by b, and multiply each element in B by f.
Time complexity analysis:
T(n) = 2T(n/2) + O(n) = O(nlogn)
This can be done in O(nlogn) using divide and conquer scheme. Before starting the algorithm, please see the following observation:
Observation: given an array A, say [1, -2, ..., 4], with n elements, we can get the inverse of A, denoted as A’ (4, …, -2, 1), in \theta(n) time with O(1) space complexity.
The basic idea of the algorithm is as follows:
1. We recursively ‘sort’ two smaller arrays of size n/2 (here ‘sort’ is defined in the question)
2. Then we spend \theta(n) time merging the two sorted smaller arrays with O(1) space complexity.
How to merge?
Suppose the two sorted smaller array is A and B. A1 denotes the negative part of A, and A2 denotes positive part of A. Similarly, B1 denotes the negative part of B, and B2 denotes positive part of B.
2.1. Compute the inverse of A2 (i.e., A2’) in \theta(|A2|) time; compute the inverse of B1 (i.e., B1’) in \theta(|B1|) time. [See observation; the total time is \theta(n) and space is O(1)]
Thus the array AB (i.e., A1A2B1B2) becomes A1A2’B1’B2.
2.2. Compute the inverse of A2’B1’ (i.e., B1A2) in \theta(|A2|) time. [See observation; the total time is \theta(n) and space is O(1)]
Thus the array A1A2’B1’B2 becomes A1B1A2B2. We are done.
Time complexity analysis:
T(n) = 2T(n/2) + \theta(n) = O(nlogn)
DP problem:
DP[i,j] means the number of ways arrarging j rocks such that the base layer has i rocks.
DP[i,j] = 0 if i>j;
= 1 if i=j;
= sum_{1<=p<i }(DP[p,j-i])
- Jason Ding June 15, 2014