Problem
https://leetcode.com/problems/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"
Solution: Recursion + Simulation
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, 4 ms, 8.6 MB class Solution { public: string countAndSay(int n) { string ans = "1"; for (int i = 1; i < n; ++i) ans = say(ans); return ans; } private: string say(const string& n){ string ans; int s = 0, l = n.length(); for (int e = 1; e <= l; ++e) if (e == l || n[s] != n[e]) { int count = e - s; ans += '0' + count; ans += n[s]; s = e; } return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment