481.神奇字符串
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:
1 | 输入:n = 6 |
Solution
根据题意,我们可以把 s
看成是由「111 组」和「222 组」交替组成的,重点在于每组内的数字是一个还是两个,这可以从 s
自身上知道。
1 | class Solution { |