建设网站美海房地产,全球十大跨境电商平台排行榜前十名,做英语题目的网站,织梦网站程序刚开始的思路#xff0c;先不管效率#xff0c;跑出来再说#xff0c;然后再进行优化。然后就有了下面的暴力代码#xff1a;
func lengthOfLongestSubstring(s string) int {// count 用来记录当前最长子串长度var count int// flag 用来对下面两个 if 语句分流var flag …刚开始的思路先不管效率跑出来再说然后再进行优化。然后就有了下面的暴力代码
func lengthOfLongestSubstring(s string) int {// count 用来记录当前最长子串长度var count int// flag 用来对下面两个 if 语句分流var flag int 0// for 对字符串进行遍历for i : 0; i len(s); i {// mark 用来记录当前子串初始为当前遍历遇到的第一个字符mark : string(s[i])// 这个 for 循环用来接着 mark 往后遍历如果遇到的字符不在 mark 里就往 mark 后面接for j : i 1; j len(s); j {// strings.Contain(A string, B string) 用来判断 A 中是否有 B有返回 true, 没有返回 falseif strings.Contains(mark, string(s[j])) true {// 有的话就 break, 当前是一个完整的无重复子串再往后接就重复了break}if strings.Contains(mark, string(s[j])) false {// 没有说明还能接着往后接就继续遍历mark string(s[j])}}if flag 0 {// flag 0 表示这是该字符串遇到的第一个无重复子串把长度记录下来count len(mark)flag 1} else if flag 1 {// flag 1 表示这以及不是第一个子串了那么就计算当前无重复子串的长度// 和原先比较更长的话就重新赋值给 count, 否则就不重新赋值if count len(mark) {count len(mark)}}}return count
}跑是跑出来了时间 300ms (仅超过 5% 用户)内存 6.44MB (仅超过 7% 用户)那我得优化以下。我寻思能不能用字符指针让源代码减少一个 for 循环emmm 然后我就开始写代码但是我发现指针并不能减少一个 for 循环因为始终需要一个 for 来遍历子串起始位置另一个 for 用来移动指针写都写了就上代码吧
package mainimport (fmtstringsunsafe
)func lengthOfLongestSubstring(s string) int {// 先将字符串变成字符数组采用用指针遍历bytes : []byte(s)// 定义字符指针var bytePtr *byte// flag 和 count 的作用上一版程序说过了不赘述var flag int 0var count intfor i : 0; i len(s); i {mark : string(s[i])for j : i 1; j len(s); j {// 指针指向 bytes[j] 位置的元素// golang 这种字符指针很麻烦必须用 unsafe.Pointer() 进行转换bytePtr (*byte)(unsafe.Pointer(bytes[j]))if strings.Contains(mark, string(*bytePtr)) false {// 如果该字符不在前面的子串中则加入mark string(*bytePtr)// 指针后移一位bytePtr (*byte)(unsafe.Pointer(uintptr(unsafe.Pointer(bytePtr)) 1))}if strings.Contains(mark, string(*bytePtr)) true {break}}if flag 0 {count len(mark)flag 1} else if flag 1 {if count len(mark) {count len(mark)}}}return count
}func main() {var s pwwkewfmt.Println(lengthOfLongestSubstring(s))
}笑死了时间 216ms (仅超过 5.84% 用户)内存 6.46MB (仅超过 6.98% 用户)几乎没有优化。我想着看看大佬都是怎么写的吧。发现大佬用的是滑动窗口确实酷来个大佬讲解视频的链接 点这里跳转然后下面是代码看不懂的朋友可以进行单步调试我是边调边画图理解的。该程序运行时间 0ms占用内存 2.26MB 比我原方案效率高太多了妙不可言。
package mainimport (fmt
)func lengthOfLongestSubstring(s string) (ans int) {window : [128]bool{} // 也可以用 map这里为了效率用的数组left : 0for right, c : range s {for window[c] { // 加入 c 后窗口内会有重复元素window[s[left]] falseleft}window[c] trueans max(ans, right-left1) // 更新窗口长度最大值}return
}func max(a, b int) int {if b a {return b}return a
}func main() {var s pwwkewfmt.Println(lengthOfLongestSubstring(s))
}
