LeetCode/外观数列
2022/7/27 23:25:35
本文主要是介绍LeetCode/外观数列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给定一个正整数 n ,输出外观数列的第 n 项
「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述
1. 递归
判断相邻相等的方法每次只能处理上一个值
等价于每次比较上一个组的末位置与当前组的初始位置
最后一个值要额外处理
class Solution { public: string countAndSay(int n) { if(n==1) return "1";//递归边界 string s=countAndSay(n-1);//从上一层结果继续生成 string ans=""; int count=1;//初始值为1 for(int i=1;i<s.length();i++){ if(s[i]==s[i-1]) count++;//相等则计数加 else{ ans+=(to_string(count)+s[i-1]);//否则先输出前一个值 count=1;//重置计数 } } return ans+to_string(count)+s.back();//这里要补上最后一组字符 } };
2. 遍历
判断组头是否相等可以避免额外处理,统一操作
使用两个下标记录位置
class Solution { public: string countAndSay(int n) { string prev = "1"; for (int i = 2; i <= n; ++i) { string curr = "";//重置cur int start = 0;//当前组起始位置 int pos = 0;//当前组末位置 while (pos < prev.size()) {//遍历所有字符 while (pos < prev.size() && prev[pos] == prev[start]) pos++;//定位到不重复位置 curr += to_string(pos - start) + prev[start]; start = pos; } prev = curr;//更新pre } return prev; } };
这篇关于LeetCode/外观数列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升