当前位置: 首页 > news >正文

【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(nm) 的,这也是为什么工程业务上,不要随便使用的原因。
  • 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 的算法板子&#xff0c;作为备忘录使用。可能有些板子、博…...

合理建模--最短路径

这道题目难就难在如何想到用最短路径来做 主要是这个题目不能用bfs来写&#xff0c;因为距离并不是1 狄克斯特拉算法很久没写了&#xff0c;有些地方生疏了 且这个题目需要记录三个信息&#xff0c;得用tuple 题目地址 int dx[] {0,0,1,-1};int dy[] {1,-1,0,0}; class Solut…...

喜报!博睿数据案例获经观传媒“2024年度数字转型创新案例”!

本文已在“经观”APP中发表&#xff0c;点击下方文章链接查看原文&#xff1a; 2024科技创变纪&#xff1a;创新破局 变量启新 近日&#xff0c;经济观察报“2024年度卓越创新实践案例”榜单评选结果正式公布。博睿数据选送的案例“从零到一&#xff1a;可观测体系建设的探索…...

基于图扑 HT 可视化技术打造智慧地下采矿可视化方案

在前端开发领域&#xff0c;不断涌现的新技术为各行业带来了创新变革的可能。今天&#xff0c;让我们聚焦于图扑软件自研的 HT for Web 产品&#xff0c;看看它如何在前端 2D、3D 渲染方面发力&#xff0c;为智慧地下采矿可视化打造令人惊叹的解决方案&#xff0c;为开发者开启…...

深度学习(2)-深度学习关键网络架构

关键网络架构 深度学习有4种类型的网络架构&#xff1a;密集连接网络、卷积神经网络、循环神经网络和Transformer。每种类型的模型都是针对特定的输入模式&#xff0c;网络架构包含了关于数据结构的假设&#xff0c;即模型搜索的假设空间。某种架构能否解决某个问题&#xff0…...

【学习笔记】Cadence电子设计全流程(二)原理图库的创建与设计(8-15)

【学习笔记】Cadence电子设计全流程&#xff08;二&#xff09;原理图库的创建与设计&#xff08;下&#xff09; 2.8 Cadence 软件自带元件库2.9 原理图元器件关联PCB2.10 原理图元器件库的移植2.11 已有原理图输出元器件库2.12 原理图设计中调用元器件库2.13 原理图元器件库关…...

【Linux网络编程】IP协议格式,解包步骤

目录 解析步骤 1.版本字段&#xff08;大小&#xff1a;4比特位&#xff09; 2.首部长度&#xff08;大小&#xff1a;4比特位&#xff09;&#xff08;单位&#xff1a;4字节&#xff09; &#x1f35c;细节解释&#xff1a; 3.服务类型&#xff08;大小&#xff1a;8比特…...

给老系统做个安全检查——Burp SqlMap扫描注入漏洞

背景 在AI技术突飞猛进的今天&#xff0c;类似Cursor之类的工具已经能写出堪比大部分程序员水平的代码了。然而&#xff0c;在我们的代码世界里&#xff0c;仍然有不少"老骥伏枥"的系统在兢兢业业地发光发热。这些祖传系统的代码可能早已过时&#xff0c;架构可能岌…...

Windows 快速搭建C++开发环境,安装C++、CMake、QT、Visual Studio、Setup Factory

安装C 简介 Windows 版的 GCC 有三个选择&#xff1a; CygwinMinGWmingw-w64 Cygwin、MinGW 和 mingw-w64 都是在 Windows 操作系统上运行的工具集&#xff0c;用于在 Windows 环境下进行开发和编译。 Cygwin 是一个在 Windows 上运行的开源项目&#xff0c;旨在提供类Uni…...

开源免费文档翻译工具 可支持pdf、word、excel、ppt

项目介绍 今天给大家推荐一个开源的、超实用的免费文档翻译工具&#xff08;DeeplxFile&#xff09;&#xff0c;相信很多人都有需要翻译文档的时刻&#xff0c;这款工具就能轻松解决你的需求。 它支持多种文档格式翻译&#xff0c;包括 Word、PDF、PPT、Excel &#xff0c;使…...

从CNN到Transformer:遥感影像目标检测的未来趋势

