peng
BAN USERMy name is Peng Liu
I am a master student major in Computer Science in Syracuse University, Syracuse, NY. I am looking for a full time job in 2013
My email : pengliu1989@gmail.com
My email : pengliu1989@gmail.com
Set a flag to do the reverse and traverse recursively
Node * rever(Node *n, int k, int m,int flag)
{
if(n==NULL)
return NULL;
if(flag==0) // do the reverse
{
Node *pre=n;
for(int i=0;i<k;i++)
{
if(pre->next !=NUL)
{
Node *tmp=pre->next;
tmp->next=pre;
pre=tmp;
}
else
{
n->next=NULL;
return pre;
}
}
flag=1;
n->next=rever(pre->next,k,m,flag);
return pre;
}
else // do the traverse
{
Node *head=n;
for(int i=0;i<m;i++)
{
if(n!=NULL)
n=n->next;
}
flag=0;
n->next=rever(n->next,k,m,flag);
return head;
}
}
an implementation of Cyrus's idea
bool findIt( queue<Node *> qu. Node *head, Node *n)
{
if(head==NULL)
return false;
if(head==n)
return true;
if(findIt(qu,head->left,n))
{
st.push(head->left);
return true;
}
if(findIt(qu,head->right,n))
{
st.push(head->right);
return true;
}
return false;
}
void search(Node *head, int num, int k)
{
if(head==NULL)
return NULL;
if(num==k)
cout<<head<<endl;
while(num<k)
{
search(head->left,num+1,k);
search(head->right,num+1,k);
}
}
void find(Node *head, Node *n, int k)
{
queue<Node *> qu;
bool check=findIt(st,head,n);
if(!check)
return ;
Node *pre=n;
for(int i=1; i<=k;i++)
{
Node *tmp= qu.front();
qu.pop();
if(i==k)
{
count<<*tmp<<endl;
return;
}
if(pre==tmp->left)
{
pre=tmp;
search(tmp->left,i+1);
}
if(pre==tmp->right)
{
pre=tmp;
search(tmp->right,i+1);
}
}
}
If the number of integers are not too large. I will make an hash table to record every integer is contained by which sets.
for example :
s1 {1,2,3,4}
s2 {3,4,5,6,7}
s3 {7,8,9}
s4 {6,11}
The hash table will be like
integer : 1-------2-------3-------4-------5-------6-------7-----------8-------9-------11
sets: ----s1-----s1---s1,s2 ---s1,s2----s2-----s2,s4--s2,s3-----s3-----s3-----s4
integer : 3-------4----------6-------7
sets: --s1,s2---s1,s2---s2,s4---s2,s3
(forget the dash here )
Whenever an integer has more then one set , there is a connection between the nodes.
So I keep deleting the set with the most frequency, until every integer has no more then one set
s1 : twice s2 : 4 times s3 : once s4: once
So I delete s2 here. After that , every integer has no more then one set .
Maybe I name the variable in the wrong way.
head is the previous Node of the sorted linked list
first , I choose the right node which is ptr1 here.
Then , make the previous node's next (head->next) to ptr1
Third, update the previous node (head=ptr1)
at last, update ptr1.
There is some bugs in my previous code . Here is tested code
Node * merge(Node *n)
{
if(n==NULL)
return NULL;
Node * ptr1=n;
Node * ptr1End=NULL;
Node * ptr2=n;
Node * head=NULL;
Node * m=head;
while(ptr2->next !=NULL)
{
if(ptr2->next->data < ptr2->data)
{
Node *tmp=ptr2->next;
ptr2->next=NULL;
ptr2=tmp;
break;
}
ptr2=ptr2->next;
}
while(ptr1!=NULL && ptr2!=NULL)
{
if(ptr1->data < ptr2->data)
{
if(head==NULL)
{
head=ptr1;
m=head;
ptr1=ptr1->next;
}
else
{
head->next=ptr1;
head=ptr1;
ptr1=ptr1->next;
}
}
else
{
if(head==NULL)
{
head=ptr2;
m=head;
ptr2=ptr2->next;
}
else
{
head->next=ptr2;
head=ptr2;
ptr2=ptr2->next;
}
}
}
if(ptr1==NULL)
{
head->next=ptr2;
}
if(ptr2==NULL)
{
head->next=ptr1;
}
return m;
}
Just an implementation of Matt's algo
Node * merge(Node *n)
{
if(n==NULL)
return NULL;
Node * ptr1=n;
Node * ptr1End=NULL;
Node * ptr2=n;
Node * head=NULL;
Node * m=head;
while(ptr2->next !=NULL)
{
if(ptr2->next->data < ptr2->data)
{
Node *tmp=ptr2->next;
ptr2->next=NULL;
ptr2=tmp;
break;
}
}
while(ptr1->next!=NULL && ptr2->next!=NULL)
{
if(ptr1->data < ptr2->data)
{
if(head==NULL)
{
head=ptr1;
m=head;
ptr1=ptr1->next;
}
else
{
head->next=ptr1;
head=ptr1;
ptr1=ptr1->next;
}
}
else
{
if(head==NULL)
{
head=ptr2;
m=head;
ptr1=ptr2->next;
}
else
{
head->next=ptr2;
head=ptr2;
ptr2=ptr2->next;
}
}
}
if(ptr1->next==NULL)
{
ptr1->next=ptr2;
}
if(ptr2->next==NULL)
{
ptr2->next=ptr1;
}
return m;
}
I think about make two array of size 256, one to record the order of characters, and the other is to record the number each character appears
char getUniqueCharacter()
{
int counter[256]={0};
char order[256]={0};
int i=0;
while(hasNext())
{
char tmp=getNext();
if(counter[tmp]==0)
order[i++]=tmp;
counter[tmp]++;
}
for(int j=0;j<256;j++)
{
char tmp=order[j];
if(tmp!='#')
{
if(counter[tmp]==1)
return tmp;
}
}
return '#';
}
O(n) runtime
Do not need to consider so many cases
- peng February 07, 2013suppose a1<a2 , b1<b2
void findDiff(int a1, int a2, int b1, int b2)
{
if(a1<b1)
{
while(a1!=b1)
{
cout<<a1<<endl;
a1++;
}
}
if(b2<a2)
{
while(b2!=a2)
{
cout<<a2<<endl;
a2--;
}
}
}