Fork me on GitHub
0%

【LeetCode】38.count-and-say

题目描述

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.

解题思路

1:“1”
2:一个“1”->”11”
3: 两个“1”->”21”
4: 一个“2”,一个“1”->”1211”
5: 一个“1”,一个“2”,两个“1”->”111221”
6: 3个“1”,两个“2”,一个“1”->”312211”
。。。
思路就是每个数字把前一个数字的表达式数出来

#

因为Python对字符串的处理比较方便,这里先实现了Python的递归方法:

38.count-and-say.pylink
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
class Solution:
def countAndSay(self, n):
"""
:type n: int
:rtype: str
"""
result = "1"
for i in range(1, n):
result = self.getNext(result)
return result

def getNext(self, last):
result = str()
count = 1
i = 0
while i < len(last):
# for i in range(len(last), 1):
if i == (len(last)-1):
result = result+str(count)+last[i]
break
while last[i] == last[i+1]:
count += 1
i += 1
if(i+1 == len(last)):
break
result = result+str(count)+last[i]
count = 1
i += 1
return result


test = Solution().countAndSay(2)
print(test)

C++的实现:

38.count-and-say.cpplink
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
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <string>
using namespace std;
class Solution
{
public:
string countAndSay(int n)
{
if (n == 0)
return "";

string res = "1";
for (int i = 1; i < n; i++)
{
res = getNext(res);
}
// int myint = stoi();
return res;
}

private:
string getNext(string last)
{
string result = "";
int count = 1;
for (int i = 0; i < last.size(); i++)
{
if (i == last.length() - 1)
{
result.append(to_string(count)) += last.at(i);
break;
}
while (last.at(i) == last.at(i + 1))
{
count++;
i++;
if (i + 1 == last.length())
break;
}
result.append(to_string(count)) += last.at(i);
count = 1;
}
return result;
}
};

int main(int argc, char const *argv[])
{
Solution solu;
int test = 4;
string res = solu.countAndSay(test);
cout << res << endl;
return 0;
}

不过最终有意思的是,同样的思路,Python花费64ms,C++花费了4ms。

打赏一次,年薪百万.