首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
admin
2017-04-28
74
问题
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:在遍历字符数组的过程中,对已经访问过的字符进行标记,同时记下它们第一次出现在原字符串中的位置,当以后再次遍历到此字符时,根据当前的位置和第一次出现的位置,求出它们之间的距离,然后用得到的距离和当前最大距离相比较。为此需要设置一个数组用来存放已经访问过的字符,为了能加快搜索,采用字符的ASCⅡ码作为数组的下标来支持随机访问,通过对应下标中的数组元素的访问标记is_access来判断它是否被访问过,另外还要获取它第一次出现的位置,很明显这里的数组元素应设置为结构体类型,每遍历一个字符就开始判断,并更新最大距离。
解析
转载请注明原文地址:https://kaotiyun.com/show/yXRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述《拉巴洛条约》签订的背景、条约的主要内容及其意义。
试述卡德纳斯改革的背景、内容、性质和意义。
结合诸条约内容简述中国社会沦为半殖民地半封建社会的过程。
1895年发现X射线,拉开物理学革命序幕的科学家是()。
美国主张建立国际联盟的主要目的是()。
元朝各行政区的行政机构称为()。()有指挥军事活动的权力,遇有征伐则设置()。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
关于中世纪西欧城市发展状况,叙述正确的是()。①城市取得自由或自治,一般以赎买为手段。②城市的自由和自治,一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役,并履行封臣的其他义务。④城市可视为
中国共产党召开七届二中全会的主要目的是()。
以下()协议完成了从网卡到IP地址的映射。
随机试题
交接于足小趾端两条经脉是()(2007年第153题)
推动区域协调发展,就要继续实施区域发展总体战略,为此,需要()
HIA血清学分型试验所使用的方法是
陈先生,44岁,患慢性粒细胞白血病3年,近日出现不明原因的高热,胸骨疼痛难忍,脾迅速增大。此情况需考虑()
某房屋建筑工程于2009年7月15日通过竣工验收,建设单位于2009年7月31日办理了竣工验收备案手续。按照《建设工程质量管理条例》的规定,该工程电气管线的最低保修期限截止日期是()。
请阅读下列材料,并按要求作答。比例的基本性质:组成比例的四个数,叫做比例的项。两端的两项叫做比例的外项,中间的两项叫做比例的内项。例如:两个外项的积是2.4×40=___两个内项的积是1.6×60=___如果把比例改成分数形式,等号两边的分子和分
阿多诺(T.W.Adorno)(中国传媒大学2013年研;北大2007年研)
(46)In1798ThomasRobertMalthusfamouslypredictedthatshort-termgainsinlivingstandardswouldinevitablybeunderminedas
JuniperNetworkssaidthatwhichYahooBrasilhasdeployedits【S1】______M-seriesrouterstolayoffthegroundworkfor
【1】
最新回复
(
0
)