题目

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

思路

实际上就是一个生成字符串问题，我们把初始字符串定义为’122’，从第二个2开始遍历字符串，后面可能会遇到’1’或者’2’

1.遇到1，向字符串末尾追加一个和当前字符串的最后一个字符不同的字符（即如果最后一个字符为’1’，添加上’2’；最后一个字符为’2’，添加上’1’）

2.遇到2，向字符串末尾追加两个和当前字符串的最后一个字符不同的字符（即如果最后一个字符为’1’，添加上’22’；最后一个字符为’2’，添加上’11’）

这里注意，只需要遍历到字符串长度到n的时候即可，最后在生成的字符串里统计1的数量返回即可。

题解

class Solution:
    def magicalString(self, n: int) -> int:
      # n<=3，直接返回1
        if n <= 3:
            return 1
        # 定义初始字符串和下标
        res, index = '122', 2
        # 遍历
        while len(res) < n:
          # 遇到1
            if res[index] == '1':
              # tmp为和最后一个字符不同的字符
                tmp = '2' if res[-1] == '1' else '1'
                res += tmp
            # 遇到2
            else:
              # tmp为和最后一个字符不同的字符
                tmp = '2' if res[-1] == '1' else '1'
                res+=  tmp + tmp
        # 统计1的个数并返回
        return res[:n].count('1')