0%

leetcode 38 Count and Say

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 _n_th sequence.

Note: The sequence of integers will be represented as a string. 题目地址:leetcode Count and Say

题目大意:

n=1 返回1

n=2由于n=1的结果为1,有1个1,所以返回11

n=3由于n=2结果为11,有2个1,返回21

n=4由于n=3结果为21,有1个2和1个1,所以返回1211

给定n,以此类推

C++

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
class Solution {
public:
string cal(string &s){
string ans = "";
int cnt =1;
int len = s.length();
for (int i = 0; i < len; i++)
{
if (i + 1 < len && s[i] != s[i + 1]){
ans = ans + char(cnt+48) + s[i];
cnt = 1;
}
else if (i + 1 < len)
cnt++;
}
ans = ans + char(cnt+48) + s[len-1];
return ans;
}
string countAndSay(int n) {
string s = "1";
for (int i = 1; i < n; i++)
s = cal(s);
return s;
}
};

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
# @return a string
def countAndSay(self, n):
s='1'
for i in range(1,n):
s=self.cal(s)
return s

def cal(self,s):
cnt=1
length=len(s)
ans=''
for i ,c in enumerate(s):
if i+1 < length and s[i]!=s[i+1]:
ans=ans+str(cnt)+c
cnt=1
elif i+1 <length:
cnt=cnt+1

ans=ans+str(cnt)+c
return ans

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~