【GoLang】【算法模板】2、GoLang 算法模板整理
文章目录
- 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(n+m) O(n+m) 的。性能大大提升。
模板题:
- [Ekmp] lc28. 实现 strStr()(kmp+字符串哈希)
进阶题:
- [kmp] aw141. 周期(kmp循环节+模板题)
以:[Ekmp] lc28. 实现 strStr()(kmp+字符串哈希) 为例题。
这里将 kmp 板子稍微改良了下,固定返回一个 []int,且必定有元素:
- 一个元素
- 为 -1 时,说明没有匹配。
- 不为 -1 时,为正常的在 s 串中的第一次匹配下标位置。
- 多个元素
- s 串与 p 串有多个匹配子串,为 这些位置的 s 串下标位置。
细节:
- s、p 都需要添加 左哨兵,为空字符串。
- ne 数组求解时,i 需要从 i=2 开始匹配。
func getNe(p string) []int {m := len(p)ne := make([]int, m + 1)p = " " + p// 注意,这里 i 需要从实际的第二个字符开始才对,// 从第一个字符开始时 p[i] == p[j+1] --》p[1]=p[0+1] 将成立,并不是一个严格的当前字符相等的关系// 建立的 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]
}
相关文章:
【GoLang】【算法模板】2、GoLang 算法模板整理
文章目录 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 的算法板子,作为备忘录使用。可能有些板子、博…...
合理建模--最短路径
这道题目难就难在如何想到用最短路径来做 主要是这个题目不能用bfs来写,因为距离并不是1 狄克斯特拉算法很久没写了,有些地方生疏了 且这个题目需要记录三个信息,得用tuple 题目地址 int dx[] {0,0,1,-1};int dy[] {1,-1,0,0}; class Solut…...
喜报!博睿数据案例获经观传媒“2024年度数字转型创新案例”!
本文已在“经观”APP中发表,点击下方文章链接查看原文: 2024科技创变纪:创新破局 变量启新 近日,经济观察报“2024年度卓越创新实践案例”榜单评选结果正式公布。博睿数据选送的案例“从零到一:可观测体系建设的探索…...
基于图扑 HT 可视化技术打造智慧地下采矿可视化方案
在前端开发领域,不断涌现的新技术为各行业带来了创新变革的可能。今天,让我们聚焦于图扑软件自研的 HT for Web 产品,看看它如何在前端 2D、3D 渲染方面发力,为智慧地下采矿可视化打造令人惊叹的解决方案,为开发者开启…...
深度学习(2)-深度学习关键网络架构
关键网络架构 深度学习有4种类型的网络架构:密集连接网络、卷积神经网络、循环神经网络和Transformer。每种类型的模型都是针对特定的输入模式,网络架构包含了关于数据结构的假设,即模型搜索的假设空间。某种架构能否解决某个问题࿰…...
【学习笔记】Cadence电子设计全流程(二)原理图库的创建与设计(8-15)
【学习笔记】Cadence电子设计全流程(二)原理图库的创建与设计(下) 2.8 Cadence 软件自带元件库2.9 原理图元器件关联PCB2.10 原理图元器件库的移植2.11 已有原理图输出元器件库2.12 原理图设计中调用元器件库2.13 原理图元器件库关…...
【Linux网络编程】IP协议格式,解包步骤
目录 解析步骤 1.版本字段(大小:4比特位) 2.首部长度(大小:4比特位)(单位:4字节) 🍜细节解释: 3.服务类型(大小:8比特…...
给老系统做个安全检查——Burp SqlMap扫描注入漏洞
背景 在AI技术突飞猛进的今天,类似Cursor之类的工具已经能写出堪比大部分程序员水平的代码了。然而,在我们的代码世界里,仍然有不少"老骥伏枥"的系统在兢兢业业地发光发热。这些祖传系统的代码可能早已过时,架构可能岌…...
Windows 快速搭建C++开发环境,安装C++、CMake、QT、Visual Studio、Setup Factory
安装C 简介 Windows 版的 GCC 有三个选择: CygwinMinGWmingw-w64 Cygwin、MinGW 和 mingw-w64 都是在 Windows 操作系统上运行的工具集,用于在 Windows 环境下进行开发和编译。 Cygwin 是一个在 Windows 上运行的开源项目,旨在提供类Uni…...
开源免费文档翻译工具 可支持pdf、word、excel、ppt
项目介绍 今天给大家推荐一个开源的、超实用的免费文档翻译工具(DeeplxFile),相信很多人都有需要翻译文档的时刻,这款工具就能轻松解决你的需求。 它支持多种文档格式翻译,包括 Word、PDF、PPT、Excel ,使…...
从CNN到Transformer:遥感影像目标检测的未来趋势
文章目录 前言专题一、深度卷积网络知识专题二、PyTorch应用与实践(遥感图像场景分类)专题三、卷积神经网络实践与遥感影像目标检测专题四、卷积神经网络的遥感影像目标检测任务案例【FasterRCNN】专题五、Transformer与遥感影像目标检测专题六、Transfo…...
【GORM学习笔记】GORM介绍以及增删改查相关操作
优缺点 优点:提高开发效率,防止SQL注入、对不熟悉SQL语句的人友好、代码统一缺点:牺牲执行能力、牺牲灵活性、弱化SQL能力 在一些小型项目上使用ORM可以大大提高开发效率,但是在一些对性能要求高得场景下,ORM可能没有…...
WebSocket在分布式环境中的局限性及解决方案
WebSocket 在分布式环境中存在一些局限性,特别是当系统需要扩展多个服务实例时,单个 WebSocket 连接的管理和消息推送就变得比较复杂。因此,必须采取一些额外的措施来确保 WebSocket 能在多个服务实例之间正确工作。 WebSocket 在分布式环境…...
SIM盾构建安全底座的可行性分析
一、背景 1.1安全需求现状 在数字化时代,信息安全面临着日益严峻的挑战。各类网络攻击手段层出不穷,如数据泄露、恶意软件攻击、网络诈骗等,给个人、企业和社会带来了巨大的损失。为了保障信息系统的安全性,需要构建一个可靠的安…...
【Java八股文】10-数据结构与算法面试篇
【Java八股文】10-数据结构与算法面试篇 数据结构与算法面试题数据结构红黑树说一下跳表说一下?LRU是什么?如何实现?布隆过滤器怎么设计?时间复杂度? 排序算法排序算法及空间复杂度 数据结构与算法面试题 数据结构 红…...
go 并发 gorouting chan channel select Mutex sync.One
goroutine // head: 前缀 index:是一个int的指针 func print(head string, index *int) {for i : 0; i < 5; i {// 指针对应的int *indexfmt.Println(*index, head, i)// 暂停1stime.Sleep(1 * time.Second)} }/* Go 允许使用 go 语句开启一个新的运…...
亲测Windows部署Ollama+WebUI可视化
一. Ollama下载 登录Ollama官网(Ollama)点击Download进行下载 如果下载很慢可用以下地址下载: https://github.com/ollama/ollama/releases/download/v0.5.7/OllamaSetup.exe 在DeepSeek官网上,你可以直接点击【model】 到达这个界面之后,…...
linux 安装启动zookeeper全过程及遇到的坑
1、下载安装zookeeper 参考文章:https://blog.csdn.net/weixin_48887095/article/details/132397448 2、启动失败 1、启动失败JAVA_HOME is not set and java could not be found in PATH 已安装 JAVA 配置了JAVA_HOME,还是报错解决方法:参考…...
策略模式Spring框架下开发实例
策略类Spring框架下开发实例 先列出策略模式下需要那些类: 策略接口 (Strategy),定义所有策略类必须遵循的行为。 具体策略类(如 ConcreteStrategyA、ConcreteStrategyB),实现不同的算法或行为。 上下文类 (Context),…...
DeepSeek模型量化
技术背景 大语言模型(Large Language Model,LLM),可以通过量化(Quantization)操作来节约内存/显存的使用,并且降低了通讯开销,进而达到加速模型推理的效果。常见的就是把Float16的浮…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
前端高频面试题2:浏览器/计算机网络
本专栏相关链接 前端高频面试题1:HTML/CSS 前端高频面试题2:浏览器/计算机网络 前端高频面试题3:JavaScript 1.什么是强缓存、协商缓存? 强缓存: 当浏览器请求资源时,首先检查本地缓存是否命中。如果命…...
解析两阶段提交与三阶段提交的核心差异及MySQL实现方案
引言 在分布式系统的事务处理中,如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议(2PC)通过准备阶段与提交阶段的协调机制,以同步决策模式确保事务原子性。其改进版本三阶段提交协议(3PC…...
热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁
赛门铁克威胁猎手团队最新报告披露,数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据,严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能,但SEMR…...
基于江科大stm32屏幕驱动,实现OLED多级菜单(动画效果),结构体链表实现(独创源码)
引言 在嵌入式系统中,用户界面的设计往往直接影响到用户体验。本文将以STM32微控制器和OLED显示屏为例,介绍如何实现一个多级菜单系统。该系统支持用户通过按键导航菜单,执行相应操作,并提供平滑的滚动动画效果。 本文设计了一个…...
内窥镜检查中基于提示的息肉分割|文献速递-深度学习医疗AI最新文献
Title 题目 Prompt-based polyp segmentation during endoscopy 内窥镜检查中基于提示的息肉分割 01 文献速递介绍 以下是对这段英文内容的中文翻译: ### 胃肠道癌症的发病率呈上升趋势,且有年轻化倾向(Bray等人,2018&#x…...
云原生时代的系统设计:架构转型的战略支点
📝个人主页🌹:一ge科研小菜鸡-CSDN博客 🌹🌹期待您的关注 🌹🌹 一、云原生的崛起:技术趋势与现实需求的交汇 随着企业业务的互联网化、全球化、智能化持续加深,传统的 I…...
