（PAT乙级） 1084 外观数列 （C语言实现，不要使用strcat）

外观数列是指具有以下特点的整数序列：

d, d1, d111, d113, d11231, d112213111, ...
1

它从不等于 1 的数字 d 开始，序列的第 n+1 项是对第 n 项的描述。比如第 2 项表示第 1 项有 1 个 d，所以就是 d1；第 2 项是 1 个 d（对应 d1）和 1 个 1（对应 11），所以第 3 项就是 d111。又比如第 4 项是 d113，其描述就是 1 个 d，2 个 1，1 个 3，所以下一项就是 d11231。当然这个定义对 d = 1 也成立。本题要求你推算任意给定数字 d 的外观数列的第 N 项。

输入格式：

输入第一行给出 [0,9] 范围内的一个整数 d、以及一个正整数 N（≤ 40），用空格分隔。

输出格式：

在一行中给出数字 d 的外观数列的第 N 项。

输入样例：

1 8
1

输出样例：

1123123111
1

题目分析：

本题和 PTA 1078压缩字符串一题比较类似https://pintia.cn/problem-sets/994805260223102976/exam/problems/994805262018265088

不过需要注意的是 strcat的效率问题，strcat在追加字符上细性能比较差，本题如果使用strcat实现 +=字符的效果会出现运行超时的情况

而且，本题的结果会比较长，建议使用100000以上的数组空间！

如何优化strcat？

这里我的做法是使用index索引代替，使用index索引时间上能缩小非常大的时间。下图中如果使用strcat会超过400ms，使用索引之后反而只需要4ms

#include <ctype.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void reverse_str(char *str){
	int left=0,right=strlen(str)-1;
	char ch;
	while(left<right){
		ch=str[left];
		str[left]=str[right];
		str[right]=ch;
		left++;
		right--;	
	}
}

char* to_string(int num){
	char* str=calloc(500,sizeof(char));
	memset(str,'\0',sizeof(str));
	int index=0;
	while(num!=0){
		str[index++]=(num%10)+'0';
		num/=10;
	}
	reverse_str(str);
	return str;
}

char* getnext(char *str){
	int num[500];
	char *nstr=calloc(100000,sizeof(char));
	memset(num,0,sizeof(num));
	int i,j,index=0;
	num[str[0]]++;
	for(i=1;str[i]!='\0';i++){
		if(str[i]!=str[i-1]){
			nstr[index++]=str[i-1];
			nstr[index++]=num[str[i-1]]+'0';
//			strcat(nstr,ch);
			num[str[i-1]]=0;
		}
		num[str[i]]++;
	}
	
	int end=strlen(str)-1;
	nstr[index++]=str[end];
	nstr[index++]=num[str[end]]+'0';
//	strcat(nstr,ch);
	return nstr;
}

int main() {
  int d,n,i;
  char str[100000]="";
  scanf("%d %d",&d,&n);
  str[0]=d+'0';
  
  char *next,*cur=str;
  for(i=2;i<=n;i++){
  	next=getnext(cur);
  	cur=next;
//  	printf("%s\n",str);
  }
  printf("%s\n",cur);
  return 0;
}

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69