|
26.左旋转字符串 题目： 定义字符串的左旋转操作：把字符串前面的若干个字符移动到字符串的尾部。 如把字符串abcdef 左旋转2 位得到字符串cdefab。请实现字符串左旋转的函数。 要求时间对长度为n 的字符串操作的复杂度为O(n)，辅助内存为O(1)。 解答： 算法如下：fedcba->cdefab 27.跳台阶问题 题目：一个台阶总共有n 级，如果一次可以跳1 级，也可以跳2 级。 求总共有多少总跳法，并分析算法的时间复杂度。 f(n) = f(n-1)+f(n-2) 28.整数的二进制表示中1 的个数 题目：输入一个整数，求该整数的二进制表达中有多少个1。 例如输入10，由于其二进制表示为1010，有两个1，因此输出2。 解决这个问题的第一想法是一位一位的观察，判断是否为1，是则计数器加一，否则跳到下一位，于是很容易有这样的程序。 ?
或者和其等价的位运算版本： ?
这样的方法复杂度为二进制的位数，即 可以考虑每次找到从最低位开始遇到的第一个1，计数，再把它清零，清零的位运算操作是与一个零，但是在有1的这一位与零的操作要同时不影响未统计过的位数和已经统计过的位数，于是可以有这样一个操作 n&(n-1) ，这个操作对比当前操作位高的位没有影响，对低位则完全清零。拿6（110）来做例子，第一次 110&101=100，这次操作成功的把从低位起第一个1消掉了，同时计数器加1，第二次100&011=000，同理又统计了高位的一个1，此时n已变为0，不需要再继续了，于是110中有2个1。 代码如下： ?
这几个方法虽然也用到了位运算，但是并没有体现其神奇之处，下面这个版本则彰显位运算的强大能力，若不告诉这个函数的功能，一般一眼看上去是想不到这是做什么的，这也是wikipedia上给出的计算hamming_weight方法。 ?
没有循环，5个位运算语句，一次搞定。 比如这个例子，143的二进制表示是10001111，这里只有8位，高位的0怎么进行与的位运算也是0，所以只考虑低位的运算，按照这个算法走一次 +---+---+---+---+---+---+---+---+ | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | <---143 +---+---+---+---+---+---+---+---+ | 0 1 | 0 0 | 1 0 | 1 0 | <---第一次运算后 +-------+-------+-------+-------+ | 0 0 0 1 | 0 1 0 0 | <---第二次运算后 +---------------+---------------+ | 0 0 0 0 0 1 0 1 | <---第三次运算后，得数为5 +-------------------------------+ 这里运用了分治的思想，先计算每对相邻的2位中有几个1，再计算每相邻的4位中有几个1，下来8位，16位，32位，因为2^5＝32，所以对于32位的机器，5条位运算语句就够了。 像这里第二行第一个格子中，01就表示前两位有1个1，00表示下来的两位中没有1，其实同理。再下来01+00=0001表示前四位中有1个1，同样的10+10=0100表示低四位中有4个1，最后一步0001+0100=00000101表示整个8位中有5个1。 29.栈的push、pop 序列 题目：输入两个整数序列。其中一个序列表示栈的push 顺序， 判断另一个序列有没有可能是对应的pop 顺序。 为了简单起见，我们假设push 序列的任意两个整数都是不相等的。 比如输入的push 序列是1、2、3、4、5，那么4、5、3、2、1 就有可能是一个pop 系列。 30.在从1 到n 的正数中1 出现的次数 题目：输入一个整数n，求从1 到n 这n 个整数的十进制表示中1 出现的次数。 分析：把该正整数表示为十进制的字符串：an-1an-2…a0，其中an-1为最高位，a0为最低位(个位)，按最高位、最低位、中间位来分别分析其中1出现的次数：
否则，an-1 > 1，则为1xn-2…x0，其中(xn-2…x0)为任意(n-1)位整数，累计10n-1个；
否则a0 >= 1，则为bn-1…b11，且 0 <= 整数(bn-2…b0) <= 整数(an-1…a1)，累计 (an-1…a1)+1个；
如果ai == 1，则除了ai == 0的情形外，还有一种情形：an-1…ai+11ci-1…c0，且0 <= (ci-1…c0) <= ai-1…a0，有(ai-1…a0)+1个，累计：(an-1…ai+1)*10i+(ai-1…a0)+1，即(an-1…ai+1ai-1…a0)+1个； 否则，ai > 1，则为bn-1…bi+11xi-1…x0，且 0 <= 整数(bn-1…bi+1) <= 整数(an-1…ai+1)，(xi-1…x0)为任意i位数，累计 ((an-1…ai+1)+1)*10i个； 31.华为面试题： 一类似于蜂窝的结构的图，进行搜索最短路径（要求5 分钟） 迪杰斯特拉算法 32. 有两个序列a,b，大小都为n,序列元素的值任意整数，无序； 要求：通过交换a,b 中的元素，使[序列a 元素的和]与[序列b 元素的和]之间的差最小。 例如: var a=[100,99,98,1,2, 3]; var b=[1, 2, 3, 4,5,40]; 当前数组a和数组b的和之差为 A = sum(a) - sum(b) a的第i个元素和b的第j个元素交换后，a和b的和之差为 A' = sum(a) - a + b[j] - （sum(b) - b[j] + a) = sum(a) - sum(b) - 2 (a - b[j]) = A - 2 (a - b[j]) 设x = a - b[j] |A| - |A'| = |A| - |A-2x| |A'|= |A-2x| 假设A > 0, 当x 在 (0,A)之间时，做这样的交换才能使得交换后的a和b的和之差变小，x越接近A/2效果越好, 如果找不到在(0,A)之间的x，则当前的a和b就是答案。 所以算法大概如下： 在a和b中寻找使得x在(0,A)之间并且最接近A/2的i和j，交换相应的i和j元素，重新计算A后，重复前面的步骤直至找不到(0,A)之间的x为止。 33. 实现一个挺高级的字符匹配算法： 给一串很长字符串，要求找到符合要求的字符串，例如目的串：123 1******3***2 ,12*****3 这些都要找出来 其实就是类似一些和谐系统。。。。。 简单哈希 34. 实现一个队列。 队列的应用场景为： 一个生产者线程将int 类型的数入列，一个消费者线程将int 类型的数出列 35. 求一个矩阵中最大的二维矩阵(元素和最大).如: 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是: 4 5 5 3 要求:(1)写出算法;(2)分析时间复杂度;(3)用C 写出关键代码 转化为求子数组和的最大值 分析：先求解一维数组最大和，再求解二维。 假设最大子矩阵的结果为从第r行到k行、从第i列到j列的子矩阵， 如下所示(ari表示a[r],假设数组下标从1开始)： | a11 …… a1i ……a1j ……a1n | | a21 …… a2i ……a2j ……a2n | ..... | ar1 …… ari ……arj ……arn | 第r行 . . . .......... | V | ak1 …… aki ……akj ……akn | 第k行 . . . ..... | an1 …… ani ……anj ……ann | 那么我们将从第r行到第k行的每一行中相同列的加起来，可以得到一个一维数组如下： #include <iostream>(ar1+……+ak1, ar2+……+ak2, ……,arn+……+akn) 由此我们可以看出最后所求的就是此一维数组的最大子断和问题。 using namespace std; struct Point { short int x; short int y; }; //求一维数组的最大和 int getMaxSumInArray(int data[], int nSize, int& start, int& end) { int sum = data[0]; int maxSum = data[0]; for( int i=1; i<nSize; i++) { if(sum>0) sum+=data; else { sum = data; start = i; end = i; } if(sum>maxSum) { maxSum = sum; end = i; } } return maxSum; } //二维 void getMaxSumInMartrix(int data[100][100], int m, int n) { int* rowArray = new int[n]; int maxSum = data[0][0]; int start = 0, end = 0; Point leftTop = {0,0},rightBottom = {0,0}; // i代表从第几行开始加 for(int i=0; i<m; i++) { //j代表加到第几行结束 for(int j=i; j<m; j++) { memset(rowArray,0,sizeof(int)*n); //从第i行加到第j行 for(int k=0; k<n; k++) { for( int t=i; t<=j; t++) rowArray[k]+=data[t][k]; } int sum = getMaxSumInArray(rowArray,n,start,end); if(sum>maxSum) { maxSum = sum; leftTop.x = i; leftTop.y = start; rightBottom.x = j; rightBottom.y = end; } } } cout<<"最大和为"<<maxSum<<endl; cout<<"起始位置为("<<leftTop.x<<","<<leftTop.y<<")"<<endl; cout<<"结束位置为("<<rightBottom.x<<","<<rightBottom.y<<")"<<endl; } int main() { int data[100][100]; int m,n; cin>>m; cin>>n; for( int i=0; i<m; i++) for( int j=0; j<n; j++) cin>>data[j]; getMaxSumInMartrix(data,m,n); return 0; } 谷歌笔试： n 支队伍比赛，分别编号为0，1，2。。。。n-1，已知它们之间的实力对比关系， 存储在一个二维数组w[n][n]中，w[j] 的值代表编号为i，j 的队伍中更强的一支。 所以w[j]=i 或者j，现在给出它们的出场顺序，并存储在数组order[n]中， 比如order[n] = {4,3,5,8,1......}，那么第一轮比赛就是4 对3， 5 对8。....... 胜者晋级，败者淘汰，同一轮淘汰的所有队伍排名不再细分，即可以随便排， 下一轮由上一轮的胜者按照顺序，再依次两两比，比如可能是4 对5,直至出现第一名 编程实现，给出二维数组w，一维数组order 和用于输出比赛名次的数组result[n]， 求出result。 37. 有n 个长为m+1 的字符串， 如果某个字符串的最后m 个字符与某个字符串的前m 个字符匹配，则两个字符串可以联接， 问这n 个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。 将各个字符串作为一个节点，首尾链接就好比是一条边，将两个节点连接起来，于是问题就变成一个有关图的路径长度的问题。链接所得的字符串最长长度即为从图的某个节点出发所能得到的最长路径问题，与最短路径类似，可以应用弗洛伊德算法求解。对于循环，即可认为各个节点通过其他节点又回到自己，反应在路径长度上，就表示某个节点到自己节点的路径大于零（注：初始化个节点到自己的长度为零）。 弗洛伊德算法介绍 Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image.png，空间复杂度为file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(1).png。 Floyd-Warshall算法的原理是动态规划。 设file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(2).png为从file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(3).png到file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(4).png的只以file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(5).png集合中的节点为中间节点的最短路径的长度。
因此，file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(8).png。 算法如下： const int MAX = 1000000000; int floyd(int matrix[5][5],int n) { int dist[5][5]; int path[5][5]; for(int i=0; i<n; i++) for(int j=0; j<n; j++) dist[j] = matrix[j],path[j] = -1; for(int k=0; k<n; k++) for(int i=0; i<n; i++) for(int j=0; j<n; j++) if(dist[j]>dist[k]+dist[k][j]) dist[j] = dist[k]+dist[k][j],path[j] = k; for(int i=0; i<n; i++) { for(int j=0; j<n; j++) { if(i!=j&&dist[j] != MAX) { cout<<i<<"到"<<j<<"最短距离为"<<dist[j]<<endl; cout<<"路径逆序为:"<<j<<"->"; int mid = path[j]; while(mid!=-1) cout<<mid<<"->",mid = path[mid]; cout<<i<<endl<<endl; } } } return 0; } int _tmain(int argc, _TCHAR* argv[]) { int matrix[5][5] = {0,MAX,1,4,MAX, MAX,0,MAX,MAX,MAX, MAX,MAX,0,MAX,2, MAX,3,MAX,0,MAX, MAX,3,MAX,MAX,0}; floyd(matrix,5); return 0; } 运行如下： file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image.jpg 问题代码如下： void maxLengthInStrings(string text[],int nSize) { int dist[100][100]; int path[100][100]; memset(path,-1,sizeof(int)*100*100); memset(dist,0,sizeof(int)*100*100); int m = text[0].size()-1; for(int i=0; i<nSize; i++) { string iText = text.substr(1,m); for(int j=0; j<nSize; j++) { if(i!=j) { string jText = text[j].substr(0,m); if(iText == jText) dist[j] = 1; else dist[j] = 0; } } } for( int k=0; k<nSize; k++) for( int i=0; i<nSize; i++) for( int j=0; j<nSize; j++) { if(dist[k]&&dist[k][j]) { if(dist[j]<dist[k]+dist[k][j]) { dist[j] = dist[k]+dist[k][j]; path[j] = k; } } } int max_from,max_to,max = 0; for(int i=0; i<nSize; i++) { for(int j=0; j<nSize; j++) if(max<dist[j]) max = dist[j],max_from = i,max_to = j; } cout<<"最长串逆序如下"<<text[max_to]<<" "; int mid = path[max_from][max_to]; while(mid>=0) cout<<text[mid]<<" ",mid = path[max_from][mid]; cout<<text[max_from]<<endl; } // test int _tmain(int argc, _TCHAR* argv[]) 运行结果如下：{ string text[] = { "abcd", "bcde", "cdea", "deab", "eaba", "abab", "deac", "cdei", "bcdf", "cdfi", "dfic", "cdfk", "bcdg", }; maxLengthInStrings(text,sizeof(text)/sizeof(text[0])); return 0; } file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(1).jpg 38. 百度面试： 1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x 次天平， 最多可以从y 个小球中找出较轻的那个，求y 与x 的关系式。 三叉树，每次分为三等分，y = 3^x 2.有一个很大很大的输入流，大到没有存储器可以将其存储下来， 而且只输入一次，如何从这个输入流中随机取得m 个记录。 先把前m个记录留下，对于第i个（i>m)，以m/i的概率留下它，(设k = rand()%m,如果k小于m，则保留下来，并且替代序号为k的数字，否则舍弃）。 3.大量的URL 字符串，如何从中去除重复的，优化时间空间复杂度 哈希法 39. 网易有道笔试： (1). 求一个二叉树中任意两个节点间的最大距离， 两个节点的距离的定义是这两个节点间边的个数， 比如某个孩子节点和父节点间的距离是1，和相邻兄弟节点间的距离是2，优化时间空间复 杂度。 如果我们把二叉树看成一个图，父子节点之间的连线看成是双向的，我们姑且定义"距离"为两节点之间边的个数。写一个程序求一棵二叉树中相距最远的两个节点之间的距离。 file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(9).png 书中对这个问题的分析是很清楚的，我尝试用自己的方式简短覆述。 计算一个二叉树的最大距离有两个情况:
file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(10).png 我也想不到更好的分析方法。 但接着，原文的实现就不如上面的清楚 (源码可从下载): // 数据结构定义struct NODE{ NODE* pLeft; // 左子树 NODE* pRight; // 右子树 int nMaxLeft; // 左子树中的最长距离 int nMaxRight; // 右子树中的最长距离 char chValue; // 该节点的值};int nMaxLen = 0;// 寻找树中最长的两段距离void FindMaxLen(NODE* pRoot){ // 遍历到叶子节点，返回 if(pRoot == NULL) { return; } // 如果左子树为空，那么该节点的左边最长距离为0 if(pRoot -> pLeft == NULL) { pRoot -> nMaxLeft = 0; } // 如果右子树为空，那么该节点的右边最长距离为0 if(pRoot -> pRight == NULL) { pRoot -> nMaxRight = 0; } // 如果左子树不为空，递归寻找左子树最长距离 if(pRoot -> pLeft != NULL) { FindMaxLen(pRoot -> pLeft); } // 如果右子树不为空，递归寻找右子树最长距离 if(pRoot -> pRight != NULL) { FindMaxLen(pRoot -> pRight); } // 计算左子树最长节点距离 if(pRoot -> pLeft != NULL) { int nTempMax = 0; if(pRoot -> pLeft -> nMaxLeft > pRoot -> pLeft -> nMaxRight) { nTempMax = pRoot -> pLeft -> nMaxLeft; } else { nTempMax = pRoot -> pLeft -> nMaxRight; } pRoot -> nMaxLeft = nTempMax + 1; } // 计算右子树最长节点距离 if(pRoot -> pRight != NULL) { int nTempMax = 0; if(pRoot -> pRight -> nMaxLeft > pRoot -> pRight -> nMaxRight) { nTempMax = pRoot -> pRight -> nMaxLeft; } else { nTempMax = pRoot -> pRight -> nMaxRight; } pRoot -> nMaxRight = nTempMax + 1; } // 更新最长距离 if(pRoot -> nMaxLeft + pRoot -> nMaxRight > nMaxLen) { nMaxLen = pRoot -> nMaxLeft + pRoot -> nMaxRight; }}这段代码有几个缺点:
#include <iostream>using namespace std;struct NODE{ NODE *pLeft; NODE *pRight;};struct RESULT{ int nMaxDistance; int nMaxDepth;};RESULT GetMaximumDistance(NODE* root){ if (!root) { RESULT empty = { 0, -1 }; // trick: nMaxDepth is -1 and then caller will plus 1 to balance it as zero. return empty; } RESULT lhs = GetMaximumDistance(root->pLeft); RESULT rhs = GetMaximumDistance(root->pRight); RESULT result; result.nMaxDepth = max(lhs.nMaxDepth + 1, rhs.nMaxDepth + 1); result.nMaxDistance = max(max(lhs.nMaxDistance, rhs.nMaxDistance), lhs.nMaxDepth + rhs.nMaxDepth + 2); return result;} (2). 求一个有向连通图的割点，割点的定义是，如果除去此节点和与其相关的边， 有向图不再连通，描述算法。 40.百度研发笔试题 1)设计一个栈结构，满足一下条件：min，push，pop 操作的时间复杂度为O(1)。 2） 一串首尾相连的珠子（m个），有N种颜色（N《=10），设计一个算法，取出其中一段，要求包含所有N中颜色，并使长度最短。并分析时间复杂度与空间复杂度。 解法： 此题犹如在一个长字符串中找出其中一段，其中有一个字符集合的所有字符，并且这段字符串要最短，当然，这个长字符串是首位相连的。可以定义一个head和一个tail标识字符串的头和尾。定义一个数组charset【256】，用这个数组记录集合中的字符出现的次数，之所以数组大小是256，大概是要用数组下标来标识字符。刚开始head=tail=0，tail++直到字符集合中所有的字符数都不为0为止，然后head++直到字符集合中某个字符的数变为0，这是便得到一个字符段。当tail>=m时，tail=tail%m，当head为m时算法结束 43、递归和非递归两种方法实现二叉树的前序遍历。 44.腾讯面试题： 1.设计一个魔方（六面）的程序。 2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。 请用5分钟时间，找出重复出现最多的前10条。 先哈希，再用hash_map，最后再归并排序 3.收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似） 45.雅虎： 某一个元素也加一，现给出一正数矩阵，判断其是否能够由一个全零矩阵经过上述运算得到。1.对于一个整数矩阵，存在一种运算，对矩阵中任意元素加一时，需要其相邻（上下左右） 2.一个整数数组，长度为n，将其分为m份，使各份的和相等，求m的最大值 比如{3，2，4，3，6} 可以分成{3，2，4，3，6} m=1; {3,6}{2,4,3} m=2 {3,3}{2,4}{6} m=3 所以m的最大值为3 采用深度优先搜索 #include "stdafx.h" #include <iostream> #include <algorithm> using namespace std; bool cmp(int a, int b) { return a > b; } bool dfs(int sum, int k, int cnt, int groupSum, int groupNum, int n, int data[], bool dataState[]) { if(cnt == groupNum) return true; else if (sum == groupSum) return dfs(0,0,cnt+1,groupSum,groupNum,n,data,dataState); else { int pre, i; for( pre = 0, i = k; i<n; i++) { if(dataState==false &&pre!=data&&sum+data<=groupSum) { dataState = true; pre = data; if(dfs(sum+data,i+1,cnt,groupSum,groupNum,n,data,dataState)) break; dataState = false; if(k == 0) return false ; } } if(i == n) return false ; return true ; } } int _tmain(int argc, _TCHAR* argv[]) { int data[100]; bool dataState[100]; int n; int sum = 0; while(cin>>n,n) { for(int i=0; i<n; ++i) { cin>>data; sum+=data; } sort(data,data+n,cmp); int groupSum = 0; for(groupSum = data[0]; groupSum<sum; ++groupSum) { if(sum%groupSum==0) { int groupNum = sum/groupSum; memset(dataState, false,sizeof (dataState)); if(dfs(0,0,0,groupSum,groupNum,n,data,dataState)) { cout<<groupNum<< ' '<<groupSum<<endl; break; } } } } return 0; } 46.搜狐： 四对括号可以有多少种匹配排列方式？比如两对括号可以有两种：（）（）和（（）） 卡特兰数C（2n,n）/(n+1) 47.创新工场： 求一个数组的最长递减子序列 比如{9，4，3，2，5，4，3，2}的最长递减子序列为{9，5，4，3，2} 递推式：LIS = max{LIS[k]+1,1,|LIS>LIS[k],0<=k<i} LIS表示已i为结尾的数的最长递增子序列的长度。 这题明显用动态规划来解。假设在目标数组array[ ]的前i个元素中，以array元素为最大元素的递增子序列的长度是LIS。那么 递归求解表达式为： LIS[i+1] = max{1, LIS[k] + 1}, array[i+1] > array[k], k<=i, k>=0 时间复杂度为O(NlgN)的代码： int min(int *array,int len) { int m = array[0]; for (int i = 1; i < len; i++) { if (m > array) m = array; } return m; } int findFirstMin(int*array, int len, int key) {//找出有序数组array中，第一个小于key的元素，并返回该元素的索引 int low = 0; int high = len - 1; int mid; while (low <= high) { mid = low + (high - low )/2; if ( array[mid] >= key) { high = mid - 1; } else { low = mid + 1; } } return high; } int LIS(int *array,int len) { int *lis = new int[len]; int *maxValue = new int[len + 1]; maxValue[1] = array[0]; maxValue[0] = min(array, len) - 1; int nmax = 1; for (int i = 0; i < len; i++) lis = 1; int j; for (int i = 1; i < len; i++) { j = findFirstMin(maxValue,nmax + 1, array); lis = j + 1; if (lis > nmax) { nmax = lis; maxValue[nmax] =array; } else if (array >maxValue[j] && array < maxValue[j + 1]) { maxValue[j + 1] =array; } } delete lis; delete maxValue; return nmax; }扩展: (1)最长公共子序列 经常会遇到复杂问题不能简单地分解成几个子问题，而会分解出一系列的子问题。简单地采用把大问题分解成子问题，并综合子问题的解导出大问题的解的方法，问题求解耗时会按问题规模呈幂级数增加。 为了节约重复求相同子问题的时间，引入一个数组，不管它们是否对最终解有用，把所有子问题的解存于该数组中，这就是动态规划法所采用的基本方法。问题描述：字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij=yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。 考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-1”，并Z=“z0，z1，…，zk-1”为它们的最长公共子序列。不难证明有以下性质： （1） 如果am-1=bn-1，则zk-1=am-1=bn-1，且“z0，z1，…，zk-2”是“a0，a1，…，am-2”和“b0，b1，…，bn-2”的一个最长公共子序列； （2） 如果am-1!=bn-1，则若zk-1!=am-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列； （3） 如果am-1!=bn-1，则若zk-1!=bn-1，蕴涵“z0，z1，…，zk-1”是“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列。 这样，在找A和B的公共子序列时，如有am-1=bn-1，则进一步解决一个子问题，找“a0，a1，…，am-2”和“b0，b1，…，bm-2”的一个最长公共子序列；如果am-1!=bn-1，则要解决两个子问题，找出“a0，a1，…，am-2”和“b0，b1，…，bn-1”的一个最长公共子序列和找出“a0，a1，…，am-1”和“b0，b1，…，bn-2”的一个最长公共子序列，再取两者中较长者作为A和B的最长公共子序列。 求解： 引进一个二维数组c[][]，用c[j]记录X与Y[j] 的LCS 的长度，b[j]记录c[j]是通过哪一个子问题的值求得的，以决定搜索的方向。 我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c[i-1][j]与c[j-1]均已计算出来。此时我们根据X = Y[j]还是X != Y[j]，就可以计算出c[j]。 问题的递归式写成： file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(11).png 回溯输出最长公共子序列过程： file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(12).png 算法分析： 由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为Θ(m + n)。 代码： file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(1).gif#include <stdio.h> #include <string.h> #define MAXLEN 100 void LCSLength(char *x, char *y, int m, int n, int c[][MAXLEN], int b[][MAXLEN]) file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(2).giffile:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(3).gif{ file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(4).gif int i, j; for(i = 0; i <= m; i++) c[0] = 0; for(j = 1; j <= n; j++) c[0][j] = 0; for(i = 1; i<= m; i++) file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(5).giffile:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(6).gif { for(j = 1; j <= n; j++) { if(x[i-1] == y[j-1]) { c[j] = c[i-1][j-1] + 1; b[j] = 0; file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(7).gif } else if(c[i-1][j] >= c[j-1]) { c[j] = c[i-1][j]; b[j] = 1; } else { c[j] = c[j-1]; b[j] = -1; } } } file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image(8).gif} void PrintLCS(int b[][MAXLEN], char *x, int i, int j) { if(i == 0 || j == 0) return; if(b[j] == 0) { PrintLCS(b, x, i-1, j-1); printf("%c ", x[i-1]); } else if(b[j] == 1) PrintLCS(b, x, i-1, j); else PrintLCS(b, x, i, j-1); } int main(int argc, char **argv) { char x[MAXLEN] = {"ABCBDAB"}; char y[MAXLEN] = {"BDCABA"}; int b[MAXLEN][MAXLEN]; int c[MAXLEN][MAXLEN]; int m, n; m = strlen(x); n = strlen(y); LCSLength(x, y, m, n, c, b); PrintLCS(b, x, m, n); return 0; } （2）最长公共子串 例如ABAB，BABA，ABBA，最长公共子串为AB。 我们可以把该问题定义如下： 给出两个字符串S和T，S的长度为m，T的长度为n，找出S与T的最长公共子串。 假设S = “ABAB”，T=“BABA”，我们可以构造一个如下的矩阵：
[url=]file:///C:/Users/ADMINI~1/AppData/Local/Temp/enhtmlclip/Image.gif[/url] 1 #include <string.h> 2 #include <stdlib.h> 3 #include <stdio.h> 4 5 const char * LongestCommonSubstring(const char * strA, const char * strB) 6 { 7 char * LCS = NULL; 8 const size_t LengthA = strlen(strA); 9 const size_t LengthB = strlen(strB);10 size_t LCSLength = 0;11 unsigned int PositionX = 0;12 unsigned int PositionY = 0;13 14 int i, j;15 int Matrix[LengthA + 1][LengthB + 1];;16 17 for(i = 0; i < LengthA ; ++i)18 {19 for(j = 0; j < LengthB ; ++j)20 {21 Matrix[j] = 0;22 }23 } 24 25 for(i = 0; i < LengthA; ++i)26 {27 for(j = 0; j < LengthB; ++j)28 {29 if(strA == strB[j])30 {31 if((i == 0)||(j == 0))32 Matrix[j] = 1;33 else 34 Matrix[j] = Matrix[i - 1][j - 1] + 1;35 }36 if(Matrix[j] > LCSLength)37 {38 LCSLength = Matrix[j];39 PositionX = i;40 PositionY = j;41 }42 }43 } 44 45 46 LCS = (char *)malloc(LCSLength + 1);47 int index = LCSLength - 1;48 while(index >= 0)49 {50 LCS[index] = strA[PositionX];51 --index;52 --PositionX;53 }54 LCS[LCSLength] = '\0'; 55 56 return LCS;57 }58 int main(int argc, char **argv) 59 {60 const char * strA = "abab";61 const char * strB = "baba";62 const char * LCS = LongestCommonSubstring(strA, strB);63 printf("Longest Common Substring is %s\n", LCS);64 return 0;65 } 48.微软： 一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5} 是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。 变形的二叉查找算法 49.一道看上去很吓人的算法面试题： 哈希 50.网易有道笔试： 2.求一个有向连通图的割点，割点的定义是， 如果除去此节点和与其相关的边，有向图不再连通，描述算法。 |
[技术| 编程·课件·Linux] 100道经典算法题（26-50)
sissi
· 发布于 2012-10-18 08:06
· 1823 次阅读
转载文章时务必注明原作者及原始链接，并注明「发表于 软院网 RuanYuan.Net 」，并不得对作品进行修改。
