LEET code -- Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.


就是照著數字念
1211
從左邊開始
有一個1 -->11
有一個2 -->12
有兩個1 -->21
所以合起來變成111221

這個版本是紀錄所以階層的  但是這個後面記憶體吃太兇
而且他只要回傳第N階就好

要注意的是  像是current(第9行
不能取代成 level[i]++=count (第15行
一定要用指標

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

char* countAndSay(int n) { char *level[n]; level[0]=calloc(1,sizeof(char)); level[0][0]='1'; for(int i=1;i<n;i++){ level[i]=calloc(6*(i),sizeof(char)); char *last=level[i-1]; char *current = level[i]; int count=0,target=(int)*last; while(*last){ //printf("%c %s\n",target,last); if(target == (int)*last)count++; else{ *current++=(count+'0');//becareful the ASCII *current++=target;//no need to add '0' target=(int)*last; count=1; } last++; } *current++=(count+'0');//becareful the ASCII *current++=target;//no need to add '0' *current='\0'; //printf("%d: %s\n",i,level[i]); } return level[n-1]; }

-----------
所以只需要兩個指標來紀錄上一筆 跟當前這筆
在互相交換計算就好了
在7跟 8那邊用previous跟next來代表 誰是當下  誰是之前算好的

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

char* countAndSay(int n) { char *level[2]; int size=128; level[0]=calloc(size,sizeof(char)); level[1]=calloc(size,sizeof(char)); level[0][0]='1'; int previous=0;//indicate which is the previous int next=1; for(int i=1;i<n;i++){ char *last=level[previous]; char *current = level[next]; int count=0,target=(int)*last,total=0; while(*last){ //printf("%c %s\n",target,last); if(target == (int)*last)count++; else{ *current++=(count+'0');//becareful the ASCII *current++=target;//no need to add '0' target=(int)*last; count=1; total+=2; } last++; } *current++=(count+'0');//becareful the ASCII *current++=target;//no need to add '0' *current='\0'; //printf("%d: %s\n",i,level[next]); int temp=previous; previous=next; next=temp; if(total > size*0.5){ size*=3; level[0]=realloc(level[0],sizeof(char)*size); level[1]=realloc(level[1],sizeof(char)*size); } } return level[previous]; }