0481. Magical String¶
题目信息¶
- 题号:
0481
- 难度:
Medium
- 主题:
只含 1 和 2 的序列、连续分组、组长度、自描述字符串
- 原题:
- 重点:
魔法字符串固定从
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)。