力扣(LeetCode)481. 神奇字符串(C++)

一、环境说明

1. 本文是 LeetCode481. 神奇字符串。
2. 模拟。
3. 测试环境:Visual Studio 2019。

二、思路分析

模拟

给定一个神奇字符串。多神奇？设长度为$10$。看$1221121221$。每一组相同的数，用空格分开，数一下每一组数的个数:$1221121$，连起来是$1221121$。这$7$个数字，居然和原来字符串的前$7$位相同！这就是神奇的定义。

我们尝试构造神奇字符串

1. $i$指向第几组，$j$指向待构建的位置。
2. $size$是当前组待构造大小。
3. 第$i$组数和第$i-1$组肯定不同。

知道以上规律，开始写代码！
提示：当$n<4$，最多有$3$个数的字符串，我们$return1$即可。这是为了方便构造字符串，我们要初始化前$3$个数。

三、代码展示

模拟:

class Solution {
public:
    int magicalString(int n) {
        if (n < 4) return 1;
        string s(n, '0');
        int ans = 1;
        s[0] = '1', s[1] = '2', s[2] = '2';//前三个元素初始化
        for (int j = 3, i = 2; j < n;) {//遍历整个s。j待构造位置，i第几组。
            int size = s[i] - '0';//第i组的待构造大小。
            int num = s[j-1] - '0';//暂存上一组的数
            while (j < n && size>0) {//在s[j]处构造'3'-num。
                s[j] = '3'-num;//构造新数。和上一组的数不同即可。
                if ('1' == s[j]) ans++;//统计1的个数
                j++;//待构造位置后移
                size--;//待构造大小--
            }
            i++;//构造完成，进入下一组
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

四、博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

1. 时间复杂度:$O(n)$ ,$n$是$s$的长度。一次遍历$s$即可构造神奇字符串，一次遍历时间复杂度是$O(n)$。
2. 空间复杂度:$O(n)$,字符串s的空间复杂度是$O(n)$。