Fork me on GitHub

leetcode之38. 报数

发表于 | 分类于
字数统计 420 字 | 阅读时长 2 分钟

题目描述：

报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1
2
3
4
5
6
> 1.     1
> 2.     11
> 3.     21
> 4.     1211
> 5.     111221
>

1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", “one 1" （"一个二" , "一个一") , 即 1211。

给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。

注意：整数顺序将表示为一个字符串。

示例 1:

1
2
3
> 输入: 1
> 输出: "1"
>

示例 2:

1
2
3
> 输入: 4
> 输出: "1211"
>

解题思路：

  1. 1
  2. 11
  3. 21
  4. 1211
  5. 111221
  6. 312211
  7. 13112221
  8. 1113213211
  9. 31131211121221
  10. 13211311123112112211
  11. 11131221133112132112212221
  12. 31131122212321121113122122113211
  13. 132113213211121312211231131122112221131221
  14. 1113122113121113122112111311222112132113212221322113112211
  15. 311311222113111231131122211231132132211211131221131211321113222113212221

思路一：

时间复杂度：$O(n)$, 空间复杂度：$O(n)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string countAndSay(int n) {
        if( n == 1) return "1";
        string prev = countAndSay(n - 1), res = "";
        
        for(char c : prev)  
        {
            if(res == "" || c != res.back())
            {
                res += "1";
                res += c;
            }
            else
                res[res.size() - 2]++;
        }
        
        return res;
    }
};

思路二：

时间复杂度：$O(n^2)$, 空间复杂度：$O(n)$.

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
class Solution {
public:
    string countAndSay(int n) {
        // 先设定一个result
        string result = "1";
        // temp做中间的缓存
        string temp = "";
        if(n == 1) return result;
        // 两层for循环
        for(int i = 0;i < n - 1;i++)
        {
            int count = 1;
            // 每次对result里面的数进行计算
            for(int j = 0; j < result.size();j++)
            {
                // 如果当前的数和下一个数相同，那么就count就加一
                if(result[j] == result[j + 1])
                {
                    count ++;
                }
                // 如果不相等，那么就将频率和字符加在一起
                else
                {
                    temp += to_string(count);
                    temp += result[j];
                    count = 1;
                }
            }
            // 把temp赋值给result
            result = temp;
            // temp为空
            temp = "";
        }
        return result;
    }
};