题目描述
这是 LeetCode 上的 481. 神奇字符串 ，难度为 中等。
Tag : 「模拟」、「构造」、「双指针」、「打表」
神奇字符串
s
仅由
'1'
和
'2'
组成，并需要遵守下面的规则：
- 神奇字符串
s
'1'
'2'
s
的前几个元素是
s = "1221121221221121122……"
。如果将
s
中连续的若干
1
和
2
进行分组，可以得到
"1 22 11 2 1 22 1 22 11 2 11 22 ......"
。每组中
1
或者
2
的出现次数分别是
"1 2 2 1 1 2 1 2 2 1 2 2 ......"
。上面的出现次数正是 s 自身。
给你一个整数
n
，返回在神奇字符串
s
的前
n
个数字中
1
的数目。
示例 1：
输入：n = 6
输出：3
解释：神奇字符串 s 的前 6 个元素是 “122112”，它包含三个 1，因此返回 3 。 示例 2：
输入：n = 1
输出：1 提示：
双指针 + 构造 + 打表
我们将相关的字符串分为三类：题目描述的神奇字符串
s
称为“原串”，对
s
进行连续段划分所得的串叫“划分串”，对划分串进行计数的串叫“计数串”。
解题的核心思路：由于划分串是对原串的划分，同时计数串又与原串相同，因此可得三类串均只有
1
和
2
两种数值。即可知划分串的每段长度只能是「长度为
1
」或「长度为
2
」，利用划分串的每段构造长度有限，我们可以通过「简单分情况讨论」的方式进行构造。
具体的，我们需要利用「原串和计数串的相同的性质」对
s
进行构造：不难发现计数串总是不长于原串，因此我们可以使用变量
i
来记录当前构造到原串位置，使用变量
j
来记录计数串对应到的实际位置。
不失一般性假设当前构造到
s
中的某一位为
last
，而计数串对应的实际位置为
t
，由于两者均只有
1
和
2
两种可能，我们可以对其进行简单的分情况讨论（可见代码注释）。
一些细节：由于神奇字符串起始字符固定，构造逻辑固定，因此神奇字符串唯一固定。
我们可以采取
代码块的方式进行打表预处理（static
中的 Java
代码块只会在类加载的过程执行一次，而 static
的测评机制是实例化多个 LC
对象来跑多个样例，但 Solution
类仍只会被加载一次，即 Solution
在多个样例测评中只会被执行一次。static
Java 代码：
class Solution {
static int N = 100010;
static int[] f = new int[N];
static {
StringBuilder sb = new StringBuilder();
sb.append("01"); // 首位多加一个 0 作为哨兵
for (int i = 1, j = 1, cnt = 0; i < N; j++) {
int last = sb.charAt(sb.length() - 1) - '0', t = sb.charAt(j) - '0';
if (last == 1) {
if (t == 1) {
// 当原串当前字符是 1，而计数串当前字符为 1
// 往后构造形成的原串只能是 12，原串指针后移一位
sb.append("2");
f[i] = ++cnt; i++;
} else {
// 当原串当前字符是 1，而计数串当前字符为 2
// 往后构造形成的原串只能是 112，此时同步更新 f[i + 1]，原串指针后移两位
sb.append("12");
f[i] = ++cnt; f[i + 1] = ++cnt; i += 2;
}
} else {
if (t == 1) {
// 当原串当前字符是 2，而计数串当前字符为 1
// 往后构造形成的原串只能是 21，原串指针后移一位
sb.append("1");
f[i] = cnt; i++;
} else {
// 当原串当前字符是 2，而计数串当前字符为 2
// 往后构造形成的原串只能是 221，原串指针后移两位
sb.append("21");
f[i] = f[i + 1] = cnt; i += 2;
}
}
}
}
public int magicalString(int n) {
return f[n];
}
} TypeScript 代码：
function magicalString(n: number): number {
let str = '01' // 首位多加一个 0 作为哨兵
const f = new Array<number>(n + 10).fill(0)
for (let i = 1, j = 1, cnt = 0; i <= n; j++) {
const last = str[str.length - 1], t = str[j]
if (last == '1') {
if (t == '1') {
// 当原串当前字符是 1，而计数串当前字符为 1
// 往后构造形成的原串只能是 12，原串指针后移一位
str += '2'
f[i] = ++cnt; i++
} else {
// 当原串当前字符是 1，而计数串当前字符为 2
// 往后构造形成的原串只能是 112，此时同步更新 f[i + 1]，原串指针后移两位
str += '12'
f[i] = ++cnt; f[i + 1] = ++cnt; i += 2
}
} else {
if (t == '1') {
// 当原串当前字符是 2，而计数串当前字符为 1
// 往后构造形成的原串只能是 21，原串指针后移一位
str += '1'
f[i] = cnt; i++
} else {
// 当原串当前字符是 2，而计数串当前字符为 2
// 往后构造形成的原串只能是 221，原串指针后移两位
str += '21'
f[i] = f[i + 1] = cnt; i += 2
}
}
}
return f[n]
} Python 代码：
class Solution:
def magicalString(self, n: int) -> int:
ss = '01' # 首位多加一个 0 作为哨兵
i, j, cnt = 1, 1, 0
f = [0] * (n + 10)
while i <= n:
last, t = ss[i], ss[j]
if last == '1':
if t == '1':
# 当原串当前字符是 1，而计数串当前字符为 1
# 往后构造形成的原串只能是 12，原串指针后移一位
ss += '2'
f[i], cnt, i = cnt + 1, cnt + 1, i + 1
else:
# 当原串当前字符是 1，而计数串当前字符为 2
# 往后构造形成的原串只能是 112，此时同步更新 f[i + 1]，原串指针后移两位
ss += '12'
f[i], f[i + 1], cnt, i = cnt + 1, cnt + 2, cnt + 2, i + 2
else:
if t == '1':
# 当原串当前字符是 2，而计数串当前字符为 1
# 往后构造形成的原串只能是 21，原串指针后移一位
ss += '1'
f[i], i = cnt, i + 1
else:
# 当原串当前字符是 2，而计数串当前字符为 2
# 往后构造形成的原串只能是 221，原串指针后移两位
ss += '21'
f[i], f[i + 1], i = cnt, cnt, i + 2
j += 1
return f[n] - 时间复杂度：，若将
static
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第
No.481
篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)