chiragjain1989
BAN USERUse a queue and a stack
q.insert(root)
n=1
flag=1
Repeat while(queue is not empty)
1. Remove n no. of elements (or less if not present) from queue and push them in stack
2. while(stack is not empty)
node=pop(stack)
if node!=NULL then visit node
if(node!=NULL&&flag==1)
q.insert(node->left); q.insert(node->right)
else if(node!=NULL&&flag==2)
q.insert(node->right); q.insert(node->left)
3. n*=2
4. if(flag==1)
flag=2;
else
flag=1;
5. Go to step 1
the second function simply tries each sub string from starting, if any valid word is found, another word from the next character is tried to be found.
Pos array just saves all the index values where the spaces have to be inserted in the original string
First function just inserts all the spaces in the original string according to the pos array.
int pos[MAXLEN];
int ind=0;
void separate(char * str)
{
if(ifseparable(str,0))
{
for(i=strlen(str)+ind,j=strlen(str);i>=0&&j>=0;i--)
{
if(i==pos[ind-1])
{
str[i]=' ';
ind--;
}
else
{
str[i]=str[j];
j--;
}
}
printf("%s",str);
}
else
printf("\nNot separable");
}
int ifseparable(char * str, int index)
{
char word[strlen(str)+1];
int i;
if(str==NULL)
return 0;
if(str[index]=='\0')
return 1;
i=0;
while(str[index])
{
word[i]=str[index];
word[i+1]='\0';
if(lookDictionary(word)&&ifseparable(str,index+1))
{
pos[ind++]=index;
return 1;
}
index++;
i++;
}
return 0;
}
How about using splay trees. When we have to insert a new item and cache is full, the node with the largest depth in the tree can be replaced with the newer item.
- chiragjain1989 April 18, 2011int min_selections(int arr[],int n)
{
int i,j;
int dp[n],min;
dp[n-1]=1;
for(int i=n-2;i>=0;i--)
{
dp[i]=1;
min=10000;
for(j=1;j<=arr[i]&&(i+j)<n;j++)
if(dp[i+j]<min)
min=dp[i+j];
dp[i]+=min;
}
return dp[0];
}
int main(void)
{
int n,arr[20];
cout<<"Size: ";
cin>>n;
for(int i=0;i<n;i++)
cin>>arr[i];
cout<<min_selections(arr,n);
}
int insertQ(int item)
{
stack1.push(item);
return;
}
int deleteQ(void)
{
if(isempty(stack1)&&isempty(stack2))
return UnderFlow;
if(!isempty(stack2))
return pop(stack2);
while(!isempty(stack1))
stack2.push(stack1.pop());
return pop(stack2);
}
Above method 1 had many errors which I updated but they are no longer there and I am not going to type them again :)
But the algo should be clear I suppose
Method 2: O(n)
Step1: Make Suffix tree of the string and its reverse O(n)
step2: Find the internal node representing longest string in the suffix tree that has its successors as leaf nodes from both the string. This longest sting is the Longest palindrome
Another O(n^2) method is to find the longest common substring between the string and its reverse.
step1: compute the longest suffixes of the strings
suffix[i,j]=suffix[i-1,j-1]+1 if str1[i]==str2[j]
=0 otherwise
maxlength palindrome = max(suffix[i,j]) for all 0<=i,j<n
to find the palindrome trace backward diagonally until suffix[i,j] are non zero
for e.g. ABRACECARCD
DCRACECARBA
suffix mat:
A B R A C E C A R C D
D 0 0 0 0 0 0 0 0 0 0 1
C 0 0 0 0 1 0 1 0 0 1 0
R 0 0 1 0 0 0 0 0 1 0 0
A 1 0 0 2 0 0 0 1 0 0 0
C 0 0 0 0 3 0 1 0 0 1 0
E 0 0 0 0 0 4 0 0 0 0 0
C 0 0 0 0 1 0 5 0 0 1 0
A 0 0 0 0 0 0 0 6 0 0 0
R 0 0 0 0 0 0 0 0 7 0 0
B ..................... so on
A
Hope its very clear
Method 1: O(n^2)
Assuming odd length palindrome, assume each character as a center of the palindrome and move two pointers left and right.
Similarly for even length palindromes
int MaxPalin(char * str)
{
//Assuming odd length palindrome
char * up,* down,* ptr1,* ptr2;
int maxlen=0;
for(ptr1=str;*ptr1;ptr1++)
{
for(up=down=ptr1;up>=str&&down&&*up==*down;up--,down++);
if(*down=='\0'&&up<str)
return strlen(str);
if(*down=='\0'||up<str&&down-up>maxlen)
maxlen=down-up;
else if(down-up+1>str)
maxlen=down-up+1;
}
//assuming even length palindromes
for(ptr1=str,ptr2=str+1;*ptr2;ptr1++,ptr2++)
if(*ptr1==*ptr2)
{
for(up=ptr1,down=ptr2;up>=str&&*down&&*up==*down;up--,down++);
if(*down=='\0'&&up<str)
return strlen(str);
if(*down=='\0'||up<str&&down-up>maxlen)
maxlen=down-up;
else if(down-up+1>str)
maxlen=down-up+1;
}
return maxlen;
}
I think a simple inorder traversal can do:
Global struct node * prevNode=NULL;
int getSuccessors(struct node * root)
{
if(!root)
return;
getSuccessors(root->left);
if(prevNode)
prevNode->successor=root;
prevNode=root;
getSuccessors(root->right);
return;
}
@Rayden: Your first solution is cool :)
- chiragjain1989 January 10, 2011int mirrorBST(struct node * root)
{
struct node * temp;
if(!root)
return;
stack.push(root);
while(!empty(stack))
{
root=stack.pop();
temp=root->left;
root->left=root->right;
root->right=temp;
if(root->right)
stack.push(root->right);
if(root->left)
stack.push(root->left);
}
return;
}
shuffle(int deck[])
{
for(i=51;i>=0;i--)
{
r=rand()%i;
t=deck[r];
deck[r]=deck[i];
deck[i]=t;
}
}
The TC is O(LogM*LogN)
- chiragjain1989 April 19, 2011