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

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

admin2017-04-28  41
问题 给定一字符串，该字符串中存在若干对相同的字符，设计一个在时间和空间上尽可能高效的算法，找出一对相同字符在该字符串中的最大距离。例如：“KLabcLdecL”，其中第一个“L”和最后一个“L”相距最远，它们在原字符串中的位置相差8，要求：
给出算法的基本设计思想。
选项
答案基本设计思想：在遍历字符数组的过程中，对已经访问过的字符进行标记，同时记下它们第一次出现在原字符串中的位置，当以后再次遍历到此字符时，根据当前的位置和第一次出现的位置，求出它们之间的距离，然后用得到的距离和当前最大距离相比较。为此需要设置一个数组用来存放已经访问过的字符，为了能加快搜索，采用字符的ASCⅡ码作为数组的下标来支持随机访问，通过对应下标中的数组元素的访问标记is_access来判断它是否被访问过，另外还要获取它第一次出现的位置，很明显这里的数组元素应设置为结构体类型，每遍历一个字符就开始判断，并更新最大距离。
解析
转载请注明原文地址:https://kaotiyun.com/show/yXRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)