Class Static Functions

Class static functions CANNOT call non-static member variables, neither can it call non-static class functions.

Generate Possible Sub-strings

Problem:

Generate all the possible substrings using the characters of a given string. Write code. (The order of chars do not matter, i.e., ac <=> ca) 
i/p: abc 
o/p: { a,b,c,ab,ac,bc,abc} 


Solution (backtracking):
https://gist.github.com/leehomyc/5335144

rebuild BST

Node* RebuildBST(vector<int> output)
{
int n=output.size();
if(n==0)
return NULL;
stack<Node*> myStack;
int i=0;
Node* root;
while(i<n)
{
int curVal=output[i];
Node* preNode=NULL,*prePreNode=NULL;
while(!myStack.empty())
{
preNode=myStack.top();
if(preNode->val>curVal)
break;
prePreNode=myStack.top();
myStack.pop();
}
Node* curNode=new Node;
curNode->val=output[i];
curNode->L=NULL;
curNode->R=NULL;
if(!preNode)
{
root=curNode;
}
else if(!prePreNode)
{
preNode->L=curNode;
}
else
{
prePreNode->R=curNode;
}
myStack.push(curNode);
i++;
}
return root;
}

find the kth largest node of a BSTBST

void kth_largest(Node* root,unsigned int k)
{
if(!root)return;
stack<Node*> myStack;
Node* curNode=root;
int i=0;
while(curNode || !myStack.empty())
{
if(curNode)
{
myStack.push(curNode);
curNode=curNode->L;
}
else
{
Node* topNode=myStack.top();
curNode=topNode->R;
myStack.pop();
i++;
if(i==k)
cout<<topNode->val<<endl;
}
}
}

Be careful with iterators!

OK, I am writing this to give you a strong warning!

STL has much more than you can imagine:

Remember this,

1. vector, deque, they are contiguous

2. list, set they are not.

So the difference is that

1. you can do arithmetic operations with vector deque iterators.

like:  vector<int>::iterator iter; iter=iter+3;

but you cant do this: set<int>::iterator iter; iter=iter-1;

but for both iterators you can do: iter++, iter--; so equivalently you can do copy(set.begin(),set.end(),
ostream_iterator<int>(cout," ")) all this stuff...

2. when you destroy an iterator, something unpredictable will happen...ok predictable.

if it is in category one, all iterators will be destroyed. so like:

deque<int>::iterator iter=myQueue.begin();
myQueue.erase(iter+3);

then iter will also be lost!

However, if it is in category two, you can safely delete one iterator without sabotaging others.

list<int>::iterator iter=myList.begin(), iter2=iter;
iter2++;
myList.erase(iter);
iter=iter2;

...and this is fine.

Find the next node given parent node in BST

#include"tree_test.h"
#include<iostream>

using namespace std;

Node* InorderSuccessor(Node* node)
{
if(node->R)
{
Node* pre=node;
node=node->R;
while(node)
{
pre=node;
node=node->L;
}
return pre;
}
else if(node->parent)
{
Node* pre=node;
node=node->parent;
while(node && node->R==pre)
{
pre=node;
node=node->parent;
}
return node;
}
else
return NULL;
}

template specialization

template<>
inline cv::Point2f CPanoramicCore<cv::Point2f>::Interpolate(double x,double y,int& flag)
{

}

template<>
void spec1<char, int>()
{

}

cannot be partially specialized!

but can use following:

 template <typename T1>

class class1<T1, int>
{

};

sky line problem

struct BDL
{
int x1;
int y;
int x2;
BDL(int x1_,int y_,int x2_){x1=x1_;y=y_;x2=x2_;}
};
struct INTVL
{
int x;
int h;
};

struct ltstr2
{
bool operator()(INTVL l,INTVL r)const
{
return l.x<r.x;
}
};

void SkyLine(vector<BDL> buildings)
{
set<INTVL,ltstr2> bdls;
INTVL intvl;
intvl.x=-INT_MAX;
intvl.h=0;
bdls.insert(intvl);
for(int i=0;i<buildings.size();i++)
{
BDL bdl=buildings[i];
int x1=bdl.x1,x2=bdl.x2,h1=bdl.y;
INTVL int1,int2;
int1.x=x1;
int2.x=x2;
set<INTVL,ltstr2>::iterator iter1=bdls.upper_bound(int1);
iter1--;
set<INTVL,ltstr2>::iterator iter2=bdls.lower_bound(int2);
set<INTVL,ltstr2> bdls2=bdls;
for(set<INTVL,ltstr2>::iterator iter=iter1;iter!=iter2;iter++)
{
x1=bdl.x1;x2=bdl.x2;h1=bdl.y;
set<INTVL,ltstr2>::iterator iter3=iter;
iter3++;
int x3,x4;
INTVL intvl=*iter;
x3=intvl.x,x4;
if(iter3==bdls.end())x4=INT_MAX;
else x4=(*iter3).x;
int h2=(*iter).h;
if(x1<x3)x1=x3;
if(x2>x4)x2=x4;
if(h2<h1)
{
INTVL nIntvl;
nIntvl.x=(*iter).x;
nIntvl.h=(*iter).h;
if(x3==x1)
bdls2.erase(nIntvl);
nIntvl.x=x1;
nIntvl.h=h1;
bdls2.insert(nIntvl);
if(x4>x2)
{
INTVL nIntvl;
nIntvl.x=x2;
nIntvl.h=h2;
bdls2.insert(nIntvl);
}
}

}
bdls=bdls2;
}
int lastH=0;
for(set<INTVL,ltstr2>::iterator iter=bdls.begin();iter!=bdls.end();iter++)
{
if((*iter).h==lastH)continue;
cout<<(*iter).x<<" "<<(*iter).h<<endl;
lastH=(*iter).h;
}
}

Logic is important. Keep clear of the logic when writing code. dont rush.