给定一字符串，该字符串中存在若干对相同的字符，设计一个在时间和空间上尽可能高效的算法，找出一对相同字符在该字符串中的最大距离。例如：“KLabcLdecL”，其中第一个“L”和最后一个“L”相距最远，它们在原字符串中的位置相差8，要求：给出算法的基本设

admin2017-04-28 75

问题给定一字符串，该字符串中存在若干对相同的字符，设计一个在时间和空间上尽可能高效的算法，找出一对相同字符在该字符串中的最大距离。例如：“KLabcLdecL”，其中第一个“L”和最后一个“L”相距最远，它们在原字符串中的位置相差8，要求：
给出算法的基本设计思想。

选项

答案基本设计思想：在遍历字符数组的过程中，对已经访问过的字符进行标记，同时记下它们第一次出现在原字符串中的位置，当以后再次遍历到此字符时，根据当前的位置和第一次出现的位置，求出它们之间的距离，然后用得到的距离和当前最大距离相比较。为此需要设置一个数组用来存放已经访问过的字符，为了能加快搜索，采用字符的ASCⅡ码作为数组的下标来支持随机访问，通过对应下标中的数组元素的访问标记is_access来判断它是否被访问过，另外还要获取它第一次出现的位置，很明显这里的数组元素应设置为结构体类型，每遍历一个字符就开始判断，并更新最大距离。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/yXRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

荷马时代的社会管理制度和经济生活。

试述卡德纳斯改革的背景、内容、性质和意义。

斯大林模式的突出特点是()。

1925年爆发的当时世界上罢工时间最长的一次斗争是()。

中国共产党召开七届二中全会的主要目的是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=

检查患者的牙齿是否是对刃时，患者的下颌应该处于下列何种位置

用力矩分配法分析图15—4一12所示结构，先锁住节点B，然后再放松，则传递到C处的弯矩为()。[2013年真题]

我国1962年后开始形成的经济协作区包括西南区、华东区、中南区、()。

我国现行的城市规划编制体系可以划分为()。

矿业工程是大型综合性建设项目，除了生产系统复杂外，还具有()的特点。

下列等式中，不正确的是(　　)。

以自己为交易对象，进行不转移所有权的自买自卖，影响证券交易价格或者证券交易量的行为，在《证券法》上称为()。

()是指以当事人的意志为转移，能够引起劳动法律关系产生、变更和消灭，具有一定法律后果的活动。

Currently,theabilitytounderstandothersandcommunicateeffectivelywithothersisconsiderablyneglectedbymanybecausemo

计算机408

学硕统考专业

荷马时代的社会管理制度和经济生活。

试述卡德纳斯改革的背景、内容、性质和意义。

斯大林模式的突出特点是()。

1925年爆发的当时世界上罢工时间最长的一次斗争是()。

中国共产党召开七届二中全会的主要目的是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

现有一个解决无向连通图的最小生成树的一种方法如下：将图中所有边按权重从大到小排序为(el，e2，…，em)；i=1；while(所剩边数>=顶点数){从图中删去ei；若图不再连通。则恢复ei；i=

检查患者的牙齿是否是对刃时，患者的下颌应该处于下列何种位置

用力矩分配法分析图15—4一12所示结构，先锁住节点B，然后再放松，则传递到C处的弯矩为()。[2013年真题]

我国1962年后开始形成的经济协作区包括西南区、华东区、中南区、()。

我国现行的城市规划编制体系可以划分为()。

矿业工程是大型综合性建设项目，除了生产系统复杂外，还具有()的特点。

下列等式中，不正确的是( )。

以自己为交易对象，进行不转移所有权的自买自卖，影响证券交易价格或者证券交易量的行为，在《证券法》上称为()。

()是指以当事人的意志为转移，能够引起劳动法律关系产生、变更和消灭，具有一定法律后果的活动。

Currently,theabilitytounderstandothersandcommunicateeffectivelywithothersisconsiderablyneglectedbymanybecausemo

下列等式中，不正确的是(　　)。