网站建筑设计,怎样做科普视频网站,娄底网站建设建站,wordpress直接访问站点文章目录 0、前言1、GoLang 算法必会技巧1.1、标准库1.1.1、sort 包1.1.2、slice 包 1.2、数据结构1.2.1、优先队列 2、板子2.1、二分2.1.1、lower_bound、upper_bound 2.2、字符串2.2.1、kmp 0、前言
整理一下 golang 的算法板子#xff0c;作为备忘录使用。可能有些板子、博… 文章目录 0、前言1、GoLang 算法必会技巧1.1、标准库1.1.1、sort 包1.1.2、slice 包 1.2、数据结构1.2.1、优先队列 2、板子2.1、二分2.1.1、lower_bound、upper_bound 2.2、字符串2.2.1、kmp 0、前言
整理一下 golang 的算法板子作为备忘录使用。可能有些板子、博文是引用互联网博主的会注明出处在此多蟹…
1、GoLang 算法必会技巧
1.1、标准库
1.1.1、sort 包
引用
其他博主 [Go语言tips01]浅谈sort包官方库 Go1.24.0-sort 例题
[M二分] lc34. 在排序数组中查找元素的第一个和最后一个位置(二分经典) [M二分] lc2080. 区间内查询数字的频率(模拟二分数据结构Go二分库函数知识总结) sort.SearchInts 练习掌握
1.1.2、slice 包
引用
官方库 Go1.24.0-slice 例题
lc 灵神 —【视频讲解】二分查找总是写不对三种写法一个视频讲透Python/Java/C/C/Go/JS slices.BinarySearch
1.2、数据结构
1.2.1、优先队列
堆这块日后补大根堆、小根堆啥的
2、板子
2.1、二分
整数二分、浮点数二分
其他博主 [Go语言tips01]浅谈sort包官方库 Go1.24.0-sort sort.SearchInts 系列函数 2.1.1、lower_bound、upper_bound
[M二分] lc2080. 区间内查询数字的频率(模拟二分数据结构Go二分库函数知识总结)
func upperBound(pos []int, target int) int {l, r : 0, len(pos)-1for l r {mid : l (r - l) / 2if pos[mid] target {l mid 1} else {r mid - 1}}return l
}func lowerBound(pos []int, target int) int {l, r : 0, len(pos) - 1for l r {mid : l (r - l) / 2if pos[mid] target {l mid 1} else {r mid - 1}}return l
}2.2、字符串
2.2.1、kmp
知识点
[kmp模板] kmp模板哔站讲的非常好的一个老师 - - - 懒猫老师-数据结构-(14)字符串匹配-KMP算法1(模式匹配) 注意
strstr() 函数其时间复杂度是 O ( n ∗ m ) O(n*m) O(n∗m) 的这也是为什么工程业务上不要随便使用的原因。kmp 函数其时间复杂度是 O ( n m ) O(nm) O(nm) 的。性能大大提升。 模板题
[Ekmp] lc28. 实现 strStr()(kmp字符串哈希)
进阶题
[kmp] aw141. 周期(kmp循环节模板题) 以[Ekmp] lc28. 实现 strStr()(kmp字符串哈希) 为例题。
这里将 kmp 板子稍微改良了下固定返回一个 []int且必定有元素
一个元素 为 -1 时说明没有匹配。不为 -1 时为正常的在 s 串中的第一次匹配下标位置。 多个元素 s 串与 p 串有多个匹配子串为 这些位置的 s 串下标位置。 细节
s、p 都需要添加 左哨兵为空字符串。ne 数组求解时i 需要从 i2 开始匹配。
func getNe(p string) []int {m : len(p)ne : make([]int, m 1)p p// 注意这里 i 需要从实际的第二个字符开始才对// 从第一个字符开始时 p[i] p[j1] --》p[1]p[01] 将成立并不是一个严格的当前字符相等的关系// 建立的 ne 数组就是错误的for i, j : 2, 0; i m; i { for j 0 p[i] ! p[j 1] {j ne[j]}if p[i] p[j 1] {j }ne[i] j}return ne
}// 返回所有 s, p 串中的匹配下标构成的切片如果不匹配则返回元素为 -1 的切片
// in: s: sadbutsad p: sad
// out: [0, 6]
// in: s: leetcode p: leeto
// out: [-1]
func kmp(s, p string) []int {ne : getNe(p)n, m : len(s), len(p)s, p s, pmatchs : []int{}for i, j : 1, 0; i n; i {for j 0 s[i] ! p[j 1] {j ne[j]}if s[i] p[j 1] {j }if j m {matchs append(matchs, i - m)j ne[j] // 现在已经找到匹配位置了。下一次开始匹配j 直接跳 ne 数组即可}}if len(matchs) 0 {return []int{-1}}return matchs
}func strStr(s string, p string) int {return kmp(s, p)[0]
}
