企业官网建设流程全解析

以下是 LeetCode 38. 外观数列 的 C 语言实现，采用迭代生成的方法，每次根据当前项生成下一项，直到得到第 n 项。

思路

外观数列的每一项都是对前一项的“读法”描述：

· 从第一项 “1” 开始；
· 遍历当前字符串，统计连续相同字符的个数，并将“个数 + 字符”拼接到新字符串中；
· 重复该过程 n-1 次即可得到第 n 项。

例如：

· 第 1 项：“1”
· 第 2 项：一个 1 → “11”
· 第 3 项：两个 1 → “21”
· 第 4 项：一个 2、一个 1 → “1211”
· 第 5 项：一个 1、一个 2、两个 1 → “111221”

代码实现

#include<stdio.h>#include<stdlib.h>#include<string.h>char*countAndSay(intn){// 第 1 项直接返回if(n==1){char*res=(char*)malloc(2);strcpy(res,"1");returnres;}// 分配足够大的缓冲区（第 30 项长度不超过 10000，足够安全）intcapacity=10000;char*cur=(char*)malloc(capacity);char*next=(char*)malloc(capacity);strcpy(cur,"1");// 迭代生成第 2 到第 n 项for(intstep=1;step<n;step++){intlen=0;intcurLen=strlen(cur);for(inti=0;i<curLen;){chardigit=cur[i];intcount=0;// 统计连续相同字符个数while(i<curLen&&cur[i]==digit){i++;count++;}// 将“个数 + 字符”追加到 next 中len+=sprintf(next+len,"%d%c",count,digit);}next[len]='\0';// 交换 cur 和 next，准备下一轮char*temp=cur;cur=next;next=temp;}// 释放多余缓冲区，返回最终结果free(next);returncur;// 调用者负责 free}

复杂度分析

· 时间复杂度：O(m)，其中 m 是第 n 项的长度。每一项的生成都需要遍历前一项，总长度呈指数增长，但 n ≤ 30，实际计算量很小。
· 空间复杂度：O(m)，使用了两个缓冲区，每个大小固定为 10000（足够容纳第 30 项，实际可动态调整）。

说明

· 使用 sprintf 将整数 count 转为字符串并追加到缓冲区，简单直观。
· 由于题目 n 的最大值为 30，第 30 项长度约 5808 个字符，因此分配 10000 字节的缓冲区绝对安全，且不会造成过大内存浪费。
· 返回的字符串由 malloc 分配，调用者需要 free 释放，符合 LeetCode 的要求。
· 如果希望更精确地管理内存，可以在每次迭代时计算所需长度并动态分配，但本实现已足够通过评测。