Manku
BAN USERnode* reverseListAlt(node *record, int k)
{
int count= 0;
node* head, *prev;
node* first= record;
node* last= record;
if (k<0)
head= record;
else if(k==0)
head= reverseList(first, NULL);
else
{
//reverse first k nodes
while(count < k && last!= NULL)
{
last= last->next;
count++;
}
head= reverseList(first, last);
// Reverse Alternate k nodes
while(last != NULL)
{
//Skip k ndoes
while(count > 0 && last!=NULL)
{
prev= last;
last= last->next;
count--;
}
//Reverse K nodes
first= last;
while(count < k && last!=NULL)
{
last= last->next;
count++;
}
prev->next= reverseList(first, last);
}
}
return head;
}
node* reverseListAlt(node *record, int k)
{
int count= 0;
node* head, *prev;
node* first= record;
node* last= record;
if (k<0)
head= record;
else if(k==0)
head= reverseList(first, NULL);
else
{
//reverse first k nodes
while(count < k && last!= NULL)
{
last= last->next;
count++;
}
head= reverseList(first, last);
// Reverse Alternate k nodes
while(last != NULL)
{
//Skip k ndoes
while(count > 0 && last!=NULL)
{
prev= last;
last= last->next;
count--;
}
//Reverse K nodes
first= last;
while(count < k && last!=NULL)
{
last= last->next;
count++;
}
prev->next= reverseList(first, last);
}
}
return head;
}
How about this.
Take an int array of size 26: where arr[0]=> 'a' and arr[25]=>'z'. initialize it with -INT_MAX.
1. p= &str2[0];
2. repeat step 3 till *p= '\0';
3. if(arr[*p]= -INT_MAX)
arr[*p]= 0;
else
arr[*p]++;
After above, we wud have array initialized with occurrence of each characters in str2. We would use this arry for matching with str1.
Now traverse str1 from left to right with two pointers p1 and p2.
1. P1= str1[0], P2=str1[0].
2. while(1)
if (arr[*P1] != -INT_MAX), arr[*P1]--; break; //We reached first matching char
else P1++;
3. P2= p1+1; // Make P2 points to next char in str1;
4. Repeat steps 5-7 till p1 and p2 both reach end of str1.
5. If All element in arr are '0' or '-INT_MAX', we found a window.
store index of p1 and p2 for MIN(earlier window, found window).
goto step 6.
else
arr[*P2]--;
P2++;
go to step 5;
6. while(1)
if (arr[*P1] != -INT_MAX),
arr[*P1]--;
break; //We reached a matching char
else
arr[P1*]++;
P1++;
7. Goto step 5.
8. Return minimum window.
from a given stone, we can easily find out where all frog can go (based on the number on that stone). Create a graph with edges starting from frogstone to all possible stones where it can reach and mark the edges. Once we have complete graph information, use Djikstra shortest path algo to find the shortest path.
Wouldn't it work?
make a binary tree where left child edge is (-) and right child edge is (+). so say for 1 ,9, 1, 2 we would have binary tree something like:
1
(-) / \(+)
9 9
(-)/ \(+) (-)/ \(+)
1 1 1 1
and so on.
Now at the leaf node, we have final number (i.e. if we start from root and apply operator on edge to each internal node). Search in leaf node for the result required (R) and print the path as output.
How about this:
1. Say root is R.
2. do an in-order traversal and keep putting element in a stack (say stack1) till we reach R to be put in stack1 (i.e. we processed all element in left sub tree).
3. Pop R.
4. Now we would go to right sub tree of R.
5. Process an element E in in-order traversal,
6. POP from stack1.
if (stack empty)
return false
else if (popped element = E)
goto 5.
else
return false;
7. if (stack empty)
return true;
else
return false;
Here is the function. Well tested.
- Manku September 08, 2016