首页 > 代码库 > 笔试算法题(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 }