图解LeetCode——481. 神奇字符串（难度：中等）

开发者 · 2024-9-7 11:19:50

一、标题

神奇字符串 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 的长度。
四、代码实现

图解LeetCode——481. 神奇字符串（难度：中等）

所属分类: 问答交流

新帖推荐: 30日

推荐作品