---

0481. 神奇字符串

• 标签：双指针、字符串
• 难度：中等

题目链接

• 0481. 神奇字符串 - 力扣

题目大意

描述：

神奇字符串 $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 \le n \le 10^{5}$。

示例：

• 示例 1：

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

• 示例 2：

输入：n = 1
输出：1

解题思路

思路 1：双指针模拟

这道题的关键在于理解神奇字符串的构造规律。

由于神奇字符串 $s$ 的特殊性质：将 $s$ 连续的出现次数进行分组，结果正好是 $s$ 自身。我们可以使用双指针来模拟这个过程：

• 使用指针 $i$ 表示当前需要重复的字符在 $s$ 中的位置，$s[i]$ 表示需要重复的次数。
• 使用指针 $j$ 表示当前要写入新字符的位置。
• 我们从 $s = "122"$ 开始，使用双指针逐步扩展字符串 $s$。
• 在每个位置，我们读取 $s[i]$ 的值（重复次数），然后在位置 $j$ 写入相应次数的字符。
• 交替写入 $'1'$ 和 $'2'$：如果当前写入的字符是 $'1'$，下一次写入 $'2'$；如果当前是 $'2'$，下一次写入 $'1'$。

算法步骤：

1. 初始化字符串 $s$ 为 "122"。
2. 初始化指针 $i = 2$（从第 $3$ 个位置开始，因为前 $3$ 个字符已经固定），$j = 3$（从第 $4$ 个位置开始写入）。
3. 初始化计数器 $count\_one$ 用于统计 $1$ 的个数。
4. 当 $j < n$ 时，重复以下步骤：
   • 读取 $s[i]$ 的值 $repeat$，表示需要重复的次数。
   • 根据当前字符交替写入 $repeat$ 次，更新 $count\_one$。
   • 将 $i$ 和 $j$ 指针向右移动。
5. 统计前 $n$ 个字符中 $1$ 的个数。

思路 1：代码

class Solution:
    def magicalString(self, n: int) -> int:
        # 初始化字符串
        s = "122"
        i = 2  # 读取位置
        j = 3  # 写入位置
        count_one = 1  # 统计 1 的个数，"122" 中有 1 个 1
        
        # 当前字符标志，True 表示当前应该是 '1'，False 表示当前应该是 '2'
        current_char = True
        
        # 扩展字符串直到长度达到 n
        while j < n:
            repeat = int(s[i])  # 读取需要重复的次数
            # 写入 repeat 次字符
            for _ in range(repeat):
                if j >= n:
                    break
                if current_char:
                    s += '1'
                    count_one += 1
                else:
                    s += '2'
                j += 1
            
            # 切换字符标志（交替写入 1 和 2）
            current_char = not current_char
            i += 1
        
        return count_one

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是给定的整数。我们需要生成长度为 $n$ 的神奇字符串。
• 空间复杂度：$O(n)$，需要存储长度为 $n$ 的字符串。