Documentation
¶
Index ¶
- func Abs[T Number](x T) T
- func BinarySearch[Number interface{ ... }](left, right Number, check func(i Number) bool) Number
- func KMP(text, patten []rune) (pos []int)
- func KMP2(text, patten []rune) (pos []int)
- func MapKeys[M ~map[K]V, K comparable, V any](m M) (keys []K)
- func MaxPrefix(str []rune) (match []int)
- func MergeSort[T cmp.Ordered](s []T, f func(left, right []T))
- func MergeSortWith[T any](s []T, cmp func(x, y T) int, f func(left, right []T))
- func Sum[S ~[]E, E cmp.Ordered](x S) E
- func ToPtr[T any](v T) *T
- func Unique[T comparable](values []T) []T
- type Number
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func BinarySearch ¶
func BinarySearch[Number interface {
~int | ~int64 | ~uint | ~uint64 | ~float64
}](left, right Number, check func(i Number) bool) Number
BinarySearch 在区间 [left, right) 中二分查找最小的 left, 满足 check(left) == true， 如果未能找到满足条件的 left, 那么将会返回 right 而不是 -1。
定义：check(left-1) == false and check(right) == true.
func KMP ¶
KMP implement Knuth–Morris–Pratt algorithm search pattern from text, return all start positions
kmp 在求 前缀表 / next 数组时，借助了动态规划的思想； 在求模式串的索引位置时，则是贪心的思想。
[前缀函数与 kmp 算法 - OI Wiki](https://oi.wiki/string/kmp) [如何更好地理解和掌握 kmp 算法? - 阮行止的回答](https://www.zhihu.com/question/21923021/answer/1032665486)
func KMP2 ¶
KMP2 前缀函数的运用
给定一个文本 t 和一个字符串 s，我们尝试找到并展示 s 在 t 中的所有出现（occurrence）。 为了简便起见，我们用 n 表示字符串 s 的长度，用 m 表示文本 t 的长度。 我们构造一个字符串 s+#+t，其中 # 为一个既不出现在 s 中也不出现在 t 中的分隔符。
接下来计算该字符串的前缀函数。 现在考虑该前缀函数除去最开始 n+1个值（即属于字符串s和分隔符的函数值）后其余函数值的意义。 根据定义，match[i] 为右端点在且同时为一个前缀的最长真子串的长度，具体到我们的这种情况下， 其值为与的前缀相同且右端点位于的最长子串的长度。由于分隔符的存在，该长度不可能超过 n。 而如果等式 match[i]= n 成立，则意味着 s 完整出现在该位置（即其右端点位于位置i）。
注意该位置的下标是对字符串 s+#+t而言的。 因此如果在某一位置有 match[i]=n 成立，则字符串 s在字符串t的 i - (n-1)-(n+1) = i - 2n处出现。
func MapKeys ¶
func MapKeys[M ~map[K]V, K comparable, V any](m M) (keys []K)
func MaxPrefix ¶
MaxPrefix 前缀表
match[i] 表示在子串 str[:i] 中「真前缀」和「真后缀」一致时的最大长度，「真前缀」/「后前缀」指不包含自身的 前缀/后缀。 或者说在子串 str[:i-1] 中求「前缀」和「后缀」一致时的最大长度
func MergeSort ¶
MergeSort 归并排序
归并排序基于分治思想将数组分段排序后合并，也是一种稳定排序的算法
闭包可用于统计逆序对。 归并填入后才会调用闭包，后续不会再使用入参切片，因此闭包内可以修改入参切片
模板题： LCR170. https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/ LC493. https://leetcode.cn/problems/reverse-pairs/
简单变形： LC2426. https://leetcode.cn/problems/number-of-pairs-satisfying-inequality/
转换题：区间和 -> 前缀和之差 -> 逆序对： LC327. https://leetcode.cn/problems/count-of-range-sum/
func MergeSortWith ¶
MergeSortWith 根据 cmp 函数作归并排序
归并排序基于分治思想将数组分段排序后合并，也是一种稳定排序的算法
闭包可用于逆序对的拓展题目。 归并填入后才会调用闭包，后续不会再使用入参切片，因此闭包内可以修改入参切片
带索引排序： LC315. https://leetcode.cn/problems/count-of-smaller-numbers-after-self
func Unique ¶
func Unique[T comparable](values []T) []T
Source Files
Directories