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]。只统计前缀中的字符,不需要返回生成的字符串。

自建示例

前缀截断在一个分组内部:

输入:n = 10
输出:5
解释:前十个字符为 1221121221,其中字符 1 出现在第 1、4、5、7、10 个位置,共 5 次。

只取首字符:

输入:n = 1
输出:1
解释:魔法字符串的第一个字符就是 1。

用组长度指针自描述生成

魔法字符串的前几个字符固定为 122。其中一个指针指向“下一组应该有多长”,另一个变量记录下一组应填入的字符(在 1 和 2 之间交替)。每生成一组,就把指针处的数字作为组长度写入字符串,并把读取指针向后移动。

只需生成到第 n 位;写入最后一组时若超过 n,截断即可。计数器在写入字符 1 时同步增加,不必再次扫描前缀。

C++ 实现

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

        std::vector<int> 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)。