笔试算法题（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("
%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!='

笔试算法题（30）：从已排序数组中确定数字出现的次数 & 最大公共子串和最大公共序列（LCS）

相关推荐