友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
481. 神奇字符串
神奇字符串 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
提示：
-
1 <= n <= 105
思路分析
利用双指针，快指针指向虚位，等待生成元素；慢指针，表明要生成的元素数量。这里还有一个隐含条件： 1 和 2 是交替出现的。这样就可以根据前三个元素 122，向后逐渐增加字符串长度了。
可以使用 false 和 true 表示 1 和 2，这样可以更加节省空间。
|
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-09-05 22:12:46
*/
public int magicalString(int n) {
// 节省空间的解法：false 表示 1，true 表示 2
boolean[] s = new boolean[n + 2];
s[1] = false;
s[1] = s[2] = true;
boolean c = true;
for (int i = 2, j = 3; j < n; i++) {
c = !c;
s[j++] = c;
if (s[i]) {
s[j++] = c;
}
}
int result = 0;
for (int i = 0; i < n; i++) {
if (!s[i]) {
result++;
}
}
return result;
// 原始解法
// char[] s = new char[n + 2];
// s[0] = '1';
// s[1] = s[2] = '2';
// int c = 2;
// for (int i = 2, j = 3; j < n; i++) {
// c ^= 3; // 1^3=2, 2^3=1，这样就能在 1 和 2 之间转换
// s[j++] = (char) (c + '0');
// if (s[i] == (char) (2 + '0')) {
// s[j++] = (char) (c + '0');
// }
// }
// int result = 0;
// for (int i = 0; i < n; i++) {
// result += 2 - (s[i] - '0');
// }
// return result;
}