转载

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啦。。。以后想起来更好的方法会更新哒

正文到此结束
Loading...