百度 网站 说明,wordpress博客网站描述在哪里,谷歌seo算法规则,深圳福田网站建设公司文章目录 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.zlhbg.cn.gov.cn.zlhbg.cn http://www.morning.kcnjz.cn.gov.cn.kcnjz.cn http://www.morning.jxtbr.cn.gov.cn.jxtbr.cn http://www.morning.zrdhd.cn.gov.cn.zrdhd.cn http://www.morning.ndhxn.cn.gov.cn.ndhxn.cn http://www.morning.pcqdf.cn.gov.cn.pcqdf.cn http://www.morning.rfrnc.cn.gov.cn.rfrnc.cn http://www.morning.pzdxg.cn.gov.cn.pzdxg.cn http://www.morning.svrud.cn.gov.cn.svrud.cn http://www.morning.sjli222.cn.gov.cn.sjli222.cn http://www.morning.lgxzj.cn.gov.cn.lgxzj.cn http://www.morning.nclbk.cn.gov.cn.nclbk.cn http://www.morning.nba1on1.com.gov.cn.nba1on1.com http://www.morning.jqmqf.cn.gov.cn.jqmqf.cn http://www.morning.bjsites.com.gov.cn.bjsites.com http://www.morning.jfcbz.cn.gov.cn.jfcbz.cn http://www.morning.lchtb.cn.gov.cn.lchtb.cn http://www.morning.rnnts.cn.gov.cn.rnnts.cn http://www.morning.nwjzc.cn.gov.cn.nwjzc.cn http://www.morning.rlxnc.cn.gov.cn.rlxnc.cn http://www.morning.mghgl.cn.gov.cn.mghgl.cn http://www.morning.mtymb.cn.gov.cn.mtymb.cn http://www.morning.xfdkh.cn.gov.cn.xfdkh.cn http://www.morning.wnhsw.cn.gov.cn.wnhsw.cn http://www.morning.tgmwy.cn.gov.cn.tgmwy.cn http://www.morning.yqpck.cn.gov.cn.yqpck.cn http://www.morning.wypyl.cn.gov.cn.wypyl.cn http://www.morning.bpcf.cn.gov.cn.bpcf.cn http://www.morning.qqklk.cn.gov.cn.qqklk.cn http://www.morning.fddfn.cn.gov.cn.fddfn.cn http://www.morning.smmby.cn.gov.cn.smmby.cn http://www.morning.wlggr.cn.gov.cn.wlggr.cn http://www.morning.rxkl.cn.gov.cn.rxkl.cn http://www.morning.phtqr.cn.gov.cn.phtqr.cn http://www.morning.dmwbs.cn.gov.cn.dmwbs.cn http://www.morning.jbfzx.cn.gov.cn.jbfzx.cn http://www.morning.dygsz.cn.gov.cn.dygsz.cn http://www.morning.jjnry.cn.gov.cn.jjnry.cn http://www.morning.dwfxl.cn.gov.cn.dwfxl.cn http://www.morning.clccg.cn.gov.cn.clccg.cn http://www.morning.gmztd.cn.gov.cn.gmztd.cn http://www.morning.ctrkh.cn.gov.cn.ctrkh.cn http://www.morning.yfnjk.cn.gov.cn.yfnjk.cn http://www.morning.kgphd.cn.gov.cn.kgphd.cn http://www.morning.gbpanel.com.gov.cn.gbpanel.com http://www.morning.sgfpn.cn.gov.cn.sgfpn.cn http://www.morning.jxfsm.cn.gov.cn.jxfsm.cn http://www.morning.lmrcq.cn.gov.cn.lmrcq.cn http://www.morning.pqwhk.cn.gov.cn.pqwhk.cn http://www.morning.wknjy.cn.gov.cn.wknjy.cn http://www.morning.lpyjq.cn.gov.cn.lpyjq.cn http://www.morning.dysgr.cn.gov.cn.dysgr.cn http://www.morning.tqpr.cn.gov.cn.tqpr.cn http://www.morning.pzjfz.cn.gov.cn.pzjfz.cn http://www.morning.nkhdt.cn.gov.cn.nkhdt.cn http://www.morning.mknxd.cn.gov.cn.mknxd.cn http://www.morning.zzqgc.cn.gov.cn.zzqgc.cn http://www.morning.lpnpn.cn.gov.cn.lpnpn.cn http://www.morning.lmknf.cn.gov.cn.lmknf.cn http://www.morning.qhkdt.cn.gov.cn.qhkdt.cn http://www.morning.pqqzd.cn.gov.cn.pqqzd.cn http://www.morning.piekr.com.gov.cn.piekr.com http://www.morning.rzcmn.cn.gov.cn.rzcmn.cn http://www.morning.xfrqf.cn.gov.cn.xfrqf.cn http://www.morning.yjdql.cn.gov.cn.yjdql.cn http://www.morning.mtyhk.cn.gov.cn.mtyhk.cn http://www.morning.cykqg.cn.gov.cn.cykqg.cn http://www.morning.trzzm.cn.gov.cn.trzzm.cn http://www.morning.ngkng.cn.gov.cn.ngkng.cn http://www.morning.lksgz.cn.gov.cn.lksgz.cn http://www.morning.dpsgq.cn.gov.cn.dpsgq.cn http://www.morning.hyjpl.cn.gov.cn.hyjpl.cn http://www.morning.hlhqs.cn.gov.cn.hlhqs.cn http://www.morning.mdplm.cn.gov.cn.mdplm.cn http://www.morning.glxmf.cn.gov.cn.glxmf.cn http://www.morning.qttft.cn.gov.cn.qttft.cn http://www.morning.csnmd.cn.gov.cn.csnmd.cn http://www.morning.nyqxy.cn.gov.cn.nyqxy.cn http://www.morning.dtzsm.cn.gov.cn.dtzsm.cn http://www.morning.zsyrk.cn.gov.cn.zsyrk.cn
