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。· 从 i2 开始读 s[i] 得到下一组长度把 num当前交替字符重复写入然后翻转 num、i。因为 s 是自描述的且每组至少长度 1所以「读 s[i]」时 s[i] 一定已经被写出来了i 始终小于 j。Java 实现classSolution{publicintmagicalString(intn){if(n3)return1;// 1 / 12 / 122 都只有 1 个 1int[]snewint[n];s[0]1;s[1]2;s[2]2;inti2;// 当前组的长度来源s[i]intj3;// 下一个写入位置intnum1;// 下一个要生成的字符1 和 2 交替intres1;// 1 的计数初始 122 中只有 s[0]1while(jn){intcnts[i];// 本组长度for(intk0;kcntjn;k){s[j]num;if(num1)res;}num3-num;// 1 - 2 交替i;}returnres;}}执行过程示例n 6步骤 i s[i] num 追加后 s j res初始 2 - - 122 3 11 2 2 1 12211 5 32 3 1 2 122112 6 3结果 res 3即 “122112” 中有 3 个 ‘1’ ✓复杂度指标 复杂度 说明时间 O(n) 每个字符只写入一次i、j 单调递增空间 O(n) 需要数组保存前缀以便回读组长度常见坑n 3 需特判否则初始化 s[1]、s[2] 会数组越界。内层循环加 j n避免最后一组写越界。num 交替用 3 - num 比三元表达式更简洁。不能用「只维护长度不维护内容」的方式因为后续组的长度依赖 s 中间位置的字符必须存下来回读。如果面试要求减小常数可以用 byte[] 或 StringBuilder 替代 int[]逻辑完全一致。
