前言:
此时你们对“编写程序查找一个字符串中最长的数字子串”都比较关切,同学们都想要学习一些“编写程序查找一个字符串中最长的数字子串”的相关知识。那么小编同时在网络上汇集了一些对于“编写程序查找一个字符串中最长的数字子串””的相关知识,希望我们能喜欢,兄弟们一起来了解一下吧!2021-06-24:求一个字符串中,最长无重复字符子串长度。
福大大 答案2021-06-24:
方法一:滑动窗口。自然智慧。
不重复的时候,右指针右移;重复的时候,左指针右移。
方法二:求出最右不重复位置。
map:key是值,value是数组序号,初始值value都是-1。
时间复杂度:O(N)。空间复杂度:O(不同字符个数)。
代码用golang编写。代码如下:
package mainimport "fmt"func main() { s := "moonfdd" ret1 := lengthOfLongestSubstring1(s) fmt.Println(ret1) ret2 := lengthOfLongestSubstring2(s) fmt.Println(ret2)}//方法一:滑动窗口。自然智慧。func lengthOfLongestSubstring1(s string) int { // 哈希集合,记录每个字符是否出现过 m := map[byte]int{} n := len(s) // 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动 rk, ans := -1, 0 for i := 0; i < n; i++ { if i != 0 { // 左指针向右移动一格,移除一个字符 delete(m, s[i-1]) } for rk+1 < n && m[s[rk+1]] == 0 { // 不断地移动右指针 m[s[rk+1]]++ rk++ } // 第 i 到 rk 个字符是一个极长的无重复字符子串 ans = getMax(ans, rk-i+1) } return ans}//方法二:求出最右不重复位置。func lengthOfLongestSubstring2(s string) int { if len(s) == 0 { return 0 } indexList := make([]int, 256) for i := 0; i < 256; i++ { indexList[i] = -1 } N := len(s) ans := 0 p := -1 for i := 0; i < N; i++ { p = getMax(p, indexList[s[i]]) ans = getMax(ans, i-p) indexList[s[i]] = i } return ans}func getMax(a int, b int) int { if a > b { return a } else { return b }}func getMin(a int, b int) int { if a > b { return a } else { return b }}
执行结果如下:
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #编写程序查找一个字符串中最长的数字子串