duckling
BAN USERint ComputeWeight(Node* root,,Node*& minNode,int& minSofar)
{
if(root == NULL)return 0;
int curWeight = root->val + ComputeWeight(root->left,minNode,minSofar)\
+ComputeWeight(root->right,minNode,minSofar);
if(curWeight < minSofar)
{
minNode = root;
minSofar = curWeight;
}
}
Node* FindMinWeightNode(Node* root)
{
Node* minNode = NULL;
int minSofar = MAX_INT;
ComputeWeight(root,minNode,minSofar);
return minNode;
}
C++ implementation of sonesh' algorithm
int MoreThanHalfElem(int a[],int n)
{
int candidate;
int count =0;
for(int i= 0;i<n;i++)
{
if(count == 0)
{
candidate = i;
count =1;
}
else
{
if( a[i] == a[candidate])
count--;
else
count ++;
}
}
count =0;
for(int i=0;i<n;i++)
{
if(a[i] == a[candidate])
count++;
}
return count >=(n+1)/2?candidate:-1;
}
take {1 2 4 5 7 8} for example ,the xor result b is 5(0101),we find that miss1 and miss2 different at the first bit(also different at the third bit),we then use this one bit to divide the array to two parts, then we will get two sub-array {1 5 7},{2 4 8}(note that we don't really need to divide the elements into two parts,we just need to check their values at that bit ).
now this problem can be reduced to the problem of finding the only one missing number in array {1 5 7} that elements are either{1 3 5 7} and the only one missing number in array { 2 4 8} that elements are either {2 4 6 8}, i think you should know to how solve this simpler problem.
@ss .the elements are between 1 to N,and two of them are missing,so N = n+2,where n is the total number of elements now,we have to xor all the elements with number 1 to N ,so initially, we set b to (n+1)xor(n+2),and then xor with 1 to n and a[i ... n] .
i have changed 'n' to 'N' in my explanation,
The way of summing the numbers proposed by @debayan is great,but it is not the quickest way.There is a better approach using xor tricks.
1).xor all the elements with number 1-N, then the result be would be:
b = miss1 ^ miss2
2).as miss1 and miss2 are different numbers, they are at least different at 1 bit of their binary reprentations,take 2(0x0010) and 3(0x0011) for example,they are different at the first bit(count form right to left).So we can use one bit that miss1 and miss2 are different at to divide the array a into 2 parts,for array {1 2 4 5 7 8},b is 5, we use the first bit of b to divide array a,then we would get two subarray:{1 5 7},{2 4 8}
3)after step 1) and 2) ,this problem becomes similar to the problem of finding the only one missing number in array of elements 1-N
time complexity:O(n)
space complexity:O(1)
below are the C++ code
void Find2MissingNums(int a[],int n)
{
int b = ((n+1)^(n+2));
for(int i=0;i<n;i++)
b ^= (a[i] ^ (i+1) );
int mask = 0x01;
while(!(b & mask))
mask <<= 1;
int miss1 = 0;
int miss2 = 0;
for(int i = 0;i<n;i++)
{
if(a[i] & mask)miss1 ^= a[i];
else miss2 ^= a[i];
if((i+1) & mask)miss1 ^= (i+1);
else miss2 ^= (i+1);
}
if((n+1) & mask)miss1 ^= (n+1);
else miss2 ^= (n+1);
if((n+2) & mask)miss1 ^= (n+2);
else miss2 ^= (n+2);
cout<<miss1<<" "<<miss2<<endl;
}
test cases:
{1,2,4,5,6,8}; 7 3
{1,3,4,5,7,8}; 6 2
{1,2,3,4,5,6}; 7 8
{3,4}; 1 2
keep the maximum production and minimum production of the subarray that the last element is a[i-1],then the maximum production of the subarray that the last element is a[i] could be computed from:{pre_max*a[i], a[i] ,pre_min * a[i]}
here is the C++ code:
time complexity:O(n),space complexity:O(1)
int MaxProduct(int a[],int n)
{
int ans,preMax,preMin;
ans=preMax = preMin = a[0];
for(int i=1;i<n;i++)
{
int curMax = max(a[i],preMax*a[i]);
curMax = max(curMax,preMin*a[i]);
ans = max(ans,curMax);
preMin = min(a[i],preMin*a[i]);
preMin = min(preMin,preMax*a[i]);
preMax= curMax;
}
return ans;
}
test case:
{0, 0, -2, 0,0,0 } 0
{-2 ,1 ,1, 8 } 8
{-2, -3, 1, 3 } 18
{-3, -4, 0, 1,2,3 } 12
{1, -1, 10, -8,-9,0 } 720
BFS or DFS traversal would work,and we can use hash table to deal with cycles.
below is the DFS code:
//definition of the graph
struct Node
{
int data;
vector<Node*> neighbors;//
//constructor.....
};
Node* DFSCopyGraph(Node* graph,unordered_map<Node*,Node*>& hmap)
{
if(hmap.find(graph) != hmap.end())
return hmap[graph];
Node* graphCpy = new Node(graph->data);
hmap[graph] = graphCpy;
for(int i=0;i<graph->neighbors.size();i++)
graphCpy->neighbors.push_back(DFSCopyGraph(neighbors[i]),hmap);
return graphCpy;
}
1) count the total number of nodes in the BST,one pass traversal,time cost:O(n)
2) traverse inorder, the (n-k+1)-th smallest node is the answer,time cost:O(n)
below are the C++ code
int CountNode(Node* root)
{
if(root==NULL)return 0;
return 1+ CountNode(root->left) + CountNode(root->right);
}
Node * kth_smallest(Node *root, unsigned int k)
{
if(root == NULL)return NULL;
Node* ans = kth_smallest(root->left,k);
if(ans != NULL)return ans;
if(k==1)return root;
k--;
return kth_smallest(root->right,k):
}
Node * kth_largest(Node *root, unsigned int k)
{
int n = CountNode(root);
return kth_smallest(root,n-k+1);
}
int Roman2Int(string s)
{
if(s.length()==0)return 0;
unordered_map<char,int> table;
table['I'] = 1;
table['V'] = 5;
table['X'] = 10;
table['L'] = 50;
table['C'] = 100;
table['D'] = 500;
table['M'] = 1000;
int ans = table[s[s.length()-1]];
for(int i=s.length()-2;i>=0;i--)
{
if(table[s[i]] < table[s[i+1]])
ans -= table[s[i]];
else
ans += table[s[i]];
}
return ans;
}
dynamic programming approach
time complexity:O(len(a)*len(b))
int LCS(string& a,string& b)
{
int m = a.length();
int n = b.length():
vector<vector<int>>dp (m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(a[i-1] == b[j-1])
dp[i][j] = 1 + dp[i-1][j-1];
else
dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}
implement showell30's algorithm with c++
//a[i][j] =1 denotes person i know person j
int Celebrity(vector<vector<int> >& a)
{
int candidate=0;
int i=1;
while(i < a.size())
{
if(!a[i][candidate] || a[candidate][i])
candidate=i;
i++;
}
//check
for(int i=0;i<a.size();i++)
{
if(i!=candidate && (!a[i][candidate] || a[candidate][i]))
return -1;//no celebrity exist
}
return candidate;
}
traverse the price sequence ,maintain the minimum price so far,and update the max profit with a[i]-min
time complexity O(n)
int maxProfit(vector<int> &a)
{
if(a.size()==0)return 0;
int min=a[0];
int best=0;
for(int i=1;i<a.size();i++)
{
int tmp = a[i]-min;
best = max(best,tmp);
if(a[i]<min)min=a[i];
}
return best;
}
dynamic programming approach:
if matrix[i][j]=0,dp[i][j]==0
else,dp[i][j]=max(dp[i-1][j],dp[i][j-1])+1,
traverse the matrix,and the maximum value of dp[i][j] is the answer.
time complexity O(m*n),space O(max(m,n)) (optimized )
int MaxConnectedOnes(vector<vector<int> >& A)
{
int n=A.size();
if(n<=0)return 0;
int m=A[0].size();
vector<int> dp(m+1);
dp[0]=0;
int maxCount=0;
for(int i=0;i<n;i++)
{
for(int j=1;j<=m;j++)
{
if(A[i][j-1]==0)dp[j]=0;
else
{
dp[j]=max(dp[j],dp[j-1])+1;
maxCount=max(maxCount,dp[j]);
}
}
}
return maxCount;
}
solution 1
sort the two arrays A[],B[],compare every elements Ai,Bj.
i=j=0;
if Ai==Bj ,then add to the result
else if Ai<Bi ,then i++
else j++
vector<int> Intersection(vector<int>& A,vector<int>& B)
{
sort(A.begin(),A.end());
sort(B.begin(),B.end());
int lenA=A.size();
int lenB=B.size();
vector<int> ans;
int i=0;
int j=0;
while(i<lenA && j<lenB)
{
if(A[i]==B[j])ans.push_back(A[i]);
else if(A[i]>B[j])j++;
else i++;
}
return ans;
}
@Damn have you tested my code?for your test case,it will return index 0(number 5),it works.
- duckling March 29, 2013As for test case [2 2 3 3 5 5],my code will return -1,cause there are 6 elements,but no element is repeated more than 3 times.
so please read carefully before comment.