leehomyc
BAN USERnon recursive:
void GetSentence(string text,vector<string> dictionary)
{
deque<pair<string,int>> my_deque;
hash_set<string> my_hash;
int N=dictionary.size();
vector<int> temp(text.length());
fill(temp.begin(),temp.end(),-1);
for(int i=0;i<N;i++)
my_hash.insert(dictionary[i]);
my_deque.push_back(pair<string,int>::pair("",-1));
while(!my_deque.empty())
{
pair<string,int> top_string=my_deque.back();
int cur_pos=top_string.second;
if(cur_pos==text.length()-1)
break;
bool flag=false;
for(int i=cur_pos+1;i<text.length();i++)
{
string sub_string=text.substr(cur_pos+1,i-cur_pos);
hash_set<string>::iterator iter=my_hash.find(sub_string);
if(iter!=my_hash.end() && i>temp[cur_pos+1])
{
my_deque.push_back(pair<string,int>::pair(sub_string,i));
temp[cur_pos+1]=i;
flag=true;
break;
}
}
if(!flag)
my_deque.pop_back();
}
if(!my_deque.empty())
my_deque.pop_front();
while(!my_deque.empty())
{
pair<string,int> cur_pair=my_deque.front();
my_deque.pop_front();
cout<<cur_pair.first<<" ";
}
cout<<endl;
}
void GetSentence(string text,vector<string> dictionary)
{
deque<pair<string,int>> my_deque;
hash_set<string> my_hash;
int N=dictionary.size();
vector<int> temp(text.length());
fill(temp.begin(),temp.end(),-1);
for(int i=0;i<N;i++)
my_hash.insert(dictionary[i]);
my_deque.push_back(pair<string,int>::pair("",-1));
while(!my_deque.empty())
{
pair<string,int> top_string=my_deque.back();
int cur_pos=top_string.second;
if(cur_pos==text.length()-1)
break;
bool flag=false;
for(int i=cur_pos+1;i<text.length();i++)
{
string sub_string=text.substr(cur_pos+1,i-cur_pos);
hash_set<string>::iterator iter=my_hash.find(sub_string);
if(iter!=my_hash.end() && i>temp[cur_pos+1])
{
my_deque.push_back(pair<string,int>::pair(sub_string,i));
temp[cur_pos+1]=i;
flag=true;
break;
}
}
if(!flag)
my_deque.pop_back();
}
if(!my_deque.empty())
my_deque.pop_front();
while(!my_deque.empty())
{
pair<string,int> cur_pair=my_deque.front();
my_deque.pop_front();
cout<<cur_pair.first<<" ";
}
cout<<endl;
}
No recursion solution, use post-order traversal:
int GetDiameter2(int& height)
{
if(!root)return 0;
stack<Node*> s;
s.push(root);
Node* prev=NULL;
int res=0;
while(!s.empty())
{
Node* cur=s.top();
if(!prev || prev->L==cur || prev->R==cur)
{
if(cur->L)
s.push(cur->L);
else if(cur->R)
s.push(cur->R);
else
{
s.pop();
cur->tmp=1;
res=max(res,1);
}
}
else if(cur->L==prev)
{
if(cur->R)
s.push(cur->R);
else
{
s.pop();
cur->tmp=cur->L->tmp+1;
res=max(res,cur->L->tmp+1);
}
}
else if(cur->R==prev)
{
s.pop();
if(cur->L)
{
cur->tmp=max(cur->L->tmp,cur->R->tmp)+1;
res=max(res,cur->L->tmp+cur->R->tmp+1);
}
else
{
cur->tmp=cur->R->tmp+1;
res=max(res,cur->R->tmp+1);
}
}
prev=cur;
}
return res;
}
please don't use two recursion:
struct Node
{
Node* L;
Node* R;
int val;
};
int GetDiameter(Node* root,int& height)
{
if(!root)
{
height=0;
return 0;
}
int lHeight,rHeight;
int lDiameter=(root->L,lHeight);
int rDiameter=(root->R,rHeight);
int res=max(lDiameter,rDiameter);
res=max(res,lHeight+rHeight+1);
height=max(lHeight,rHeight)+1;
return res;
}
use stl, and it is much more convenient:
bool MyCompare(pair<int,int> p1,pair<int,int> p2){return p1.first<p2.first;}
bool MyCompare2(int p1,pair<int,int> p2){return p1<p2.first;}
int NumOfIntersection(vector<int> A)
{
int N=A.size();
vector<pair<int,int>> P;
for(int i=0;i<N;i++)
{
int start_pt=i-A[i],end_pt=i+A[i];
P.push_back(pair<int,int>::pair(start_pt,end_pt));
}
sort(P.begin(),P.end(),MyCompare);
int res=0;
for(int i=0;i<N;i++)
{
vector<pair<int,int>>::iterator iter=upper_bound(P.begin()+i,P.end(),P[i].second,MyCompare2);
iter--;
int id=iter-P.begin();
res+=(id-i);
}
return res;
}
dp:
int max_coin(vector<int> pots)
{
vector<vector<int>> dp_table;
int pot_num=pots.size();
dp_table.resize(pot_num);
for(int i=0;i<pot_num;i++)
{
dp_table[i].resize(pot_num);
for(int j=0;j<i;j++)
dp_table[i][j]=0;
}
for(int k=0;k<pot_num;k++)
{
for(int i=0;i<pot_num;i++)
{
int j=i+k;
if(j>=pot_num)
continue;
double pots1,pots2;
if(i+2<pots.size() && j-1>=0)
pots1=pots[i]+min(dp_table[i+2][j],dp_table[i+1][j-1]);
else
pots1=pots[i];
if(i+1<pots.size() && j-2>=0)
pots2=pots[j]+min(dp_table[i+1][j-1],dp_table[i][j-2]);
else
pots2=pots[j];
dp_table[i][j]=max(pots1,pots2);
}
}
return dp_table[0][pot_num-1];
}
dfs:
#include<iostream>
#include<stack>
using namespace std;
struct Pos
{
int r;
int c;
bool visited;
int neighbor;
};
int neighbor_r[4]={0,1,0,-1};
int neighbor_c[4]={-1,0,1,0};
int MazeWalk(bool* maze,int row,int col)
{
int res=0;
vector<vector<Pos>> rec;
rec.resize(row);
for(int i=0;i<row;i++)
{
rec[i].resize(col);
for(int j=0;j<col;j++)
{
Pos my_pos;
my_pos.r=i;
my_pos.c=j;
my_pos.visited=maze[i*col+j];
my_pos.neighbor=0;
rec[i][j]=my_pos;
}
}
stack<Pos> my_stack;
rec[0][0].visited=true;
my_stack.push(rec[0][0]);
while(!my_stack.empty())
{
Pos& cur_pos=my_stack.top();
int cur_r=cur_pos.r,cur_c=cur_pos.c;
//cout<<cur_r<<" "<<cur_c<<" "<<cur_pos.neighbor<<endl;
if(cur_r==row-1 && cur_c==col-1)
{
res++;
rec[cur_r][cur_c].visited=false;
my_stack.pop();
continue;
}
if(cur_pos.neighbor>=4)
{
rec[cur_r][cur_c].visited=false;
my_stack.pop();
continue;
}
int new_r,new_c;
new_r=cur_r+neighbor_r[cur_pos.neighbor];
new_c=cur_c+neighbor_c[cur_pos.neighbor];
cur_pos.neighbor++;
if(new_r>=0 && new_c>=0 && new_r<row && new_c<col && rec[new_r][new_c].visited==false)
{
rec[new_r][new_c].visited=true;
my_stack.push(rec[new_r][new_c]);
}
}
return res;
}
We can divide the problem into several small problems:
1) For each node p, is the subtree with p as its root a binary search tree?
2) If it is a binary search tree, what is the size of the tree?
We can use recursion to do this:
Step1. for each node p, compute the minimum and maximum element of the subtree that rooted in p, as well as the size of the subtree.
Step 2. for each node p, check the maximum element of its left subtree and the minimum element of its right subtree to see if it is a BST, and if it is, sum up the size of the left right subtree and itself to get the size.
Step 3. Traversal the tree to find out the maximum BST as its subtree.
- leehomyc March 05, 2013