LeetCode_双指针_中等_481.神奇字符串

1.题目

神奇字符串 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 <= 10⁵

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/magical-string

2.思路

（1）双指针
思路参考本题官方题解，具体细节见下方代码中的注释。

3.代码实现（Java）

//思路1————双指针
class Solution {
    public int magicalString(int n) {
        int res = 1;
        if (n < 4) {
            return res;
        }
        //用字符数组 chs 来存储神奇字符串中的每一个字符
        char[] chs = new char[n];
        //初始化 chs
        chs[0] = '1';
        chs[1] = '2';
        chs[2] = '2';
        int i = 2;
        //从下标为 3 的位置开始构造
        int j = 3;
        //一边构造长度为 n 的神奇字符串，一边统计前 n 个数字中 1 的数目
        while (j < n) {
        	//获取要构造的数字的数目 cnt
            int cnt = chs[i] - '0';
            //相邻组中的数字一定不相同，所以可以通过 j 的前一个位置的数来判断当前需要构造的组中的数字 num
            int num = 3 - (chs[j - 1] - '0');
            //构造 cnt 个数字 'num'
            while (cnt > 0 && j < n) {
                chs[j] = (char) ('0' + num);
                //如果当前要构造的字符是 '1'，那么 res++
                if (num == 1) {
                    res++;
                }
                j++;
                cnt--;
            }
            i++;
        }
        return res;
    }
}
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