leetcode第37题--Count and Say

题目:(据说是facebook的面试题哦)

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.

题目好难理解,要不是看了别人的题目解释我真心不知道要想多久才知道它的意思。一开始我以为来一个数,将它表示为后面的形式就可以了。所以就写了个来一个数转换为读出的形式。然后自然是错了。

题目的意思是按照一定的规则出现数字,以字符串的形式。规定第一个是1,接下去就是按照前一个数的读法记录,所以第二个就是1个1,记录为11,那第三个就是对11的读法就是2个1,记录为21,第四个就是对21的读法,一个2一个1,记录为1211,一次类推估计应该知道什么意思了吧。Facebook出这样的题果然思维略叼啊。

leetcode把这题label为easy,题目都这么难理解起码medium啊哈哈。

在刚才错误的基础上,在加一个循环调用就可以了。即对 给定一个string后,输出它的读法 进行循环n次就得到n的答案了。如果n为零就输出“”。

class Solution {
public:
string getNext(string s)
{
if (s == "") return "1";
string ans = "";
int len = s.size(), cnt = 1; // 计数cnt初始为1,因为一旦出现一个数那至少是一次
for (int i = 0; i < len; i++)
{
if (i+1 < len && s[i+1] == s[i])
{
cnt++;continue;
}
ans += cnt + '0'; // 和下面的s[i]要分开来加,否则会先进行字符串相加再到ans中
ans += s[i];
cnt = 1; //记录后记得将cnt恢复为1
}
return ans;
}
string countAndSay(int n)
{
if (n == 0)
return "";
string ans = "";
for (int i = 0; i < n; ++i) // 重复找n次next的就可以了
ans = getNext(ans);
return ans;
}
};
上一篇:一个非常棒的html5框架-ionic


下一篇:iOS红马甲项目Bug总结(2)