首页 > 代码库 > 笔试算法题(30):从已排序数组中确定数字出现的次数 & 最大公共子串和最大公共序列(LCS)
笔试算法题(30):从已排序数组中确定数字出现的次数 & 最大公共子串和最大公共序列(LCS)
出题:在已经排序的数组中,找出给定数字出现的次数;
分析:
- 解法1:由于数组已经排序,所以可以考虑使用二分查找确定给定数字A的第一个出现的位置m和最后一个出现的位置n,最后m-n+1就是A出现的次数;使用二分查找可疑快速确定给定数字,但是如果确定其左右范围则比较麻烦,对编码细节要求较高;
- 解法2:HashTable解决
解题:
1 int occurrence(int *array, int length, int t) { 2 /** 3 * 寻找t所在的区间 4 * 此阶段之后left和right索引 5 * 的段中,t必定横跨左右部分 6 * 如果left>right说明没有找到t,返回0 7 * */ 8 int left=0, right=length-1, middle; 9 while(left<=right) { 10 middle=(left+right)/2; 11 if(t==array[middle]) 12 break; 13 else if(t>array[middle]) 14 left=middle+1; 15 else 16 right=middle-1; 17 } 18 if(left>right) return 0; 19 /** 20 * 处理左边部分 21 * 此部分中的元素都小于等于t 22 * 不断逼近最左边的t 23 * */ 24 int l1=left, r1=middle,m1; 25 while(l1<=r1) { 26 /** 27 * 当两个相邻的数取middle时,要取 28 * 左边的一个,由于除法本就是向下 29 * 取整,所以没问题 30 * */ 31 m1=(l1+r1)/2; 32 if(t==array[m1]) { 33 if(l1==r1) 34 break; 35 r1=m1-1; 36 } else 37 l1=m1+1; 38 } 39 /** 40 * 处理右边部分 41 * 比部分中的元素都大于等于t 42 * 不断逼近最右边的t 43 * */ 44 int l2=middle, r2=right, m2; 45 while(l2<=r2) { 46 /** 47 * 注意除法都是向下取整,会对结果造成 48 * 影响,从右向左逼近的时候需要向上取整 49 * 也就是当两个相邻的数取middle时,要取 50 * 右边的一个 51 * */ 52 m2=(l2+r2+1)/2; 53 if(t==array[m2]) { 54 if(l2==r2) 55 break; 56 l2=m2+1; 57 } else 58 r2=m2-1; 59 } 60 61 return m2-m1+1; 62 } 63 64 int main() { 65 int array[]={1,2,3,4,5,5,5}; 66 int count=occurrence(array, 7, 5); 67 printf("\n%d",count); 68 return 0; 69 }
出题:给定两个字符串,要求找到他们的最大公共子串;
分析:
- LCS问题与LIS(Largest Incremental Sub-sequence)问题类似,将原字符串A进行排序之后得到B,则A的LIS就是A和B的LCS。另外也可以直接使用DP;经典的LCS,但是有两种解释,一种是子串需要连在一起出现,一种是子串不需要连在一起出现;
- 解法1:Largest Common Sub-string,如果将需求理解为公共子串的字符必须相连,则解法如下:将字符串A的每一个字符依次匹配B的每一个位置,时间复杂度O(MN),M和N分别为A和B的长度;
- 解法2:Largest Common Sub-Sequence,如果将需求理解为公共子串的字符可以分离,则为经典的LCS问题(也可以理解为求两个集合的顺序交集),则解法如下:动态规划(DP),
给定first[1,m]和second[1,n],求LCS(first[1,m],second[1,n]),
如 果first和second的最后一个字符相同,则有first[m]=second[n]=result[k],这样问题化解为给定 first[1,m-1]和second[1,n-1],求LCS(first[1,m-1],second[1,n-1]),原问题为 LCS(first[1,m],second[1,n])= LCS(first[1,m-1],second[1,n-1]) +1
如果first和second的最后一个字符不相同,则问题化解为result[1,k]= max{LCS(first[1,m-1],second[1,n]), LCS(first[1,m],second[1,n-1]);
解题:
1 char* lcs1(char *first, char *second) { 2 char *f=first,*ftemp=NULL, *stemp=NULL, *start=NULL; 3 int max=0, ctemp=0; 4 bool iscs; 5 /** 6 * 依次以first中的每个字符作为一次循环的开始, 7 * 每次循环都从second的起始字符开始比较。 8 * 将first当前的索引字符从second的起始字符开始 9 * 比较,如果不相同,则比较second右边的下一个字符 10 * 如果相同,则增加计数,并同时移动first和second 11 * */ 12 while(*f!=‘\0‘) { 13 /** 14 * 每次循环都需要更新四个变量: 15 * 将first设置到下一个字符, 16 * 将公共子串计数清0, 17 * 将second设置到起始字符, 18 * 将是否存在公共子串设置为false 19 * */ 20 ftemp=f;ctemp=0;stemp=second;iscs=false; 21 while(ftemp!=‘\0‘ && stemp!=‘\0‘) { 22 if(*ftemp!=*stemp) { 23 if(iscs) 24 break; 25 stemp++; 26 } else { 27 iscs=true; 28 ctemp++; 29 ftemp++;stemp++; 30 } 31 } 32 /** 33 * 仅当当前的计数大于最大计数时, 34 * 才更新max指针和start指针 35 * */ 36 if(max<ctemp) { 37 max=ctemp; 38 start=f; 39 } 40 /** 41 * 如果一次循环中两个字符串中任意一个 42 * 已经到结尾,说明不会再有更大的max, 43 * 直接跳出循环 44 * */ 45 if(*ftemp==‘\0‘ || stemp==‘\0‘) 46 break; 47 f++; 48 } 49 if(start==NULL) 50 return NULL; 51 /** 52 * 创建动态内存存储lcs 53 * */ 54 char *result=new char[max+1]; 55 char *rtemp=result; 56 for(int i=0;i<max;i++) { 57 printf("%c,",*start); 58 *rtemp=*start; 59 rtemp++;start++; 60 } 61 *rtemp=‘\0‘; 62 return result; 63 } 64 /** 65 * 由于仅需要打印dir对应值为0的元素(此时first和second的字符相等),所以 66 * 只需要传入first或者second中的一个就可以。 67 * 使用递归的方式,从末尾开始处理,但是递归之后才进行打印,所以LCS可以正序 68 * 打印 69 * */ 70 void showLCS(char *first, int *dir, int lfirst, int lsecond, int length) { 71 if(lfirst==0 || lsecond==0) 72 return; 73 if(dir[lfirst+lsecond*length]==0) { 74 showLCS(first, dir, lfirst-1, lsecond-1, length); 75 printf("%c,",first[lfirst]); 76 } else if(dir[lfirst+lsecond*length]==1) 77 showLCS(first, dir, lfirst-1, lsecond, length); 78 else 79 showLCS(first, dir, lfirst, lsecond-1, length); 80 } 81 /** 82 * 利用动态规划,使用簿记matrix的方法记录小子问题,然后重复利用 83 * 小子问题解决合成问题,最终解决整个问题。 84 * 在first和second组成的二维表中,一共有三种状态转移方式: 85 * 如果first[m]=second[n],则跳到first[m-1]和second[n-1] 86 * 如果first[m]!=second[n],则跳到first[m-1]和second[n], 87 * first[m]和second[n-1]的LCS中较大的一个 88 * 需要设定初始状态为0 89 * */ 90 void lcs2(char *first, int lfirst, char *second, int lsecond) { 91 int *dir=new int[lfirst*lsecond]; 92 int *dis=new int[lfirst*lsecond]; 93 /** 94 * 保留first和second的第一个字符,将其dis设置为0,便于实现簿记 95 * dir矩阵中:0表示up-left移动;1表示left移动;2表示up移动 96 * */ 97 for(int i=0;i<lfirst;i++) 98 dis[i]=0; 99 for(int i=0;i<lsecond;i++) 100 dis[i*lfirst]=0; 101 102 for(int j=1;j<lsecond;j++) { 103 for(int i=1;i<lfirst;i++) { 104 if(first[i]==second[j]) { 105 /** 106 * 如果当前字符相等,则说明[i,j]长度的LCS为 107 * [i-1,j-1]长度的LCS 加上1; 108 * up-left移动 109 * */ 110 dis[i+j*lfirst]= 111 dis[(i-1)+(j-1)*lfirst]+1; 112 dir[i+j*lfirst]=0; 113 } else if(dis[i+(j-1)*lfirst] > 114 dis[(i-1)+j*lfirst]) { 115 /** 116 * 如果当前字符不等,并且[i,j-1]长度的LCS大于 117 * [i-1,j]长度的LCS,则当前[i,j]长度的LCS等于 118 * [i,j-1]产度的LCS 119 * up移动 120 * */ 121 dis[i+j*lfirst]= 122 dis[i+(j-1)*lfirst]; 123 dir[i+j*lfirst]=2; 124 } else { 125 /** 126 * 如果当前字符不等,并且[i-1,j]长度的LCS大于 127 * [i,j-1]长度的LCS,则当前[i,j]长度的LCS等于 128 * [i-1,j]产度的LCS 129 * left移动 130 * */ 131 dis[i+j*lfirst]= 132 dis[(i-1)+j*lfirst]; 133 dir[i+j*lfirst]=1; 134 } 135 } 136 } 137 138 showLCS(first, dir, lfirst-1, lsecond-1, lfirst); 139 140 delete [] dir; 141 delete [] dis; 142 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。