LeetCode 481. 神奇字符串

题意理解

神奇字符串 s 只由 ‘1’ 和 ‘2’ 组成，且它的连续相同字符分组长度序列恰好等于 s 本身。例如：

s = "1221121221221121122..." 分组: 1 | 22 | 11 | 2 | 1 | 22 | 1 | 22 | 11 | 2 | ... 长度: 1 2 2 1 1 2 1 2 2 1 ...

长度序列 1,2,2,1,1,2,1,2,2,1,… 正好就是 s 本身 —— 这就是「自描述」的含义。

题目要求返回 s 前 n 个字符中 ‘1’ 的个数。

核心思路

用一个指针 i 表示「当前正在解释的组长度」在 s 中的下标，另一个指针 j 表示「下一个要写入的位置」，字符在 ‘1’ 和 ‘2’ 之间交替。

· 初始 s = “122”：第 0 组是 ‘1’（长度 s[0]=1），第 1 组是 ‘22’（长度 s[1]=2）。
· 从 i=2 开始，读 s[i] 得到下一组长度，把 num（当前交替字符）重复写入，然后翻转 num、i++。

因为 s 是自描述的，且每组至少长度 1，所以「读 s[i]」时 s[i] 一定已经被写出来了（i 始终小于 j）。

Java 实现

classSolution{publicintmagicalString(intn){if(n<=3)return1;// "1" / "12" / "122" 都只有 1 个 '1'int[]s=newint[n];s[0]=1;s[1]=2;s[2]=2;inti=2;// 当前组的长度来源：s[i]intj=3;// 下一个写入位置intnum=1;// 下一个要生成的字符（1 和 2 交替）intres=1;// '1' 的计数，初始 "122" 中只有 s[0]=1while(j<n){intcnt=s[i];// 本组长度for(intk=0;k<cnt&&j<n;k++){s[j++]=num;if(num==1)res++;}num=3-num;// 1 <-> 2 交替i++;}returnres;}}

执行过程示例（n = 6）

步骤 i s[i] num 追加后 s j res
初始 2 - - 122 3 1
1 2 2 1 12211 5 3
2 3 1 2 122112 6 3

结果 res = 3，即 “122112” 中有 3 个 ‘1’ ✓

复杂度

指标 复杂度 说明
时间 O(n) 每个字符只写入一次，i、j 单调递增
空间 O(n) 需要数组保存前缀以便回读组长度

常见坑

1. n <= 3 需特判：否则初始化 s[1]、s[2] 会数组越界。
2. 内层循环加 j < n：避免最后一组写越界。
3. num 交替用 3 - num 比三元表达式更简洁。
4. 不能用「只维护长度不维护内容」的方式，因为后续组的长度依赖 s 中间位置的字符，必须存下来回读。

如果面试要求减小常数，可以用 byte[] 或 StringBuilder 替代 int[]，逻辑完全一致。