欢迎来到李耶的频道【LeetCode面试题】。外观数列38.外观数列题目「外观数列」是一个数位字符串序列由递归公式定义countAndSay(1) 1countAndSay(n)是countAndSay(n-1)的行程长度编码RLE。行程长度编码RLE是一种字符串压缩方法其工作原理是将连续相同字符组替换为该组的长度后跟字符本身。例如字符串3322251的 RLE 是23321511因为33替换为23222替换为325替换为151替换为11。输入n 1 输出1 解释这是基本情况。输入n 4 输出1211 解释 countAndSay(1) 1 countAndSay(2) 读 1 一 个 1 11 countAndSay(3) 读 11 二 个 1 21 countAndSay(4) 读 21 一 个 2 一 个 1 12 11 1211提示1 n 30解法一模拟法迭代思路从基础项1开始通过循环n-1次不断对当前字符串应用“外观”描述规则生成下一项直到得到第n项。具体操作是扫描当前字符串统计连续相同字符的数量并将“数量 字符”追加到新字符串中。functioncountAndSay(n){letcurrentStr1;for(leti2;in;i){letnextStr;letcount1;for(letj0;jcurrentStr.length;j){if(j1currentStr.lengthcurrentStr[j]currentStr[j1]){count;}else{nextStrcountcurrentStr[j];count1;}}currentStrnextStr;}returncurrentStr;}时间复杂度 / 空间复杂度O(n * m) / O(m)其中 n 是给定的正整数m 是生成字符串的最大长度。优势逻辑清晰是解决此题最常用、最直观的方法。解法二递归法思路根据题目给出的递归定义countAndSay(n)依赖于countAndSay(n-1)。因此可以编写一个递归函数先求出第n-1项然后对其进行“外观”描述得到第n项。functioncountAndSay(n){if(n1)return1;constprevStrcountAndSay(n-1);letresult;letcount1;for(leti0;iprevStr.length;i){if(i1prevStr.lengthprevStr[i]prevStr[i1]){count;}else{resultcountprevStr[i];count1;}}returnresult;}时间复杂度 / 空间复杂度O(n * m) / O(n)。递归调用栈深度为 n因此空间复杂度为 O(n)。优势代码结构与题目定义高度一致非常简洁易于理解。解法对比解法时间 / 空间复杂度优势推荐指数模拟法迭代O(n * m) / O(m)完全迭代避免递归栈风险性能稳定⭐⭐⭐⭐⭐递归法O(n * m) / O(n)代码优雅与问题定义天然契合便于理解⭐⭐⭐⭐扩展题字符串压缩实现一个基本的字符串压缩算法将连续相同字符替换为字符加出现次数。计数二进制子串给定一个字符串统计具有相同数量连续 0 和 1 的非空子串数量同样涉及“连续相同字符”的统计思想。“差之毫厘失之千里。” —— 《礼记·经解》关注李耶每天一道面试题一起卷起来