东坑东莞网站建设,企业官网的重要性,模板网站优化,南宁世尊商贸网站建设目录 一、问题描述
二、解题思路
三、代码
四、复杂度分析 一、问题描述
「外观数列」是一个数位字符串序列#xff0c;由递归公式定义#xff1a;
countAndSay(1) 1countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
行程长度编码#xff08;RLE由递归公式定义
countAndSay(1) 1countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。
行程长度编码RLE是一种字符串压缩方法其工作原理是通过将连续相同字符重复两次或更多次替换为字符重复次数运行长度和字符的串联。例如要压缩字符串 3322251 我们将 33 用 23 替换将 222 用 32 替换将 5 用 15 替换并将 1 用 11 替换。因此压缩后字符串变为 23321511。
给定一个整数 n 返回 外观数列 的第 n 个元素。
二、解题思路
“外观数列”是一个通过递归生成的序列序列中的每一项是对前一项的描述。具体的描述方式类似于行程长度编码RLE即按字符连续重复的次数来描述每一位。
为了生成第 n 个元素我们需要从第 1 项开始逐步构造后续项。第 1 项为 1后续每一项由对前一项进行“描述”得到。
例如
countAndSay(1) 1countAndSay(2) 11 “1”被描述为“一个1”countAndSay(3) 21 “11”被描述为“两个1”countAndSay(4) 1211 “21”被描述为“一个2、一个1”countAndSay(5) 111221 “1211”被描述为“一个1、一个2、两个1”
实现步骤
从第 1 项开始递归或迭代生成第 n 项。使用双指针或计数来对字符串进行“描述”即按连续字符的次数和字符本身生成新的字符串。
三、代码
class Solution {public String countAndSay(int n) {// 从第1项 1 开始构造逐步生成第n项String result 1;// 从第二项开始循环直到第n项for (int i 2; i n; i) {StringBuilder current new StringBuilder(); // 存储当前项int count 1; // 用于计数相同数字的次数// 遍历上一个字符串result描述该字符串for (int j 1; j result.length(); j) {if (result.charAt(j) result.charAt(j - 1)) {// 如果当前字符与前一个字符相同计数加1count;} else {// 如果不同生成描述并重置计数current.append(count).append(result.charAt(j - 1));count 1;}}// 处理最后一段字符的描述current.append(count).append(result.charAt(result.length() - 1));// 更新result为当前描述的字符串result current.toString();}return result; // 返回最终生成的第n项}
}四、复杂度分析
时间复杂度O(n * L)L 是字符串的平均长度。由于每一项的长度逐渐增长复杂度接近 O(n²)。空间复杂度O(L)其中 L 是当前生成的字符串的长度。我们只需要存储当前项和前一项因此空间使用较为高效。
