图解LeetCode——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 的数目。

二、示例

2.1> 示例 1：

【输入】n = 6
【输出】3
【解释】神奇字符串 s 的前 6 个元素是 “122112”，它包含三个 1，因此返回 3 。

2.2> 示例 2：

【输入】n = 1
【输出】1

提示：

• 1 <= n <= 10^5

三、解题思路

根据题目描述，我们可以采用双指针的方式来模拟创建这个“神奇字符串”。其中，p指针每次移动都是+1的，magic[p]表示第p组里有多少个元素。tail指针指向的是待赋值的元素位置。那么，我们先向magic数组中初始化magic[0]=1，表示第0组有1个元素，值为1。那么，由于每个组内的元素值是“1”和“2”交替出现的，那么就可以推断出下面每个组元素个数，以及元素的值了。具体请见下图所示：

问题：数字1和2如何相互转换

当某一位上的任意值a（0或1）与1执行按位异或操作时，具有“按位翻转”的作用。即：0翻转为1，1翻转为0。而当某一位上的任意值a（0或1）与0执行按位异或操作时，则会将a原样输出。具体如下所示：

0 ^ 1 = 1（0被按位翻转为1）
1 ^ 1 = 0（1被按位翻转为0）
0 ^ 0 = 0（0被原样输出）
1 ^ 0 = 1（1被原样输出）

当我们了解到了异或的按位翻转功能，就可以通过采用与3进行异或方式将数字1和2相互转换。

时间复杂度：O(n)，其中 n 为字符串 s 的长度。

四、代码实现

class Solution {
    public int magicalString(int n) {
        int[] magic = new int[n + 1]; // 用于存储神奇数字集合
        magic[0] = 1; // 初始化第1个元素为0
        int tail = 1, p = 1, result = 1, value = 1, count = 2;
        while (tail < n) {
            value = value ^ 3; // 确定第"p"组内元素的值"value"是多少。(通过与3异或，可以将1和2互换)
            while(count-- > 0 && tail < n) { // 循环创建第"p"组内的"count"个元素，每个元素的值都是"value"
                magic[tail++] = value;
                if (value == 1) result++; // 如果发现元素的值"value"是1，则将"result"加1
            }
            count = magic[++p]; // 创建完第"p"组所有元素之后，获得下一组(即："p+1")需要创建的数字个数"count"
        }
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o)/ ~ 「干货分享，每天更新」

最后编辑于 ： 2022.10.31 10:22:15 © 著作权归作者所有,转载或内容合作请联系作者