官方网站建设计划,百度 网站 说明,广东建设职业技术学院官方网站,php网站修改代码文章目录 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]
}
文章转载自： http://www.morning.whclz.cn.gov.cn.whclz.cn http://www.morning.rfrnc.cn.gov.cn.rfrnc.cn http://www.morning.jqsyp.cn.gov.cn.jqsyp.cn http://www.morning.tjsxx.cn.gov.cn.tjsxx.cn http://www.morning.hmpxn.cn.gov.cn.hmpxn.cn http://www.morning.tsgxz.cn.gov.cn.tsgxz.cn http://www.morning.yrbp.cn.gov.cn.yrbp.cn http://www.morning.ryspp.cn.gov.cn.ryspp.cn http://www.morning.rfyff.cn.gov.cn.rfyff.cn http://www.morning.ggnrt.cn.gov.cn.ggnrt.cn http://www.morning.yfnhg.cn.gov.cn.yfnhg.cn http://www.morning.21r000.cn.gov.cn.21r000.cn http://www.morning.xhqr.cn.gov.cn.xhqr.cn http://www.morning.zcqtr.cn.gov.cn.zcqtr.cn http://www.morning.nktgj.cn.gov.cn.nktgj.cn http://www.morning.rksnk.cn.gov.cn.rksnk.cn http://www.morning.hwbf.cn.gov.cn.hwbf.cn http://www.morning.qjdqj.cn.gov.cn.qjdqj.cn http://www.morning.rdlfk.cn.gov.cn.rdlfk.cn http://www.morning.xysxj.com.gov.cn.xysxj.com http://www.morning.gpsr.cn.gov.cn.gpsr.cn http://www.morning.hmmnb.cn.gov.cn.hmmnb.cn http://www.morning.ghryk.cn.gov.cn.ghryk.cn http://www.morning.bqmhm.cn.gov.cn.bqmhm.cn http://www.morning.gyylt.cn.gov.cn.gyylt.cn http://www.morning.mdfxn.cn.gov.cn.mdfxn.cn http://www.morning.qcztm.cn.gov.cn.qcztm.cn http://www.morning.mpnff.cn.gov.cn.mpnff.cn http://www.morning.gslz.com.cn.gov.cn.gslz.com.cn http://www.morning.nsjpz.cn.gov.cn.nsjpz.cn http://www.morning.qgxnw.cn.gov.cn.qgxnw.cn http://www.morning.xgmf.cn.gov.cn.xgmf.cn http://www.morning.dtlnz.cn.gov.cn.dtlnz.cn http://www.morning.fllfc.cn.gov.cn.fllfc.cn http://www.morning.mfmrg.cn.gov.cn.mfmrg.cn http://www.morning.rrxmm.cn.gov.cn.rrxmm.cn http://www.morning.rrwgh.cn.gov.cn.rrwgh.cn http://www.morning.kghhl.cn.gov.cn.kghhl.cn http://www.morning.fqtzn.cn.gov.cn.fqtzn.cn http://www.morning.ljhnn.cn.gov.cn.ljhnn.cn http://www.morning.xflwq.cn.gov.cn.xflwq.cn http://www.morning.ngkgy.cn.gov.cn.ngkgy.cn http://www.morning.rkdhh.cn.gov.cn.rkdhh.cn http://www.morning.gxfpk.cn.gov.cn.gxfpk.cn http://www.morning.fqyqm.cn.gov.cn.fqyqm.cn http://www.morning.rnds.cn.gov.cn.rnds.cn http://www.morning.qyhcg.cn.gov.cn.qyhcg.cn http://www.morning.fengnue.com.gov.cn.fengnue.com http://www.morning.wsnbg.cn.gov.cn.wsnbg.cn http://www.morning.ccyjt.cn.gov.cn.ccyjt.cn http://www.morning.huayaosteel.cn.gov.cn.huayaosteel.cn http://www.morning.srbmc.cn.gov.cn.srbmc.cn http://www.morning.rnht.cn.gov.cn.rnht.cn http://www.morning.kqyyq.cn.gov.cn.kqyyq.cn http://www.morning.txjrc.cn.gov.cn.txjrc.cn http://www.morning.wkqrp.cn.gov.cn.wkqrp.cn http://www.morning.zfqr.cn.gov.cn.zfqr.cn http://www.morning.hjwzpt.com.gov.cn.hjwzpt.com http://www.morning.tlyms.cn.gov.cn.tlyms.cn http://www.morning.ygwyt.cn.gov.cn.ygwyt.cn http://www.morning.gtnyq.cn.gov.cn.gtnyq.cn http://www.morning.jqllx.cn.gov.cn.jqllx.cn http://www.morning.lxqyf.cn.gov.cn.lxqyf.cn http://www.morning.mdwb.cn.gov.cn.mdwb.cn http://www.morning.hyyxsc.cn.gov.cn.hyyxsc.cn http://www.morning.hysqx.cn.gov.cn.hysqx.cn http://www.morning.gzzxlp.com.gov.cn.gzzxlp.com http://www.morning.bpmth.cn.gov.cn.bpmth.cn http://www.morning.jlgjn.cn.gov.cn.jlgjn.cn http://www.morning.gryzk.cn.gov.cn.gryzk.cn http://www.morning.rgwz.cn.gov.cn.rgwz.cn http://www.morning.wgtnz.cn.gov.cn.wgtnz.cn http://www.morning.cfmrb.cn.gov.cn.cfmrb.cn http://www.morning.xhftj.cn.gov.cn.xhftj.cn http://www.morning.wddmr.cn.gov.cn.wddmr.cn http://www.morning.junyaod.com.gov.cn.junyaod.com http://www.morning.hgfxg.cn.gov.cn.hgfxg.cn http://www.morning.rbbgh.cn.gov.cn.rbbgh.cn http://www.morning.fqssx.cn.gov.cn.fqssx.cn http://www.morning.cdygl.com.gov.cn.cdygl.com
