题目描述

一个有魔力的字符串 S 仅包含 '1' 和 '2' 并且遵循以下规则：

字符串 S 是有魔力的因为连接连续 '1' 和 '2' 出现次数可以构成 S 本身。

S 的前几个元素如下： S = "1221121221221121122……"

如果我们将 S 中连续的 '1' 和 '2' 分组，将会得到

1 22 11 2 1 22 1 22 11 2 11 22 ......

每组 '1' 和 '2' 的出现次数为：

1 2 2 1 1 2 1 2 2 1 2 2 ......

可以看到出现次数的序列就是 S 本身。

给定整数 N 作为输入，返回 S 前 N 个元素中 '1' 的个数。

样例

输入：6
输出：3
解释：S 的前 6 个元素为 "122112" ，包含 3 个 '1'，所以返回 3。

说明

• N 不超过 100000。

算法

(模拟) $O(n)$

1. 特判 n == 0 和 n <= 3 的情况，分别返回 0 和 1。
2. 将前三个字符 122 加入数组中，每次按照数组前边给定的数量，添加一组新的字符。
3. 例如，接下来按照第三个元素 2，需要加入两个字符，上次加入的是 2，那么这次新加入的字符应该是 1；此时数组为 12211，然后按照第四个元素 1，需要加入一个字符，上次加入的是 1，那么这次新加入的字符应该是 2。依次类推，直到长度达到 n。

时间复杂度

• 直接构造长度为 $n$ 的数字串，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储当前的数字串。

C++ 代码

class Solution {
public:
    int magicalString(int n) {
        if (n == 0) return 0;
        if (n <= 3) return 1;

        vector<int> vec;
        vec.push_back(1);
        vec.push_back(2);
        vec.push_back(2);

        int x = 1, num = 2, p = 2, i = 3, ans = 1;
        while (i < n) {
            for (int j = 0; j < num; j++)
                vec.push_back(x);

            if (x == 1)
                ans += min(num, n - i);

            x = 3 - x;
            i += num;
            num = vec[++p];
        }

        return ans;
    }
};