大家好，我是小卡皮巴拉
文章目录
目录
力扣题目：外观数列
题目描述
解题思路
问题理解
算法选择
具体思路
解题要点
完整代码（C++）
兄弟们共勉 ！！！
每篇前言
博客主页：小卡皮巴拉
咱的口号：🌹小比特，大梦想🌹
作者请求：由于博主水平有限，难免会有错误和不准之处，我也非常渴望知道这些错误，恳请大佬们批评斧正。
力扣题目：外观数列
原题链接：38. 外观数列 - 力扣（LeetCode）
题目描述
「外观数列」是一个数位字符串序列，由递归公式定义：
countAndSay(1) = "1"countAndSay(n)是countAndSay(n-1)的行程长度编码。
行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将连续相同字符（重复两次或更多次）替换为字符重复次数（运行长度）和字符的串联。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。
给定一个整数 n ，返回 外观数列 的第 n 个元素。
示例 1：
输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = "1" 的行程长度编码 = "11"
countAndSay(3) = "11" 的行程长度编码 = "21"
countAndSay(4) = "21" 的行程长度编码 = "1211"
示例 2：
输入：n = 1
输出："1"
解释：
这是基本情况。
解题思路
问题理解
本题要求根据外观数列的递归定义，求出外观数列的第 n 个元素。外观数列的递归定义为：countAndSay(1) = "1"，countAndSay(n) 是 countAndSay(n - 1) 的行程长度编码。行程长度编码是将连续相同字符替换为字符重复次数和字符的串联。
算法选择
采用模拟和双指针的方法，从外观数列的第一个元素 "1" 开始，依次对前一个结果进行行程长度编码，迭代 n - 1 次，最终得到第 n 个元素。
具体思路
-
初始化：将外观数列的第一个元素初始化为
"1"，存储在字符串ret中。 -
迭代生成：进行
n - 1次迭代，每次迭代对当前的ret进行行程长度编码。-
行程长度编码：使用双指针
left和right遍历当前字符串ret。left指针指向当前处理的字符，right指针用于找到连续相同字符的末尾。当right指向的字符与left指向的字符相同时，right指针右移。当right指向的字符与left指向的字符不同时，说明找到了一组连续相同的字符，其数量为right - left。将该数量转换为字符串，并与该字符拼接，添加到临时字符串tmp中。然后更新left指针到right指针的位置，继续处理下一组相同字符。 -
更新结果：一次行程长度编码完成后，将临时字符串
tmp的结果更新到ret中，为下一次迭代做准备。
-
-
返回结果：经过
n - 1次迭代后，ret即为外观数列的第n个元素，返回ret。
解题要点
-
迭代过程：明确需要进行
n - 1次迭代，每次迭代都对前一个结果进行行程长度编码。 -
双指针使用：使用双指针
left和right来遍历字符串，方便统计连续相同字符的数量。 -
行程长度编码：正确将连续相同字符的数量和字符进行拼接，生成行程长度编码的结果。
完整代码（C++）
class Solution {
public:string countAndSay(int n) {// 初始化外观数列的第一个元素为 "1"string ret = "1";// 进行 n - 1 次迭代，因为已经有了初始的 "1"，还需要进行 n - 1 次行程长度编码for(int i = 1; i < n; i++){// 临时字符串，用于存储每次迭代后的行程长度编码结果string tmp;// 获取当前字符串的长度int len = ret.size();// 使用双指针 left 和 right 来遍历字符串for(int left = 0, right = 0; right < len;){// 当 right 没有越界且当前字符和 left 指向的字符相同时，right 指针右移while(right < len && ret[left] == ret[right]) right++;// 将相同字符的数量（right - left）转换为字符串，并与该字符拼接，添加到临时字符串 tmp 中tmp += to_string(right - left) + ret[left];// 更新 left 指针到 right 指针的位置，继续下一组相同字符的处理left = right;}// 将临时字符串 tmp 的结果更新到 ret 中，为下一次迭代做准备ret = tmp;}// 返回外观数列的第 n 个元素return ret;}
};兄弟们共勉 ！！！
码字不易，求个三连
抱拳了兄弟们！
