首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求: 给出算法的基本设
admin
2017-04-28
31
问题
给定一字符串,该字符串中存在若干对相同的字符,设计一个在时间和空间上尽可能高效的算法,找出一对相同字符在该字符串中的最大距离。例如:“KLabcLdecL”,其中第一个“L”和最后一个“L”相距最远,它们在原字符串中的位置相差8,要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:在遍历字符数组的过程中,对已经访问过的字符进行标记,同时记下它们第一次出现在原字符串中的位置,当以后再次遍历到此字符时,根据当前的位置和第一次出现的位置,求出它们之间的距离,然后用得到的距离和当前最大距离相比较。为此需要设置一个数组用来存放已经访问过的字符,为了能加快搜索,采用字符的ASCⅡ码作为数组的下标来支持随机访问,通过对应下标中的数组元素的访问标记is_access来判断它是否被访问过,另外还要获取它第一次出现的位置,很明显这里的数组元素应设置为结构体类型,每遍历一个字符就开始判断,并更新最大距离。
解析
转载请注明原文地址:https://kaotiyun.com/show/yXRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
第一国际开展了哪些活动?其内部经历了哪些主要斗争?
关于斯巴达的论述错误的是()。
有人说:“我们应当以资本供给全世界,而谁以资本供给全世界,谁就应当管理全世界。”讲这话的应该是()。
下列关于湘军的叙述中不正确的是()。
第一国际成立前,各国无产阶级强烈要求加强国际团结的直接原因是()。
周人重视婚姻,对婚礼尤为讲究。周代的婚礼有六项程序,即:①纳征②问名③纳采④请期⑤亲迎⑥纳吉下列选项顺序排列正确的是()
关于中世纪西欧城市发展状况,叙述正确的是()。①城市取得自由或自治,一般以赎买为手段。②城市的自由和自治,一般以封建主或国王颁发的特许证书为凭据。③有的城市集体为封君服军役,并履行封臣的其他义务。④城市可视为
中国共产党召开七届二中全会的主要目的是()。
加尔文教传播到法国后,其信仰者被称为()。
设计一个算法,求无向图G(采用邻接表存储)的连通分量个数。
随机试题
肺胀的病理因索,主要责之于()(1995年第58题)
根性感觉障碍特点应除外
某幼儿班聘请某甲担任幼儿班教师。某日上午9时左右,幼儿班课间休息时,某甲离校打电话,几个幼儿在教室里的火炉旁烤火。其中某乙5岁和某丙4岁因争夺位置而打斗,某乙用石块将某丙头部打破,而某丙则把某乙按在火炉上,某乙被烫伤。为此,某丙花去医药费500元,某乙花去
A公司承包某超高层建筑机电工程施工项目,该工程位于市中心繁华区,工程范围包括通风与空调、给水排水及消防水、动力照明、环境与设备监控系统等,建设单位要求A公司严格实施绿色施工,严格进行安全和质量管理。A公司项目部针对工程情况,制定了绿色施工管理和环境保护的
唐某长期利用CORELDraw9软件伪造增值税专用发票,李某固定从唐某处进“货”,批发给赵某,赵某则利用手机短信兜售。假定各犯罪嫌疑人涉案数额(量)均已达到起刑标准,根据刑事法律制度的规定,下列说法正确的有()。
根据民法通则及相关规定,下列关于诉讼时效期间的哪种说法是正确的?
不要用力牵拉幼儿的手臂以防脱臼,这是因为幼儿的()。
根据我国《合同法》的规定,下列合同是无效合同的是()。
下列关于ADSL的描述中,错误的是()。
A、Thegirlwasdisgustedwithhispoverty.B、Thegirl’sfamilywereopposedtotheirmarriage.C、Hefeltsorryforhisterrible
最新回复
(
0
)