编写一个函数来查找字符串数组中的最长公共前缀.docx

上传人:王** 文档编号:657380 上传时间:2023-12-08 格式:DOCX 页数:4 大小:18.68KB
下载 相关 举报
编写一个函数来查找字符串数组中的最长公共前缀.docx_第1页
第1页 / 共4页
编写一个函数来查找字符串数组中的最长公共前缀.docx_第2页
第2页 / 共4页
编写一个函数来查找字符串数组中的最长公共前缀.docx_第3页
第3页 / 共4页
编写一个函数来查找字符串数组中的最长公共前缀.docx_第4页
第4页 / 共4页
亲,该文档总共4页,全部预览完了,如果喜欢就下载吧!
资源描述

《编写一个函数来查找字符串数组中的最长公共前缀.docx》由会员分享,可在线阅读,更多相关《编写一个函数来查找字符串数组中的最长公共前缀.docx(4页珍藏版)》请在优知文库上搜索。

1、1、编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀,返回空字符串o示例1:输入:rs=flower,flow,flight输出:W示例2:输入:btrs=dog,racecar,car:bw解麻:愉入不存在公共前缀。可以使用水平扫描法解决这个问题。我们将第一个字符串作为最长公共前缀的初始值,然后逐个比较后面的字符串与当前的公共前缀,更新公共前缀为两者的共同部分。如果最终的公共前缀为空字符串,则说明不存在公共前缀。具体步骤如下:如果输入字符串数组为空,直接返回空字符串。将第一个字符串设为初始的最长公共前缀。遍历数组中的每个字符串,将当前字符串与最长公共前缀进行比较,更新最长公共

2、前缀为两者的共同部分。如果最长公共前缀为空字符串,则直接返回空字符串。返回最长公共前缀作为结果。 1=h=200 0=strsi.length=200 strsi仅由小写英文字母组成#include#include#includeusingnamespacestd;stringIOngeStComrnOnPrefiX(VeCtOr&strs)if(O)return;)stringprefix=strsO;for(inti=l;i();i+)while(strsi.find(prefix)!=0)prefix=r(0,h()-1);if()return)returnprefix;)intmain

3、()vectorstrs=flower,flow,flight);stringresult=IongestCommonPrefix(Strs);coutLongestcommonprefix:,resultendl;returnO;)给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。请必须使用时间复杂度为O(IOgn)的算法。示例1:输入:nums=1,3,5,6,target=5输出:2输入:nums=1,3,5,6,target=2SU1区例3:输入:nums=1,3,5,6,target=7箔出:4可以使用二分查找算法

4、来解决这个问题。由于给定的数组是有序的,我们可以通过比较目标值与数组中间元素的大小,来确定目标值在数组中的位置。具体步骤如下:L初始化左边界left为0,右边界right为数组长度减1。2.当Ieft小于等于right时,执行以下步骤:2.1 计算中间位置mid,mid=(left+right)/2。2.2 如果目标值等于中间位置的元素numsmid,则返回mid。2.3 如果目标值小于中间位置的元素numsmid,则在左半边继续查找,更新右边界为midIo2.4 如果目标值大于中间位置的元素numsmid,则在右半边继续查找,更新左边界为mid+Io如果循环结束时仍未找到目标值,则返回lef

5、t,即将被按顺序插入的位置。时间复杂度分析:由于每次查找都将数组范围缩小一半,所以时间复杂度为0(logn)o 1=h=10fl -IOk=numsi素|的瓯排列数组 1(V=targetV=IOg#include#includeusingnamespacestd;intsearchlnsert(vector&nums,inttarget)intleft=O;intright=()-1;while(left=right)intmid=left+(right-left)/2;if(numsmid=target)returnmid;elseif(numsmidtarget)left=mid+1;elseright=mid-1;)returnleft;)intmain()vectornums=1,3,5,6;inttarget=5;intresult=searchlnsert(nums,target);coutInsertposition:,resultendl;returnO;

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!