首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
admin
2017-04-28
37
问题
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:在遍历字符数组的过程中,对已经访问过的字符进行标记,同时记下它们第一次出现在原字符串中的位置,当以后再次遍历到此字符时,根据当前的位置和第一次出现的位置,求出它们之间的距离,然后用得到的距离和当前最大距离相比较。为此需要设置一个数组用来存放已经访问过的字符,为了能加快搜索,采用字符的ASCⅡ码作为数组的下标来支持随机访问,通过对应下标中的数组元素的访问标记is_access来判断它是否被访问过,另外还要获取它第一次出现的位置,很明显这里的数组元素应设置为结构体类型,每遍历一个字符就开始判断,并更新最大距离。
解析
转载请注明原文地址:https://kaotiyun.com/show/yXRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述罗马法学的发展情况。
试述卡德纳斯改革的背景、内容、性质和意义。
概述日本古代文化的发展情况。
1895年发现X射线,拉开物理学革命序幕的科学家是()。
关于斯巴达的论述错误的是()。
1923年纳粹党魁希特勒发动了“啤酒馆暴动”,对此叙述不正确的一项是()。
汉章帝会群儒于白虎观,讨论经义,由()写成《白虎通德论》(又称《白虎通义》、《白虎通》)一书,这部书系统地吸收了阴阳五行和谶纬之学,形成今文经学派的主要观点。
1951年底到1952年春,中国共产党在党政机构工作人员中开展运动的内容是()。
16世纪中期,德意志资产阶级迫切要求实现国家的统一,其首要的目的是()。
随机试题
通过沪深证券交易所交易系统发行和交易的债券是()。
书店为争夺读者、提高营业额竞相打折销售,这是买主与卖主之间的竞争。()
引起水冲脉的疾病是
窝沟封闭的适应症是
OPT中的物流原则要求批量大小应是固定的。()
初唐四杰中写檄文讨伐武则天的是()。
时尚健美操的种类有()。
参加教师资格考试有作弊行为时,其考试成绩作废,()年内不得再次参加教师资格考试。
当事人对法院作出的民事决定有权申请复议的是()。
Whatmatters______notwinningbutparticipating.
最新回复
(
0
)