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)``。