向大拿们请教一道字符串的题目

题目描述:

给定长度为1048576的字符串,请找到由相同字符组成的最长子字符串的位置。可以确定的是有且只有一个这样的子字符串,它的长度是8192。
你不允许查看字符串的内容。但是你可以调用一个外部函数“ getMaxLength(int startPosition,int endPosition)”,该函数将返回在间隔内找到的最长相同连续字符。

请问大拿们有什么高效的查找方案没有?
十分感谢!
#笔试题目#
全部评论
感觉像是二分+递归
点赞 回复
分享
发布于 2019-12-12 01:16
动规?
点赞 回复
分享
发布于 2019-12-12 10:59
乐元素
校招火热招聘中
官网直投
    static final int LONGEST_STR_LEN = 8192;     public int getLongestStrStartIndex(int l, int r) {         int mid = (l + r) / 2;         if (getMaxLength(l, mid) == LONGEST_STR_LEN) { //最长字符串出现在左边             return getLongestStrStartIndex(l, mid);         }         if (getMaxLength(mid + 1, r) == LONGEST_STR_LEN) {//最长字符串出现在右边             return getLongestStrStartIndex(mid + 1, r);         }         //最长字符串在中间, 剩下的工作是二分找从 l 至 mid 中 getMaxLength最大的下标, 就是最后的答案.         //        |___________|_____________|_______________________________|         //        l     A     B      C     mid                              r         // 先比较 int b = getMaxLength(B, mid) 和 int c = getMatLength(C, mid)         // 如果一样, 说明要的结果在 (c, mid)中间, 继续二分.         // 如果前者大, 比较int a = getMaxLength(A, mid) 和 b, 如果一样大说明结果在(B, C)中间         // 如果 a 大说明结果在(l, B)中间.         return ...;     } 大概还有更好的解法吧.
点赞 回复
分享
发布于 2019-12-12 21:41

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务