The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...
Given an integer n, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
Analysis:1, 11, 21, 1211, 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, generate the nth sequence.
Note: The sequence of integers will be represented as a string.
No particular algorithms applied to this problem. Simply go through n rounds, wherein we calculate the time of each repeated characters and append to output string.
Code:
class Solution { public: string countAndSay(int n) { string sout; string s="1"; while(n-->1) { sout=helper(s); s=sout; } return s; } string helper(string s) { int count=0; char last=s[0]; string sout=""; for (int i=0; i<=s.length(); i++) { if (s[i]==last) count++; else { sout+=to_string(count)+s[i-1]; last=s[i]; count=1; } } return sout; } };
Version 우리카지노 4
ReplyDelete