Skip to content

038 Count and Say

38. Count and Say

题目: https://leetcode.com/problems/count-and-say/

难度:

Easy

思路

  1. i代表字符下标，从0开始取值，也就是从第一个字符开始，因为要让i取到最后一个字符，并且后面还要进行i+1的操作，所以将原字符串随意加上一个‘*’字符防止溢出
  2. count代表此时已经连续相同的字符个数

  3. res代表最终输出的字符串

  4. 只要i下标对应的字符等于下一个字符，则sum和i都加1，无限循环

  5. 如果i下标对应的字符不等于下一个字符了，则res应该加上str(sum)和i下标对应的那个字符，并且i加1，sum复原回0
Examples of nth sequence

 1.     1
 2.     11
 3.     21
 4.     1211
 5.     111221 
 6.     312211
 7.     13112221
 8.     1113213211
 9.     31131211131221
 10.   13211311123113112211


解法1
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        if n == 1:
            return '1'
        s = self.countAndSay(n-1) + '*'
        res, count = '', 1
        for i in range(len(s)-1):
            if s[i] == s[i+1]:
                count += 1
            else:
                res += str(count) + str(s[i])
                count = 1
        return res

解法2
class Solution(object):
    def countAndSay(self, n):
        """
        :type n: int
        :rtype: str
        """
        res = '1'
        for i in range(n-1):
            res = ''.join([str(len(list(group))) + digit for digit, group in itertools.groupby(res)])
        return res

详见python进阶-ITERTOOLS模块小结

解法3
class Solution {
    public String countAndSay(int n) {
        if(n == 1){  
            return "1";  
        }  
        //递归调用，然后对字符串处理  
        String str = countAndSay(n-1) + "*";//为了str末尾的标记，方便循环读数  
        char[] c = str.toCharArray();  
        int count = 1;  
        String s = "";  
        for(int i = 0; i < c.length - 1;i++){  
            if(c[i] == c[i+1]){  
                count++;//计数增加  
            }else{  
                s = s + count + c[i];//上面的*标记这里方便统一处理  
                count = 1;//初始化  
            }  
        }  
        return s;

    }
}
回到顶部