The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
1is read off as"one 1"or11.
11is read off as"two 1s"or21.
21is read off as"one 2, thenone 1"or1211.Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
题目大意:
n=1 返回1
n=2由于n=1的结果为1，有1个1，所以返回11
n=3由于n=2结果为11，有2个1，返回21
n=4由于n=3结果为21，有1个2和1个1，所以返回1211
给定n,以此类推
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public: string cal(string &s){ string ans = ""; int cnt =1; int len = s.length(); for (int i = 0; i < len; i++) { if (i + 1 < len && s[i] != s[i + 1]){ ans = ans + char(cnt+48) + s[i]; cnt = 1; } else if (i + 1 < len) cnt++; } ans = ans + char(cnt+48) + s[len-1]; return ans; } string countAndSay(int n) { string s = "1"; for (int i = 1; i < n; i++) s = cal(s); return s; } }; |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution: # @return a string def countAndSay(self, n): s='1' for i in range(1,n): s=self.cal(s) return s def cal(self,s): cnt=1 length=len(s) ans='' for i ,c in enumerate(s): if i+1 < length and s[i]!=s[i+1]: ans=ans+str(cnt)+c cnt=1 elif i+1 <length: cnt=cnt+1 ans=ans+str(cnt)+c return ans |
更多题解可以查看： https://www.hrwhisper.me/leetcode-algorithm-solution/
本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处：细语呢喃 > leetcode 38 Count and Say
本文地址：https://www.hrwhisper.me/leetcode-count-and-say/