2022-10-31 481

leetcode 481 典型的双指针题目,
优化是，不需要存储字符串，直接用数字，避免转换
用前面的i指向的，生成j指向的，注意j-1 ，才是交替出现的原因。
因为一个数字出现了3次，就完蛋了，所以是交替出现。

class Solution:
    def magicalString(self, n: int) -> int:
        if n < 4:
            return 1
        s = [0] * n
        s[:3] = [1,2,2]
        res, i, j =1, 2, 3
        while j < n:
            cnt = s[i]
            num = 3 - s[j - 1]
            while cnt and j < n:
                s[j] = num
                if num == 1:
                    res += 1
                j += 1
                cnt -= 1
                
            i += 1

        return res