转载

leetcode刷题--Count and Say

题目：输入一个阶数n，输出一个该阶对应的字符串s。这个字符串由上一介输出的字符串处理得到。具体规则是：n=1时输出字符串1；n=2时，数上次字符串中的数值个数，因为上次字符串有1个1，所以输出11；n=3时，由于上次字符是11，有2个1，所以输出21；n=4时，由于上次字符串是21，有1个2和1个1，所以输出1211。依次类推。

这道题依然难度是easy，陷阱在于不是求不同数字字符出现的次数，而是求连续相同字符的出现次数。解题可以用递归的思路来写，不过我没修改过，不是尾递归的形式（python反正也没有尾递归优化）。

思路如下：

递归思路：当n＝1时返回字符串“1”，其他调用前一阶的返回字符串形成递归
求连续相同字符出现次数：基本是C语言的思路--设置计数器count和临时变量same，same存储当前计数的数字，count记录当前数字的重复次数。当当前计数的数字与same不同时更新结果字符串。更新same的值，count值归位。

+需要注意开头和结尾处的处理

代码如下：

class Solution:  # @param {integer} n  # @return {string}  def cands(self,n):   if n==1:    st="1"    return st   else:    st=self.cands(n-1)    count=1    same=''    se=''    for i in range(len(st)):     if same!=st[i]:      if same !='':       se+=str(count)       se+=same      same=st[i]      count=1     else:      count+=1    se+=str(count)    se+=same    return se  def countAndSay(self, n):   return self.cands(n)

ps:不要吐槽python写的像C啦。。。以后想起来更好的方法会更新哒

正文到此结束