Leetcode 481. 神奇字符串

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

我的想法：
1.先研究下这个神奇字符串s，12轮换着来。
12
12
1对应有1个1，那么2就会对应有2个2

122
12
那这样的话第三位也是2。

12211
122
第三位的2就会对应2个1，那么四五位也出来了就是1。

12211
12211

第四位的1就会对应个2，第五位的1就对应1。

122112
12211

1221121
12211

以此类推。
那就想，s 初始为 122，再引进个数组，让它跟 s 同步增加。遍历数组的值，判断 s 之后是加几个 1 加几个 2 。最后再输出 s 中前 n 个数中有多少个 1 就行。

class Solution:
    def magicalString(self, n: int) -> int:
        s = "122"
        newlist = list(s)
        i = 2
        while i < n:
            if s[-1] == "2": # 如果s最后一位是1，就加2
                s += "1" * int(newlist[i]) # newlist[i]为对应的个数
                newlist.extend(["1"] * int(newlist[i]))
            elif s[-1] == "1":
                s += "2" * int(newlist[i])
                newlist.extend(["2"] * int(newlist[i]))
            i += 1
        return s[:n].count("1")
1
2
3
4
5
6
7
8
9
10
11
12
13
14

后来再一想，那就没必要引进新的数组了，直接用 s 就好了。

class Solution:
    def magicalString(self, n: int) -> int:
        s = "122"
        i = 2
        while i < n:
            if s[-1] == "2":
                s += "1" * int(s[i])
            elif s[-1] == "1":
                s += "2" * int(s[i])
            i += 1
        return s[:n].count("1")
1
2
3
4
5
6
7
8
9
10
11

粘几个其他人的题解：
官方的双指针
【宫水三叶】双指针构造打表
【爪哇缪斯】图解LeetCode