Leetcode 481 Magical String

发表于 |

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.

分析：
龟龟!第二次在leetcode上写题解，beats 100%太骚了，而且血虐之后的
https://leetcode.com/problems/magical-string/discuss/139180/python-solution-78ms-beats-100%

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
s = [1,2,2]
index = 2
while len(s) < 100000:
	# according to the last element, we decide the value of 'val'
	val = 3 - s[-1]
	s.extend([val]*s[index])
	index += 1

class Solution(object):
    def magicalString(self, n):
        """
        :type n: int
        :rtype: int
        """
        return s[:n].count(1)

O(n) time, O(n) space
65 / 65 test cases passed.
difficulty: medium
Runtime: 78 ms, beats 100%