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

admin2017-04-28 35

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

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

下列对第三次科技革命推动了国际经济格局调整的叙述，不正确的是()。

美国主张建立国际联盟的主要目的是()。

热月党人打击复辟活动，维护革命成果的著名战役是()。

1951年底到1952年春，中国共产党在党政机构工作人员中开展运动的内容是()。

毛泽东明确提出“中国革命斗争的胜利要靠中国同志了解中国情况”论断的著作是()。

全国高校院系调整的具体时间是()。

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

若某浮点机基数为4，尾数采用补码表示，则该浮点机的规格化尾数形式为()。

面部位于瞳孔直下的腧穴是

患者，男，45岁。发现阴囊包块，透光试验阴性，平卧后消失。该患者最可能的诊断是

在一个较长时期中，不规则波动的随机因素往往可以相互抵消。()

对实行配额管理的限制出口货物，出口配额申请人应当在每年11月1日至11月15日提出下一年度出口配额的申请。()

证券经纪人从事客户招揽和客户服务等活动，应当()。Ⅰ．遵守法律、行政法规Ⅱ．遵守监管机构和行政管理部门的规定Ⅲ．自觉接受所服务的证券公司的管理Ⅳ．向客户充分提示证券投资的风险

“发现法”要有一定的知识经验储备，要求学生有相当的思考力，因而不太适用于低年级教学．()

马克思主义中国化历史过程产生了两大理论成果—毛泽东思想和中国特色社会主义理论体系。这两大理论成果之间的关系是()

在Applet的关键方法中，下列哪个方法是关闭浏览器以释放Applet占用的所有资源?

最近

IfinallygotthejobIdreamedabout.Neverinallmylife______sohappy.