题目:
The count-and-say sequence is the sequence of integers beginning as follows: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.
代码:
class Solution {
public:
string countAndSay(int n) {
string tmp1 = "";
string tmp2 = "";
for ( size_t i = ; i < n; ++i )
{
int digit_count = ;
for ( size_t j = ; j < tmp1.size(); ++j )
{
if ( tmp1[j]==tmp1[j-] )
{
++digit_count;
}
else
{
tmp2 += digit_count+'';
tmp2 += tmp1[j-];
digit_count = ;
}
}
tmp2 += digit_count+'';
tmp2 += tmp1[tmp1.size()-];
tmp1 = tmp2;
tmp2 = "";
}
return tmp1;
}
};
tips:
这个题意不太好理解。
简单说就是:第n组字符串是第n-1组字符串的读法;读法的准则就是‘连续出现个数+数字’。
其余的就是处理一下边界case。
=======================================
第二次过这道题,对题意理解好了之后,代码一次AC。
class Solution {
public:
string countAndSay(int n) {
if (n<) return "";
string ret = "";
for ( int i=; i<n; ++i )
{
string tmp_ret = "";
int count_same_digit = ;
char curr_digit = ret[];
for ( int j=; j<ret.size(); ++j )
{
if ( ret[j]!=ret[j-] )
{
tmp_ret += string(,count_same_digit+'') + string(,curr_digit);
curr_digit = ret[j];
count_same_digit = ;
}
else
{
count_same_digit++;
}
}
tmp_ret += string(,count_same_digit+'') + string(,curr_digit);
ret = tmp_ret;
}
return ret;
}
};