23道常见的面试算法题

1目录1求一个集合中的连续串，使得这个连续串中各个数相加的和最大.............................................12求一个集合中的连续串，使得这个连续串中各个数相加的和最小.............................................23动态规划求组合.................................................................................................................................34寻找发贴“水王”................................................................................................................................45求一个字符串中最长的重复子串，'0000……'不算在内...........................................................66求两个字符串的最长公共子串.........................................................................................................87读一组整数到VECTOR对象，计算并输出每对相邻元素的和。如果读入元素个数为奇数，则提示用户最后一个元素没有求和，并输出其值。然后修改程序：头尾元素两两配对（第一个和最后一个，第二个和倒数第二个，以此类推），计算每对元素的和，并输出。........................98整数转化为字符串...........................................................................................................................129字符串转化为整数...........................................................................................................................1310转换字符串格式为：原来字符串里的字符+该字条连续出现的个数，例如字符串：1233422222转化为1121324125（1出现1次，2出现1次，3出现2次……）...1411将一句话里的单词进行倒置，标点符号不倒换。比如“ICOMEFROMBEIJING.”“BEIJING.FROMCOMEI”.......................................................................................................1512二叉树根结点为ROOT,用递归法把二叉树的叶子结点按从左到右的顺序连成一个单链表................................................................................................................................................................1713连续正整数之和............................................................................................................................1714文件中有一组整数，要求排序后输出到另一个文件中.............................................................1915小猪吃米........................................................................................................................................2116在一个数组中存在着新数组，求出新数组的长度。.................................................................2317写函数找出一个字符串中出现频率最高的字符（如果最高频率相同的有多个字符，取最先遇见的那个字符）................................................................................................................................2418十三个人围成一个圈，从第一个人开始顺序报号1、2、3。凡是报到“3”者退出圈子，请找出最后留在圈子中的人原来的序号................................................................................................2619已知N个人（以编号1，2，3...N分别表示）围坐在一张圆桌周围。从编号为K的人开始报数，数到M的那个人出列；他的下一个人又从1开始报数，数到M的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列................................................................................2820十进制正数或负数转化为二进制................................................................................................3121将阿拉伯数字转化为中文数字，如12“一十二”.................................................................3222大数存储，求100的阶乘........................................................................................................3523在一个字符串中找到第一个只出现一次的字符。如“ABACCDEFF”，输出B。...............3611求一个集合中的连续串，使得这个连续串中各个数相加的和最大#includestdio.hintgetmax(inta[],intn,int*begin,int*end);intomain(void){inta[]={-1,-2,-3,100,-4,-5,6,-7,9,200};intbegin;intend;intsum;sum=getmax(a,10,&begin,&end);printf(Themaximalsumis%d\n,sum);printf(Thebeginindexis%d,theendindexis%d\n,begin,end);return0;}/*++算法:从第一个数出发，向右叠加，将他们的和累加于sum，只要和大于零，就继续。期间，保存这些和值中的最大值为max。如果sum小于零，则从sum小于零的后一个重新计算。--*/intgetmax(int*a,intn,int*begin,int*end){intmax=a[0];intsum=a[0];inttempbegin=0;*begin=0;*end=0;for(inti=1;in;i++){if(sum0){sum+=a[i];}else{tempbegin=i;sum=a[i];}2if(max=sum){max=sum;*begin=tempbegin;*end=i;}}returnmax;}2求一个集合中的连续串，使得这个连续串中各个数相加的和最小#includestdio.hintgetmin(inta[],intn,int*begin,int*end);intmain(void){//测试数组全部通过测试//inta[]={8,9,-3,-10,7,0,8,-12,9,8,-1,-2,9};//inta[]={1,2,3,4,5};//inta[]={-1,-2,-3,-5,-4};//inta[]={-1,100,-1000,100,-1};//inta[]={1,1,1,1,1};//inta[]={-1,-1,-1,-1,-1};//inta[]={1,-1,1,-1};//inta[]={8,9,-3,-10,7,0,8,-12,9,8,-1,-2,9};inta[]={8,9,-3,-10,7,-5,2,-12,9,8,-1,-2,9};intbegin;intend;intsum;intk=sizeof(a)/sizeof(int);sum=getmin(a,k,&begin,&end);printf(Theminimumsumis%d\n,sum);printf(Thebeginindexis%d,theendindexis%d\n,begin,end);return0;}intgetmin(int*a,intn,int*begin,int*end){intmin=a[0];3intsum=a[0];inttempbegin=0;*begin=0;*end=0;for(inti=1;in;i++){if(sum0){sum=sum+a[i];}else{tempbegin=i;sum=a[i];}if(sum=min){min=sum;*begin=tempbegin;*end=i;}}returnmin;}3动态规划求组合/*++++++++++++++++++++++++++++++++++++++++++++++思想：C(n,k)=C(n-1,k-1)+C(n-1,k)利用动态规划法，用一个二维数组把前面算出的组合数保存起来，这样就不用重复对一个小的组合数算很多次++++++++++++++++++++++++++++++++++++++++++++++*/#includeiostreamusingnamespacestd;constintN=6;constintK=3;inta[N+1][K+1];//N+1行，K+1列的存储4intmin(intx,inty){returnxy?x:y;}intCom(intn,intk){for(inti=0;i=n;++i){for(intj=0;j=min(i,k);++j){if(j==0||j==i)//每行第0列(最左边，C(n,0)=1，主对角线元素也为1){a[i][j]=1;}else{a[i][j]=a[i-1][j-1]+a[i-1][j];//根据递推式}}}returna[n][k];}voidmain(){coutThecombinationvalueof(6,3)isCom(N,K)endl;}4寻找发贴“水王”1）题目一个论坛中有一大“水王”，他不但喜欢发帖，还会回复其他ID发的每个帖子。该“水王”发帖数目超过了总数的一半。如果你有一个当前论坛所有帖子（包括回帖）的列表，其中帖子作者的ID也在表中，你能快速找出这个传说中的“水王”吗？2）分析5如果每次删除两个不同的ID（不管是否包含“水王”的ID），那么，在剩下的ID列表中，“水王”ID出现的次数仍然超过总数的