问答题 2.  用递归的方法实现一个求字符串中连续出现相同字符的最大值,例如字符串“aaabbcc”中连续出现字符‘a’的最大值为3,字符串“abbc”中连续出现字符‘b’的最大值为2。
【正确答案】如果不要求采用递归的方法,那么算法的实现就非常简单,只需要在遍历字符串的时候定义两个额外的变量curMaxLen与maxLen,分别记录与当前遍历的字符重复的连续字符的个数和遍历到目前为止找到的最长的连续重复字符的个数。在遍历的时候,如果相邻的字符相等,那么执行curMaxLen+1;否则,更新最长连续重复字符的个数,即maxLen=max(curMaxLen,maxLen),由于碰到了新的字符,因此curMaxLen=1。
   题目要求用递归的方法来实现,通过对非递归方法进行分析可以知道,在遍历字符串的时候,curMaxLen与maxLen是最重要的两个变量,那么在进行递归调用的时候,通过传入两个额外的参数(curMaxLen与maxLen)就可以采用与非递归方法类似的方法来实现,实现代码如下:
   def getMaxDupChar(s,startIndex,curMaxLen,maxLen):
   #字符串遍历结束, 返回最长连续重复字符串的长度
   if startIndex==len(s)-1:
   return max(curMaxLen,maxLen)
   #如果两个连续的字符相等, 那么在递归调用的时候把当前最长串的长度加1
   if list(s)[startIndex]==list(s)[startIndex+1]:
   return getMaxDupChar(s,startIndex+1,curMaxLen+1,maxLen)
   #两个连续的子串不相等, 求出最长串max(curMaxLen, maxLen),
   #当前连续重复字符串的长度变为1
   else:
   return getMaxDupChar(s,startIndex+1,1,max(curMaxLen,maxLen))
   
   if __name__=="__main__":
   print "abbc的最长连续重复子串长度为: "+str(getMaxDupChar("abbc",0,1,1))
   print "aaabbcc的最长连续重复子串长度为:"+str(getMaxDupChar("aaabbcc",0,1,1))
   程序的运行结果为:
   abbc的最长连续重复子串长度为:2
   aaabbcc的最长连续重复子串长度为:3
   算法性能分析:
   由于这种方法对字符串进行了一次遍历,因此,算法的时间复杂度为O(N)。这种方法也没有申请额外的存储空间。
【答案解析】[考点] 如何统计字符串中连续的重复字符个数