卖萌的弱渣

I am stupid, I am hungry.

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, …

Example

  • 1 is read off as “one 1” or 11.
  • 11 is read off as “two 1s” or 21.
  • 21 is read off as “one 2, then one 1” or 1211.
  • Given an integer n, generate the nth sequence.

Note

The sequence of integers will be represented as a string.

Solution

(Count-and-Say.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution(object):
    def count(self,s):
        num = 1
        ret = ""
        for i,j in enumerate(s):
            if i+1 < len(s) and s[i] == s[i+1]:
                num += 1
            elif i+1 < len(s):
                ret = ret + str(num) + s[i]
                num = 1
        # last element
        ret = ret + str(num) + s[i]
        return ret
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        ret = "1"
        for i in range(1,n):
            ret = self.count(ret)
        return ret
if __name__ == "__main__":
    sol = Solution()
    sol.countAndSay(2)