题目分析
题目是要生成一个数列中的任意一项，其中的前五项如下所示：
- 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.
其中数列中的每一项都是一个字符串，而且每一项都是由前一项产生的。
编程实现
C实现
内存区域可以分为栈，堆，静态存储区和常量存储区。局部变量，函数形参，临时变量都是在栈上获得内存的，它们获取的方式都是由编译器自动执行的。 C标准函数库提供了许多函数来实现对堆上内存管理，其中包括：malloc函数，free函数，calloc函数和realloc函数。使用这些函数需要包含头文件stdlib.h
之所以使用堆，是因为栈只能用来保存临时变量、局部变量和函数参数。在函数返回时，自动释放所占用的存储空间。而堆上的内存空间不会自动释放，直到调用free()函数，才会释放堆上的存储空间。
C 语言中 malloc、calloc、realloc 和free 函数的使用方法
1、malloc()
头文件：stdlib.h
声明：void * malloc(int n);
含义：在堆上，分配n个字节，并返回void指针类型。
返回值：分配内存成功，返回分配的堆上存储空间的首地址；否则，返回NULL
2、calloc()
头文件：stdlib.h
声明：void *calloc(int n, int size);
含义：在堆上，分配nsize个字节，并初始化为0，返回void 类型
返回值：同malloc() 函数
3、recalloc()
头文件：stdlib.h
声明：void * realloc(void * p,int n);
含义：重新分配堆上的void指针p所指的空间为n个字节，同时会复制原有内容到新分配的堆上存储空间。注意，若原来的void指针p在堆上的空间不大于n个字节，则保持不变。
返回值：同malloc() 函数
4、free()
头文件：stdlib.h
声明：void free (void * p);
含义：释放void指针p所指的堆上的空间。
返回值：无
5、memset()
头文件：string.h
声明：void * memset (void * p, int c, int n) ;
含义：对于void指针p为首地址的n个字节，将其中的每个字节设置为c。
返回值：返回指向存储区域 p 的void类型指针。
程序实现
这里用到了C语言中的malloc()函数。
char* countAndSay(int n) {
if( n == 1 ) return "1";
char *cur = malloc(2), *tmp; //之所以分配两个字节，由于数列中除了第一个元素以外的其他元素，都至少占两个字节。
cur[0] = '1';
cur[1] = 0;
int len, idx, j, count;
for(int i = 2; i <= n; ++i)
{
len = strlen(cur);
tmp = malloc(len * 3);
memset(tmp, 0, len * 3); //初始化堆
count = 1;
for(idx = 1, j = 0; idx < len; ++idx)
{
if(cur[idx] == cur[idx-1])
{
++count;
}
else
{
tmp[j++] = '0' + count; //count转化为char型
tmp[j++] = cur[idx-1];
count = 1;
}
}//end of for
tmp[j++] = '0' + count;
tmp[j++] = cur[len-1];
free(cur); //释放内存
cur = tmp;
}
return cur;
}
C++实现
class Solution {
public:
string countAndSay(int n) {
if (n == 0) return "";
string res = "1";
while (--n){
string cur = "";
for (int i = 0; i < res.size(); i++){ //遍历字符串中的每个数字
int count = 1;
while ((i + 1 < res.size()) && (res[i] == res[i + 1])){ //比较每个数字与其后面的数字是否相等
count++; //相等则count + 1
i++; //用于继续比较每个数字后面与其后所有数字，直至超出字符串长度或两数字不相等
}
cur += to_string(count) + res[i]; //count转化为字符串和字符串中的数字加到cur后面
}
res = cur; //字符串cur赋给res，重复上面步骤，直至跳出循环
}
return res;
}
};
总结反思
C和C++的时间复杂度几乎一样。这道题说白了就是计数字符串中的每个数字的个数，整个数列中的每个元素又都是由前一个元素再次计数字符串中的每个数字的个数产生的。
