题目描述：
A magical string S consists of only '1' and '2' and obeys the following rules:
The string S is magical because concatenating the number of contiguous occurrences of characters '1' and '2' generates the string S itself.
The first few elements of string S is the following: S = "1221121221221121122……"
If we group the consecutive '1's and '2's in S, it will be:
1 22 11 2 1 22 1 22 11 2 11 22 ......
and the occurrences of '1's or '2's in each group are:
1 2 2 1 1 2 1 2 2 1 2 2 ......
You can see that the occurrence sequence above is the S itself.
Given an integer N as input, return the number of '1's in the first N number in the magical string S.
Note: N will not exceed 100,000.
Example 1:
Input: 6 Output: 3 Explanation: The first 6 elements of magical string S is "12211" and it contains three 1's, so return 3.
题目大意：
魔法字符串Ｓ只包含'1'和'2'并遵从以下规则：
字符串S由连续出现的'1'和'2'拼接而成，并可以由其本身生成。
S的起始部分元素为：S = "1221121221221121122……"
如果按照连续出现的'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'的个数。
注意：N不会超过100000
解题思路：
字符串模拟
令魔法字符串ms = '122'，维护指针p，初始令p = 2
若ms[p] == '1' 则向ms追加1个与ms末尾元素不同的字符
否则，向ms追加2个与ms末尾元素不同的字符
Python代码：
class Solution(object):
def magicalString(self, n):
"""
:type n: int
:rtype: int
"""
ms = '122'
p = 2
while len(ms) < n:
ms += str(3 - int(ms[-1])) * int(ms[p])
p += 1
return ms[:n].count('1')
本文链接：http://bookshadow.com/weblog/2017/01/08/leetcode-magical-string/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
