笔试算法题（30）：从已排序数组中确定数字出现的次数 & 最大公共子串和最大公共序列（LCS）
2024-09-30 16:29:57
出题：在已经排序的数组中，找出给定数字出现的次数；
分析：
- 解法1：由于数组已经排序，所以可以考虑使用二分查找确定给定数字A的第一个出现的位置m和最后一个出现的位置n，最后m-n+1就是A出现的次数；使用二分查找可疑快速确定给定数字，但是如果确定其左右范围则比较麻烦，对编码细节要求较高；
- 解法2：HashTable解决
解题：
int occurrence(int *array, int length, int t) {
/**
* 寻找t所在的区间
* 此阶段之后left和right索引
* 的段中，t必定横跨左右部分
* 如果left>right说明没有找到t，返回0
* */
int left=, right=length-, middle;
while(left<=right) {
middle=(left+right)/;
if(t==array[middle])
break;
else if(t>array[middle])
left=middle+;
else
right=middle-;
}
if(left>right) return ;
/**
* 处理左边部分
* 此部分中的元素都小于等于t
* 不断逼近最左边的t
* */
int l1=left, r1=middle,m1;
while(l1<=r1) {
/**
* 当两个相邻的数取middle时，要取
* 左边的一个，由于除法本就是向下
* 取整，所以没问题
* */
m1=(l1+r1)/;
if(t==array[m1]) {
if(l1==r1)
break;
r1=m1-;
} else
l1=m1+;
}
/**
* 处理右边部分
* 比部分中的元素都大于等于t
* 不断逼近最右边的t
* */
int l2=middle, r2=right, m2;
while(l2<=r2) {
/**
* 注意除法都是向下取整，会对结果造成
* 影响，从右向左逼近的时候需要向上取整
* 也就是当两个相邻的数取middle时，要取
* 右边的一个
* */
m2=(l2+r2+)/;
if(t==array[m2]) {
if(l2==r2)
break;
l2=m2+;
} else
r2=m2-;
}
return m2-m1+;
}
int main() {
int array[]={,,,,,,};
int count=occurrence(array, , );
printf("\n%d",count);
return ;
}
出题：给定两个字符串，要求找到他们的最大公共子串；
分析：
- 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])；
解题：
char* lcs1(char *first, char *second) {
char *f=first,*ftemp=NULL, *stemp=NULL, *start=NULL;
int max=, ctemp=;
bool iscs;
/**
* 依次以first中的每个字符作为一次循环的开始，
* 每次循环都从second的起始字符开始比较。
* 将first当前的索引字符从second的起始字符开始
* 比较，如果不相同，则比较second右边的下一个字符
* 如果相同，则增加计数，并同时移动first和second
* */
while(*f!='\0') {
/**
* 每次循环都需要更新四个变量：
* 将first设置到下一个字符，
* 将公共子串计数清0，
* 将second设置到起始字符，
* 将是否存在公共子串设置为false
* */
ftemp=f;ctemp=;stemp=second;iscs=false;
while(ftemp!='\0' && stemp!='\0') {
if(*ftemp!=*stemp) {
if(iscs)
break;
stemp++;
} else {
iscs=true;
ctemp++;
ftemp++;stemp++;
}
}
/**
* 仅当当前的计数大于最大计数时，
* 才更新max指针和start指针
* */
if(max<ctemp) {
max=ctemp;
start=f;
}
/**
* 如果一次循环中两个字符串中任意一个
* 已经到结尾，说明不会再有更大的max，
* 直接跳出循环
* */
if(*ftemp=='\0' || stemp=='\0')
break;
f++;
}
if(start==NULL)
return NULL;
/**
* 创建动态内存存储lcs
* */
char *result=new char[max+];
char *rtemp=result;
for(int i=;i<max;i++) {
printf("%c,",*start);
*rtemp=*start;
rtemp++;start++;
}
*rtemp='\0';
return result;
}
/**
* 由于仅需要打印dir对应值为0的元素（此时first和second的字符相等），所以
* 只需要传入first或者second中的一个就可以。
* 使用递归的方式，从末尾开始处理，但是递归之后才进行打印，所以LCS可以正序
* 打印
* */
void showLCS(char *first, int *dir, int lfirst, int lsecond, int length) {
if(lfirst== || lsecond==)
return;
if(dir[lfirst+lsecond*length]==) {
showLCS(first, dir, lfirst-, lsecond-, length);
printf("%c,",first[lfirst]);
} else if(dir[lfirst+lsecond*length]==)
showLCS(first, dir, lfirst-, lsecond, length);
else
showLCS(first, dir, lfirst, lsecond-, length);
}
/**
* 利用动态规划，使用簿记matrix的方法记录小子问题，然后重复利用
* 小子问题解决合成问题，最终解决整个问题。
* 在first和second组成的二维表中，一共有三种状态转移方式：
* 如果first[m]=second[n]，则跳到first[m-1]和second[n-1]
* 如果first[m]!=second[n]，则跳到first[m-1]和second[n]，
* first[m]和second[n-1]的LCS中较大的一个
* 需要设定初始状态为0
* */
void lcs2(char *first, int lfirst, char *second, int lsecond) {
int *dir=new int[lfirst*lsecond];
int *dis=new int[lfirst*lsecond];
/**
* 保留first和second的第一个字符，将其dis设置为0，便于实现簿记
* dir矩阵中：0表示up-left移动；1表示left移动;2表示up移动
* */
for(int i=;i<lfirst;i++)
dis[i]=;
for(int i=;i<lsecond;i++)
dis[i*lfirst]=;
for(int j=;j<lsecond;j++) {
for(int i=;i<lfirst;i++) {
if(first[i]==second[j]) {
/**
* 如果当前字符相等，则说明[i,j]长度的LCS为
* [i-1,j-1]长度的LCS 加上1；
* up-left移动
* */
dis[i+j*lfirst]=
dis[(i-)+(j-)*lfirst]+;
dir[i+j*lfirst]=;
} else if(dis[i+(j-)*lfirst] >
dis[(i-)+j*lfirst]) {
/**
* 如果当前字符不等，并且[i,j-1]长度的LCS大于
* [i-1,j]长度的LCS，则当前[i,j]长度的LCS等于
* [i,j-1]产度的LCS
* up移动
* */
dis[i+j*lfirst]=
dis[i+(j-)*lfirst];
dir[i+j*lfirst]=;
} else {
/**
* 如果当前字符不等，并且[i-1,j]长度的LCS大于
* [i,j-1]长度的LCS，则当前[i,j]长度的LCS等于
* [i-1,j]产度的LCS
* left移动
* */
dis[i+j*lfirst]=
dis[(i-)+j*lfirst];
dir[i+j*lfirst]=;
}
}
}
showLCS(first, dir, lfirst-, lsecond-, lfirst);
delete [] dir;
delete [] dis;
}
最新文章
- 引用项目外dll时不显示注释的解决方案
- WPS 认证机制
- ListMultimap 容器
- ios7技巧：你需要掌握的19个iOS7使用技巧
- CCNA 4.14 TP Correction
- iOS 常用控件集合 完整项目
- jdbc连接池中c3p0的配置文件的详解以及在在java中如何使用
- Spark 1.60的executor schedule
- 并发情况下synchronized死锁
- Linux-统一事件源
- 解决 MySQL 分页数据错乱重复
- mysql中 date datetime time timestamp 的区别
- C#多线程之旅(7)——终止线程
- JustSoso笔记
- Python XML解析之DOM
- 【easy】202. Happy Number
- EMF32名词解释
- 使用Eclipse的代码追踪功能
- Docker面试题
- macOS下通过docker在局域网成功访问mysql5.6数据库