LeetCode题目38：外观数列
原题描述
+
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221第一项是数字 1
描述前一项，这个数是 1 即 “一个 1 ”，记作 11
描述前一项，这个数是 11 即 “两个 1 ” ，记作 21
描述前一项，这个数是 21 即 “一个 2 一个 1 ” ，记作 1211
描述前一项，这个数是 1211 即 “一个 1 一个 2 两个 1 ” ，记作 111221
示例 1
输入: 1
输出: "1"
解释：这是一个基本样例。示例 2
输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组,
"2" 可以读作 "12"，也就是出现频次 = 1 而值 = 2；
类似 "1" 可以读作 "11"。
所以答案是 "12" 和 "11" 组合在一起，也就是 "1211"。原题链接：https://leetcode-cn.com/problems/count-and-say
思路解析
+
从题目描述就知道这是一个基于前次结果迭代的过程。
做统计时要注意，连续出现的数字要一次性统计完再生成结果。关于如何统计连续出现的数字，只需要两个首尾指针begin和end，并且不断后移end并统计次数即可。
我做这道题的时候竟然卡在了怎么把数字转字符串这件事上，想想真是太无聊了。
像这种简单的题目大概率不会出现在面试题中，就当做一个消遣吧~
C++参考代码
+
class Solution {
public:
string countAndSay(int n) {
string res = "1";
for (int i = 1; i < n; ++i) {
string next_res = "";
int begin = 0, end = 0;
while (end < res.size()) {
int count = 0;
while(res[end] == res[begin] && end < res.size()) {
++count;
++end;
}
int val = res[begin];
if (end < res.size()) begin = end;
next_res += count + '0';
next_res += val;
}
res = next_res;
}
return res;
}
};讲技术，也谈风月，更关注程序员的生活状况，欢迎联系二少投稿你感兴趣的话题。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-08-22，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读