alexz
算法

Magical String

  • 481
  • Medium
约 8 分钟

我们将题目拆分为两个部分：

  • magical string -> s
  • 分组 -> group

根据题面可以得出：

  • s 只能有 1 或者 2。
  • 1 或 2 重复的次数不超过2。

所有的 s 前 3 位一定是 122：

group 当前是 [1, 2]；s 当前是 122。

我们引入两个指针：

  • read 指向 s 的当前位置 主指针(慢指针)
  • write 指向 group 的当前位置 从指针(快指针)

大概的逻辑是：

  • read 每次循环只 +1
  • write 每次循环往 s 追加 count = s[read] 个字符
  • 追加的字符和当前末尾相反，1 接 2，2 接 1
  • 可以理解是自己在追加自己，同时自己也在读取自己

初始时 read = 3，write = 4。s 是 122，末尾是 2，所以先接 1。

开始生成 s:

input n

s = "122"
read = 3
write = 4

while write <= n {
  count = s[read]
  // 为了避免出现连数的情况 `111111` 或 `222222`
  // 数字必然要和末尾相反
  v = 3 - s[write - 1]
  // 主指针读到几，从指针就追加几个数字
  for i in 0..count {
    s[write] = v
    write++
  }
  read++
}

代码如下

function magicalString(n) {
  const s = [1, 2, 2]
  for (let i = 2; s.length < n; i++) {
    const v = 3 - s[s.length - 1]
    for (let k = 0; k < s[i] && s.length < n; k++) s.push(v)
  }
  let ones = 0
  for (let i = 0; i < n; i++) if (s[i] === 1) ones++
  return ones
}