当前位置: 首页> 教育> 就业 > 云采网采购平台_厦门网站设计公司找哪家_免费seo关键词优化排名_经典软文范例大全

云采网采购平台_厦门网站设计公司找哪家_免费seo关键词优化排名_经典软文范例大全

时间:2025/7/11 15:10:04来源:https://blog.csdn.net/2401_85548793/article/details/147098740 浏览次数:0次
云采网采购平台_厦门网站设计公司找哪家_免费seo关键词优化排名_经典软文范例大全

大家好,我是小卡皮巴拉

文章目录

目录

力扣题目:外观数列

题目描述

解题思路

问题理解

算法选择

具体思路

解题要点

完整代码(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. 初始化:将外观数列的第一个元素初始化为 "1",存储在字符串 ret 中。

  2. 迭代生成:进行 n - 1 次迭代,每次迭代对当前的 ret 进行行程长度编码。

    • 行程长度编码:使用双指针 left 和 right 遍历当前字符串 retleft 指针指向当前处理的字符,right 指针用于找到连续相同字符的末尾。当 right 指向的字符与 left 指向的字符相同时,right 指针右移。当 right 指向的字符与 left 指向的字符不同时,说明找到了一组连续相同的字符,其数量为 right - left。将该数量转换为字符串,并与该字符拼接,添加到临时字符串 tmp 中。然后更新 left 指针到 right 指针的位置,继续处理下一组相同字符。

    • 更新结果:一次行程长度编码完成后,将临时字符串 tmp 的结果更新到 ret 中,为下一次迭代做准备。

  3. 返回结果:经过 n - 1 次迭代后,ret 即为外观数列的第 n 个元素,返回 ret

解题要点

  1. 迭代过程:明确需要进行 n - 1 次迭代,每次迭代都对前一个结果进行行程长度编码。

  2. 双指针使用:使用双指针 left 和 right 来遍历字符串,方便统计连续相同字符的数量。

  3. 行程长度编码:正确将连续相同字符的数量和字符进行拼接,生成行程长度编码的结果。

完整代码(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;}
};

兄弟们共勉 !!! 

码字不易,求个三连

抱拳了兄弟们!

关键字:云采网采购平台_厦门网站设计公司找哪家_免费seo关键词优化排名_经典软文范例大全

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: