lyzoridc
BAN USERCoding Language: C/C++, Python
Excel at: algorithm & design patterens
Degree: a Master @cs.whu.edu.cn
Work experience: None
Contact me: lyzoridc@gamil.com
two traversals to get it done!
1st, reverse the list to the new list
2nd, from the previous list's last one, we reverse this new list back to original order, at the same time we count the number of current handling node, when it's nth , we print it out.
ele findLastNth(node *head, int n)
{
int i;
node *p, *q ,*cur;
p=cur=head;
q=p->next;
p->next=NULL;
while(q!=NULL){
cur=q;
q=q->next;
cur->next=p;
p=cur;
}
q=p->next;
p->next=NULL;
i=1;
while(q!=NULL){
cur=q;
q=q->next;
cur->next=p;
if(i==n)
return p->ele;
p=cur;
i++;
}
}
/*The code is here, the space that Array points to should be enough to hold extra chars*/
void text_handler(char *Array)
{
int curdiff=0;
int prepos=0;
int end=strlen(Array);
int indicator=0;
int tmpi;
for(int i=0;i<end;++i){
if(Array[i]=='a'){
if(curdiff==1)
indicator=1;/*from positive to 0*/
curdiff-=1;
}
else if(Array[i]=='b'){
if(curdiff==-1)
indicator=-1;/*from negative to 0*/
curdiff+=1;
}
if(curdiff==0){
if(indicator ==0)
continue;
else{
if(indicator==-1){
/*from font to back*/
int tmpi=prepos;
for(int j=prepos;j<=i;++j){
if(Array[j]=='a')
continue;
else if(Array[j]=='b'){
Array[tmpi++]='b';
Array[tmpi++]='d';
}
else
Array[tmpi++]=Array[j];
}
}
else{
/*from back to front*/
int tmpi=i;
for(int j=i;j>=prepos;--j){
if(Array[j]=='a')
continue;
else if(Array[j]=='b'){
Array[tmpi--]='d';
Array[tmpi--]='b';
}
else
Array[tmpi--]=Array[j];
}
}
prepos=i+1;
indicator=0;
}
}
}
if( (indicator==0&&curdiff < 0) || indicator==1){
tmpi=prepos;
for(int j=prepos;j<=end-1;++j){
if(Array[j]=='a')
continue;
else if(Array[j]=='b'){
Array[tmpi++]='b';
Array[tmpi++]='d';
}
else
Array[tmpi++]=Array[j];
}
}
else if( (indicator==0 &&curdiff>0) || indicator==-1){
tmpi=curdiff+end-1;
for(int j=end-1;j>=prepos;--j){
if(Array[j]=='a')
continue;
else if(Array[j]=='b'){
Array[tmpi--]='d';
Array[tmpi--]='b';
}
else
Array[tmpi--]=Array[j];
}
}
Array[end+curdiff]='\0';
}
@kaps84
because d1/e1 is slower than b1/c1, if there is b1/c1, d1/e1 can never reach top3
we only know b1 is faster than b2, a2 is faster than a3, b1 is faster than c1.
but we should continue judging whether b1 is faster than a2/a3, whether c1 is faster than a2/a3, or b2 is faster than c1, or their opposite results.
Above correct answers all need another temporary O(n) space to assist.
This method only needs O(1) space to solve it , stated as follows:
1. Define curdiff as an integer , whose value indicates difference length between current temporary ended array(if this ended position is i) and its corresponding transformed array, let me explain it with an example:
>>if original char array is :[bbeeaa...] /* ellipsis means other left unhandled chars*/
>>its corresponding transformed format: [bdbdee...]
>>initialize curdiff=0
>>so when i=1, curdiff=1, because [b] is transformed into [bd], latter is 1 longer than prior
>> when i=2, curdiff=2, because [bb] is transformed into[bdbd], latter is 2 longer than prior
>> when i=3, curdiff=2, when i=4 curdiff=2
>> when i=5, curdiff=1 because [bbeea] is transformed into [bdbdee]
>> when i=6, curdiff=0 because [bbeeaa] is transformed into [bdbdee], they are equal
2. When reaching a position that curdiff=0, let this position be i, we can transform this prior array without considerating posterior array, because this temporary transformed array will not override posterior places. Moreover, define prepos(int) as previous transform's last position, before scaning prepos=0. There are several cases to be considerated:
>> 1) if curdiff approaches 0 from positive value: we will transform this temp array (values between [prepos+1,i]) from back to front ,and update prepos=i.
>> 2) if curdiff approaches 0 from negative value: we will transform this temp array (values between [prepos+1,i]) from front to back ,and update prepos=i.
>> 3) if curdiff stays 0 since last transformation: we only need to reserse it, and update prepos=i.
Then we restart the scanning process from position i+1, until all chars in the array are scan
/* Transform the array from back to front means that we transform the array from position i to position prepos+1 as the rule says*/
3. When scanning is done, if curdiff > 0, we will transform the unhandled elements(values between [prepos+1,end]) from back to front, but we have to save char from position end+curdiff to position prepos+1, so sufficient spare space are needed.Vice versa , if curdiff<0, we will transform the unhandled elements from front to back.
This method only needs 3 extra variables(curdiff,i,prepos) to save some information, which costs O(1) space. Because we only need scan the array twice, its time complexity is O(n).
answer :7 races
reason details:
1. we have 5 races for 25 horses that 5 horses on a team, define each team as a, b, c, d, e.
2. carry a best horse race for each team first place, define them as a.1,b.1,c.1,d.1,e.1
3. assume prior best horse race 's top 3 places are a.1 b.1 c.1 , so we know the fastest horse is a.1, we only need to take last race to know who are second and third quickest horse. The horses that participate in this race are b.1 b.2 a.2 a.3 c.1 , this race 's top 2 places are 2nd and 3rd quickest horses
Repgladyskcombs, Personnel at Green Bricks
Hello, I am Gladys. I am a Industrial Photographer. I started off my photographic career as a News photographer based ...
Repbrandysolsen, Area Sales Manager at AMD
I am a Social butterflies who enjoy travel.Have fun doing this job and project an atmosphere that reflects Amazon ...
great, this code is right, simple and very understandable~
- lyzoridc March 29, 2010:P