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

admin2017-04-28 82

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

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

1901一1939年间美国历届政府在国内经济活动中职能作用的演变。

中华人民共和国恢复了在联合国合法席位的时间是()。

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

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

在平衡二叉树中的每个结点上增设一个Lsize域，其值为它的左子树中的结点个数加1，试写一个时间复杂度为O(logn)的算法，确定树中第k个结点的位置。

设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1则T中的叶子数是()。

患者，40岁。右耳垂下肿物5年，生长缓慢，无痛。检查：肿物以耳垂为中心，界限清楚，活动，呈椭圆形，表面呈结节状，硬度中等。该患者最可能的临床诊断是右侧腮腺

女，24岁。停经45d，诊断为早期妊娠。在行负压吸宫术时，突然出现面色苍白、出汗、头晕、胸闷，体检血压80／50mmHg，心率40／min。最可能的诊断是

使胃蛋白酶原转变为胃蛋白酶的激活物是()。

斜井表土段如为粘结性土层时，其暗挖的方法宜采用()。

下列无形资产不得计算摊销在企业所得税前扣除的是()。

在计算机中，算法是指()

在关系运算中，投影运算的含义是()。

关于汇编语言程序（）。