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"
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 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | class Solution { public: string countAndSay(int n) { if(n<=0) return ""; string s = "1"; for(int i=2; i<=n; ++i){ int sz = s.size(); int start = 0, end = 0; string s1; while(start<sz){ while(end<sz && (end==0 || s[end]==s[start])) end++; int ct = end-start; s1 += char('0'+ct); s1 += s[start]; start = end; } s = s1; } return s; } }; class Solution { public: string countAndSay(int n) { string s = "1"; for(int i=2; i<=n; ++i) { string tmp; int cnt = 0; char c; for(int j=0; j<s.size(); ++j) { if(cnt==0){//j==0 c = s[j]; }else if(s[j]!=s[j-1]){ tmp += to_string(cnt) + c; cnt = 0; c = s[j]; } cnt++; } if(cnt) tmp += to_string(cnt) + c; s = tmp; } return s; } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | class Solution { public String countAndSay(int n) { if(n==1) return "1"; String prev = countAndSay(n-1); StringBuilder cur = new StringBuilder(); int i = 0, sz = prev.length(); while(i<sz){ char c = prev.charAt(i++); int count = 1; while(i<sz && prev.charAt(i)==c){ count++; i++; } cur.append(count); cur.append(c); } return cur.toString(); } } |
No comments:
Post a Comment