0481. 神奇字符串【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 模拟生成

1. 📝 题目描述

• leetcode

神奇字符串 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^5

2. 🎯 s.1 - 模拟生成

c

int magicalString(int n) {
    if (n == 0) return 0;
    if (n <= 3) return 1;
    int* s = (int*)malloc(sizeof(int) * (n + 2));
    s[0] = 1; s[1] = 2; s[2] = 2;
    int len = 3, i = 2;
    while (len < n) {
        int next = s[len - 1] == 1 ? 2 : 1;
        int count = s[i];
        for (int j = 0; j < count && len < n; j++) s[len++] = next;
        i++;
    }
    int res = 0;
    for (int k = 0; k < n; k++) if (s[k] == 1) res++;
    free(s);
    return res;
}

js

/**
 * @param {number} n
 * @return {number}
 */
var magicalString = function (n) {
  if (n === 0) return 0
  if (n <= 3) return 1
  const s = [1, 2, 2]
  let i = 2 // 指向当前组的长度
  while (s.length < n) {
    const next = s[s.length - 1] === 1 ? 2 : 1
    const count = s[i]
    for (let j = 0; j < count && s.length < n; j++) s.push(next)
    i++
  }
  let res = 0
  for (let k = 0; k < n; k++) if (s[k] === 1) res++
  return res
}

py

class Solution:
    def magicalString(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 3:
            return 1
        s = [1, 2, 2]
        i = 2
        while len(s) < n:
            nxt = 2 if s[-1] == 1 else 1
            s.extend([nxt] * s[i])
            i += 1
        return s[:n].count(1)

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

算法思路：

• 根据神奇字符串的自描述性质，用指针 $i$ 指向当前组的长度
• 交替生成 1 和 2，每次追加 $s[i]$ 个相同字符
• 统计前 $n$ 位中 1 的个数