首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
admin
2017-04-28
82
问题
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:在遍历字符数组的过程中,对已经访问过的字符进行标记,同时记下它们第一次出现在原字符串中的位置,当以后再次遍历到此字符时,根据当前的位置和第一次出现的位置,求出它们之间的距离,然后用得到的距离和当前最大距离相比较。为此需要设置一个数组用来存放已经访问过的字符,为了能加快搜索,采用字符的ASCⅡ码作为数组的下标来支持随机访问,通过对应下标中的数组元素的访问标记is_access来判断它是否被访问过,另外还要获取它第一次出现的位置,很明显这里的数组元素应设置为结构体类型,每遍历一个字符就开始判断,并更新最大距离。
解析
转载请注明原文地址:https://kaotiyun.com/show/yXRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
荷马时代的社会管理制度和经济生活。
1901一1939年间美国历届政府在国内经济活动中职能作用的演变。
中华人民共和国恢复了在联合国合法席位的时间是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
中国共产党召开七届二中全会的主要目的是()。
材料一1870年代初的南部,虽然也不时出现针对黑人的种族暴行,但在日常生活中,黑人基本能与白人同车船、共饭桌、游公园。但这种情况并没有持续多久。随着前白人奴隶主“重新夺回”南部各州政权,许多州在维护社会秩序名义下,制定了各种法律,规定黑人与白人必
在平衡二叉树中的每个结点上增设一个Lsize域,其值为它的左子树中的结点个数加1,试写一个时间复杂度为O(logn)的算法,确定树中第k个结点的位置。
设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1则T中的叶子数是()。
已知一个带有表头结点的单链表,结点结构为(data,next),假设该链表只给出了头指针L,请设计一个时间和空间上尽可能高效的算法,将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同。给出算法的基本设计思想。
随机试题
患者,40岁。右耳垂下肿物5年,生长缓慢,无痛。检查:肿物以耳垂为中心,界限清楚,活动,呈椭圆形,表面呈结节状,硬度中等。该患者最可能的临床诊断是右侧腮腺
女,24岁。停经45d,诊断为早期妊娠。在行负压吸宫术时,突然出现面色苍白、出汗、头晕、胸闷,体检血压80/50mmHg,心率40/min。最可能的诊断是
使胃蛋白酶原转变为胃蛋白酶的激活物是()。
斜井表土段如为粘结性土层时,其暗挖的方法宜采用()。
下列无形资产不得计算摊销在企业所得税前扣除的是()。
2011年1月甲企业以融资租赁的方式租入一处房产,原值1000万元,租赁期5年,租入当月投入使用,每月支付租赁费10万元,税务机关确定甲企业为该房产的纳税人,计算房产余值的扣除比例为20%。2011年甲企业融资租赁的房产应缴纳房产税()。
2×17年3月,甲公司购买了90套全新的公寓拟以优惠价格向职工出售,该公司共有90名职工,其中72名为直接生产人员,18名为公司总部管理人员。甲公司拟向直接生产人员出售的住房平均每套购买价为100万元,向直接生产人员出售的价格为每套80万元;拟向管理人员出
在计算机中,算法是指()
在关系运算中,投影运算的含义是()。
关于汇编语言程序()。
最新回复
(
0
)