跳到主要内容

481.神奇字符串

· 阅读需 3 分钟

1、题干​

神奇字符串 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 <= 105

2、解题思路​

题目要求计算神奇字符串 s 的前 n 个数字中 1 的数目，只需要按照规则模拟构造神奇字符串，再计算 1 的数量即可。

构造过程借助双指针实现，快指针 i 逐步递增，慢指针 cur 根据其可消耗次数 count 决定是否递增，每次 i 递增做以下计算：

  • 若当前字符是 1，则最终结果累计一次
  • 计算出第 i+1 个字符，第 i+1 个字符只有两种情况，要么跟第 i 个字符相同，要么不同
    • 当前仅当慢指针 cur 对应的字符是 2 且 第 i-1 和 i 个字符不同时，第 i 和 i+1 个字符相同
    • 其他情况第 i 和 i+1 个字符不同
  • 可消耗次数 count 减 1
  • 若可消耗次数 count 次数为 0，那么慢指针 cur 加 1，count 赋值为慢指针指向的新数字

3、代码​

function magicalString(n: number): number {
    const nums = new Array(n).fill(1);
    let res = 0, cur = 0, count = 1;

    for (let i = 0; i < n; i++) {
        if (nums[i] === 1) res++;

        nums[i + 1] = nums[i] === 2 ? 1 : 2;
        if (nums[cur] === 2 && nums[i] !== nums[i - 1]) nums[i + 1] = nums[i];

        if (--count === 0) count = nums[++cur];
    }

    return res;
}

4、复杂度​

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

5、执行结果​

image.png