[LeetCode] 38. Count and Say 计数和读法
The count-and-say sequence is the sequence of integers with the first five terms as following:
1. 1
2. 11
3. 21
4. 1211
5. 111221
1
is read off as "one 1"
or 11
.11
is read off as "two 1s"
or 21
.21
is read off as "one 2
, then one 1"
or 1211
.
Given an integer n where 1 ≤ n ≤ 30, generate the nth term of the count-and-say sequence.
Note: Each term of the sequence of integers will be represented as a string.
Example 1:
Input: 1
Output: "1"
Example 2:
Input: 4
Output: "1211"
这道计数和读法问题还是第一次遇到,看似挺复杂,其实仔细一看,算法很简单,就是对于前一个数,找出相同元素的个数,把个数和该元素存到新的 string 里。代码如下:
class Solution {
public:
string countAndSay(int n) {
if (n <= ) return "";
string res = "";
while (--n) {
string cur = "";
for (int i = ; i < res.size(); ++i) {
int cnt = ;
while (i + < res.size() && res[i] == res[i + ]) {
++cnt;
++i;
}
cur += to_string(cnt) + res[i];
}
res = cur;
}
return res;
}
};
博主出于好奇打印出了前 12 个数字,发现一个很有意思的现象,不管打印到后面多少位,出现的数字只是由 1, 2 和3 组成,网上也有人发现了并分析了原因,参见这个帖子,前十二个数字如下:
Github 同步地址:
https://github.com/grandyang/leetcode/issues/38
类似题目:
参考资料:
https://leetcode.com/problems/count-and-say/
https://leetcode.com/problems/count-and-say/discuss/16000/Show-an-Answer-in-Java
https://leetcode.com/problems/count-and-say/discuss/16043/C%2B%2B-solution-easy-understand
LeetCode All in One 题目讲解汇总(持续更新中...)
最新文章
- ajax 跨域请求时url参数添加callback=?会实现跨域问题
- JVM内存管理------GC算法精解(复制算法与标记/整理算法)
- How can I exclude directories from grep -R?
- 设计模式-01-MVC
- Buy Tickets(线段树)
- 一群猴子排成一圈,按1,2,...n 编号,数到m只,踢出局,直到剩下最后一个猴子是大王
- 用Eclipse+ADT创建可运行项目,创建lib项目,引用一个lib项目
- WebBrowser自动点击链接 广告自动点击 Ads Auto Click
- Java实战之03Spring-01Spring概述
- Qt学习之路: 国际化(上)
- linux修改环境变量
- C语言函数调用约定
- Python collections模块总结
- B树,B+树,B*树
- Linux 命令行下导入导出 .sql 文件
- Testing - 软件测试知识梳理 - 理解测试
- Event IO Process
- [LeetCode] 103. Binary Tree Zigzag Level Order Traversal _ Medium tag: BFS
- The Gene of Bitizens
- DataTable 转换 DataSet