0481. Magical String ==================== 题目信息 -------- :题号: 0481 :难度: Medium :主题: 只含 1 和 2 的序列、连续分组、组长度、自描述字符串 :原题: `LeetCode 0481 `_ :重点: 魔法字符串固定从 ``122112...`` 开始、连续组长度序列等于字符串自身、只统计前 ``n`` 项中的 1 题目重述 -------- 魔法字符串 ``s`` 是一个只包含字符 ``'1'`` 和 ``'2'`` 的无限字符串。把 ``s`` 按连续相同字符分组后,各组长度依次组成的数字序列恰好仍是 ``s`` 自身。该字符串以 ``"1221121221221121122..."`` 开始。 给定正整数 ``n``,返回魔法字符串前 ``n`` 个字符中字符 ``'1'`` 的数量。``n`` 位于 ``[1, 10^5]``。只统计前缀中的字符,不需要返回生成的字符串。 自建示例 -------- 前缀截断在一个分组内部: .. code-block:: text 输入:n = 10 输出:5 解释:前十个字符为 1221121221,其中字符 1 出现在第 1、4、5、7、10 个位置,共 5 次。 只取首字符: .. code-block:: text 输入:n = 1 输出:1 解释:魔法字符串的第一个字符就是 1。 用组长度指针自描述生成 ---------------------- 魔法字符串的前几个字符固定为 ``122``。其中一个指针指向“下一组应该有多长”,另一个变量记录下一组应填入的字符(在 1 和 2 之间交替)。每生成一组,就把指针处的数字作为组长度写入字符串,并把读取指针向后移动。 只需生成到第 ``n`` 位;写入最后一组时若超过 ``n``,截断即可。计数器在写入字符 ``1`` 时同步增加,不必再次扫描前缀。 C++ 实现 -------- .. code-block:: cpp class Solution { public: int magicalString(int n) { if (n <= 3) return 1; std::vector magical(n + 2, 0); magical[0] = 1; magical[1] = 2; magical[2] = 2; int read = 2; int write = 3; int nextValue = 1; int ones = 1; while (write < n) { int repeat = magical[read++]; for (int count = 0; count < repeat && write < n; ++count) { magical[write++] = nextValue; if (nextValue == 1) ++ones; } nextValue = 3 - nextValue; } return ones; } }; 代码分析 -------- ``read`` 读取的不是待写字符,而是下一组长度;``nextValue`` 负责在相邻组之间切换,因此生成过程正好满足“组长度序列等于字符串本身”的定义。每个位置只写一次,时间复杂度为 ``O(n)``,额外空间复杂度为 ``O(n)``。