文章目录 前言专题一、深度卷积网络知识专题二、PyTorch应用与实践&#xff08;遥感图像场景分类&#xff09;专题三、卷积神经网络实践与遥感影像目标检测专题四、卷积神经网络的遥感影像目标检测任务案例【FasterRCNN】专题五、Transformer与遥感影像目标检测专题六、Transfo…...

【GORM学习笔记】GORM介绍以及增删改查相关操作

优缺点 优点&#xff1a;提高开发效率&#xff0c;防止SQL注入、对不熟悉SQL语句的人友好、代码统一缺点&#xff1a;牺牲执行能力、牺牲灵活性、弱化SQL能力 在一些小型项目上使用ORM可以大大提高开发效率&#xff0c;但是在一些对性能要求高得场景下&#xff0c;ORM可能没有…...

WebSocket在分布式环境中的局限性及解决方案

WebSocket 在分布式环境中存在一些局限性&#xff0c;特别是当系统需要扩展多个服务实例时&#xff0c;单个 WebSocket 连接的管理和消息推送就变得比较复杂。因此&#xff0c;必须采取一些额外的措施来确保 WebSocket 能在多个服务实例之间正确工作。 WebSocket 在分布式环境…...

SIM盾构建安全底座的可行性分析

一、背景 1.1安全需求现状 在数字化时代&#xff0c;信息安全面临着日益严峻的挑战。各类网络攻击手段层出不穷&#xff0c;如数据泄露、恶意软件攻击、网络诈骗等&#xff0c;给个人、企业和社会带来了巨大的损失。为了保障信息系统的安全性&#xff0c;需要构建一个可靠的安…...

【Java八股文】10-数据结构与算法面试篇

【Java八股文】10-数据结构与算法面试篇 数据结构与算法面试题数据结构红黑树说一下跳表说一下&#xff1f;LRU是什么&#xff1f;如何实现&#xff1f;布隆过滤器怎么设计&#xff1f;时间复杂度&#xff1f; 排序算法排序算法及空间复杂度 数据结构与算法面试题 数据结构 红…...

go 并发 gorouting chan channel select Mutex sync.One

goroutine // head&#xff1a; 前缀 index&#xff1a;是一个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进行下载 如果下载很慢可用以下地址下载&#xff1a; https://github.com/ollama/ollama/releases/download/v0.5.7/OllamaSetup.exe 在DeepSeek官网上&#xff0c;你可以直接点击【model】 到达这个界面之后&#xff0c;…...

linux 安装启动zookeeper全过程及遇到的坑

1、下载安装zookeeper 参考文章&#xff1a;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,还是报错解决方法&#xff1a;参考&#xf…...

策略模式Spring框架下开发实例

策略类Spring框架下开发实例 先列出策略模式下需要那些类: 策略接口 (Strategy)&#xff0c;定义所有策略类必须遵循的行为。 具体策略类&#xff08;如 ConcreteStrategyA、ConcreteStrategyB&#xff09;&#xff0c;实现不同的算法或行为。 上下文类 (Context)&#xff0c;…...

DeepSeek模型量化

技术背景 大语言模型&#xff08;Large Language Model&#xff0c;LLM&#xff09;&#xff0c;可以通过量化&#xff08;Quantization&#xff09;操作来节约内存/显存的使用&#xff0c;并且降低了通讯开销&#xff0c;进而达到加速模型推理的效果。常见的就是把Float16的浮…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路

进入2025年以来&#xff0c;尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断&#xff0c;但全球市场热度依然高涨&#xff0c;入局者持续增加。 以国内市场为例&#xff0c;天眼查专业版数据显示&#xff0c;截至5月底&#xff0c;我国现存在业、存续状态的机器人相关企…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

随着互联网技术的飞速发展&#xff0c;消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁&#xff0c;不仅优化了客户体验&#xff0c;还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用&#xff0c;并…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Module Federation 和 Native Federation 的比较

前言 Module Federation 是 Webpack 5 引入的微前端架构方案&#xff0c;允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...

OPENCV形态学基础之二腐蚀

一.腐蚀的原理 (图1) 数学表达式&#xff1a;dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一&#xff0c;腐蚀跟膨胀属于反向操作&#xff0c;膨胀是把图像图像变大&#xff0c;而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...