首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
admin
2017-04-28
33
问题
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:在遍历字符数组的过程中,对已经访问过的字符进行标记,同时记下它们第一次出现在原字符串中的位置,当以后再次遍历到此字符时,根据当前的位置和第一次出现的位置,求出它们之间的距离,然后用得到的距离和当前最大距离相比较。为此需要设置一个数组用来存放已经访问过的字符,为了能加快搜索,采用字符的ASCⅡ码作为数组的下标来支持随机访问,通过对应下标中的数组元素的访问标记is_access来判断它是否被访问过,另外还要获取它第一次出现的位置,很明显这里的数组元素应设置为结构体类型,每遍历一个字符就开始判断,并更新最大距离。
解析
转载请注明原文地址:https://jikaoti.com/ti/lKfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
凯末尔世俗化改革的内容和意义。
1901—1939年间美国历届政府在国内经济活动中职能作用的演变。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
宁夏回族自治区的设立时间是()。
“文化大革命”结束后,在纠正“文化大革命”错误的过程中,整个过程受到()的严重阻碍。
美国主张建立国际联盟的主要目的是()。
下列内容,哪些与垄断组织出现有关?()①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治和经济生活④积极向外扩张,从经济上瓜分世界
相对于单一内核结构,采用微内核结构设计实现操作系统具有诸多好处,但是,()并不是微内核的优势。
某浮点机字长16位,其浮点数格式为:阶码5位(含1位阶符),采用补码表示,尾数11位(含1位数符),采用补码表示,且尾数为规格化形式。已知X=0.1011000011×20.0101,Y=0.0001100000×20.1000,试求X+Y.要求写出详细的
随机试题
抗日战争开始后,国民政府军事委员会的内部领导体制及机构作了较大调整,大大提高了军事委员会的地位。这一调整主要体现为()
丙型肝炎的主要传播途径是
根据民事诉讼法有关管辖的规定,下列哪些民事诉讼由原告住所地人民法院管辖?
客流因人们的出行而形成,而人们出行的原因有两种:即生产、工作的需要和生活的需要。下列各项属于生活需要的有()。
劳动保障行政复议是由( )引起的。
导游员根据()与旅游者签订的合同或约定,按接待计划安排和组织游客参观游览。
下列哪些理论是对遗忘的理论解释?()
工人人数最多的厂是()。
分析商业银行盈利性的指标不包括()。[中国人民大学2015金融硕士]
A、It’suptoyou.B、Comeoffit.C、Thatisagoodidea.D、ItisOK.A本题考查对征求意见的选择疑问句的回答。对此类问题的回答,可以选择其一作答;也可以都不选择,然后表明自己的态度。A)“取
最新回复
(
0
)