百度2013校园招聘笔试题解析

明天就要参加百度的校招笔试了，今天准备的时候在网上看到了去年百度的一道笔试题，思考了一下，记录一下结果

题目：写一个递归程序，求字符串中最长的重复字母数量。比如abbbccd返回3，abbc返回2。

分析：这个题目如果说使用非递归算法会比递归算法要好想一些。其实一个问题如果需要使用递归解决，最主要的一个问题就是如何将问题分解成递归式的。

拿这个题目来说，需要确定的就是每一步递归需要处理什么，一般最先想到的是每一次递归处理一个字符，但这样不能解决这个问题。正确的方法其实是每一步解决一个重复字母串，就像题目中给的例子 abbbccd，每次递归需要处理的字符分别为：a、bbb、cc、d，每次递归的结果为已经处理的字符串中的最长的重复字母数量。

语言表达能力有限，还是直接贴代码吧

#include <stdio.h>int maxCount(char *pc) {    int count = 1;    char c = *pc;    if (c == '\0') {        return 0;    }    char next = *(pc++);    while (next != '\0' && c == next) {        count ++;        next = *(pc++);    }    if (next == '\0') {        return count;    } else {        int n = maxCount(pc);        return n > count ? n : count;    }}int main() {    int res = maxCount("1223334444");    printf("%d\n", res);    return 0;}

1楼jinguol999昨天 22:43

递归真的很美呀n加个if(pc==NULL){return -1}n更鲁棒了

Re: gd9201298小时前

回复jinguol999n日。。。