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

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

admin2017-04-28  53
问题 给定一字符串，该字符串中存在若干对相同的字符，设计一个在时间和空间上尽可能高效的算法，找出一对相同字符在该字符串中的最大距离。例如：“KLabcLdecL”，其中第一个“L”和最后一个“L”相距最远，它们在原字符串中的位置相差8，要求：
根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
选项
答案算法实现如下： typedef struct element //定义字符的访问标记和位置信息 { bool is access； //表示该字符是否被访问过 int position； //记录下该字符第一次出现的位置 }array[128]； //字符的ASCⅡ值范围为0～127 int get_max len(char str[]，int n) //n为字符数组的长度 { int max=0； //初始化相同字符间的最大距离 int i=0； while (i＜n) { if（array[str[i]j.is access==false) //如果该字符第一次出现 { array[str[i]].position=i； //记下第一次出现的位置 array[str[i]].is_access=true； //置标记信息为已访问 } else //该字符不是第一次出现 { 1f(i—array[str[i]].position＞=max) //两字符距离比当前最大值大 { max=i—array[str[i]].position； //更新最大值 } } i++； } return max； }
解析
转载请注明原文地址:https://kaotiyun.com/show/8XRi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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