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

清疚 2023-10-07 20:53 6阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 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 <= 105

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

## 2.思路 ##

（1）双指针  
思路参考[本题官方题解][Link 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;
        }
    }

[Link 1]: https://leetcode.cn/problems/magical-string/solution/shen-qi-zi-fu-chuan-by-leetcode-solution-y5dg/