程序员经验分享-hwhale

零散算法

2023-11-16

1、字符串匹配

朴素的串匹配算法：

KMP匹配算法：

2、广度优先搜索BFS

3、深度优先搜索DFS

4、狄克斯特拉算法Dijkstra

5、贪婪算法

6、动态规划

7、安全散列算法SHA

用递归分析问题，基于循环写代码。

10、关于查找算法

（1）遍历（数组、链表、xml）

（2）二分查找（前提有序）

（3）hash表查找：哈希表的特点就是查找效率高，时间复杂度为常数级别 O(1)， 而额外空间复杂度则要高出许多。

hash_table：hash_table这种数据结构在插入，删除，搜寻等操作上也具有常数平均时间，并且不需要依赖于数据的随机性（RB Tree、AVL Tree依赖于数据的随机性）。如果需要存储的数据相比较桶子的个数来说不是很多的情况采用线性探测或二次探测；如果负载系统比较大则采用拉链法。

（4）map容器：对内存大小比较敏感或者数据存储要求有序的话，则可以用 map 容器，map容器是用红黑树实现的，查找效率稍微低一些，复杂度为（logn）。

（5）数据库查找

选择算法时权衡三个因素: 查找速度, 数据量, 内存使用。

lmdb底层原理：mmap文件映射 ，B+树查找

11、平衡点

有序数组可以利用二分查找法快速的查找特定的值，时间复杂度为O(log2N)，但是插入数据时很慢，时间复杂度为O(N)；链表的插入和删除速度都很快，时间复杂度为O(1)，但是查找特定值很慢，时间复杂度为O(N)。有没有一种数据结构既能像有序数组那样快速的查找数据，又能像链表那样快速的插入数据呢？树就能满足这种要求。不过依然是以算法的复杂度为代价。一个程序当它降低了一个方面的复杂度，必然会在其他方面增加复杂度，阴阳互补。

 

参考连接：

https://blog.csdn.net/u012152619/article/details/42059325

12、C实现

所有基础数据结构和算法的纯C语言实现，如各自排序、链表、栈、队列、各种树以及应用、图算法、字符串匹配算法、回溯、并查集等

https://github.com/LeechanX/Data-Structures-and-Algorithms-in-C     

七大查找算法实现：

https://www.cnblogs.com/leezx/p/5719012.html

uthash

http://troydhanson.github.io/uthash/

十大排序算法选择与对比：

https://www.cnblogs.com/panda-ling/p/6705193.html

linux内核哈希链表：https://www.cnblogs.com/wanghetao/archive/2013/04/13/3019156.html

https://blog.csdn.net/hty46565/article/details/53201824

B+树：

B树是一种平衡的多路查找树，在文件系统中主要作为文件的索引。也多用在数据库索引中。因为外存较慢，而且使用二叉树很容易造成频繁的I/O读写，现在可以引入多叉树来改变这种情况的。

https://github.com/KinderRiven/bplus_tree

http://www.srcmini.com/1348.html

https://blog.csdn.net/xiaohusaier/article/details/77101640

Bloom filter

海量数据处理

https://www.cnblogs.com/haippy/archive/2012/07/14/2590669.html

跳跃表

https://blog.csdn.net/daniel_ustc/article/details/20218489

红黑树C实现

https://www.cnblogs.com/skywang12345/p/3624177.html

手动迭代开方

海量数据排序：https://blog.csdn.net/yu487/article/details/86021711

https://blog.csdn.net/zhushuai1221/article/details/51781002

https://blog.csdn.net/FX677588/article/details/72471357

比较排序nlogn证明：https://www.zhihu.com/question/24516934

递归和回溯：https://www.cnblogs.com/brifuture/p/6553665.html

https://blog.csdn.net/yhflyl/article/details/86763197

分治：https://blog.csdn.net/qq_37763204/article/details/79519823

https://blog.csdn.net/qq_39382769/article/details/80788293

动态规划：https://www.jianshu.com/p/86daf14620b1

https://www.cnblogs.com/chihaoyuIsnotHere/p/10138087.html

https://github.com/search?l=C&q=动态规划&type=Repositories

贪婪算法：最短路径问题(广度优先、狄克斯特拉)都属于贪婪算法

https://www.jianshu.com/p/b613ae9d77ff

五大经典算法：https://github.com/jingong/Algorithm

 

递归算法的时间复杂度计算：https://blog.csdn.net/so_geili/article/details/53444816

 

 

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构与算法

零散算法 的相关文章

  • 数据结构中常见的树（BST二叉搜索树、AVL平衡二叉树、RBT红黑树、B-树、B+树、B*树）

    原文 http blog csdn net sup heaven article details 39313731 数据结构中常见的树 BST二叉搜索树 AVL平衡二叉树 RBT红黑树 B 树 B 树 B 树 转载 2014年09月16日

  • 将二叉树转为有序的双向链表

    一 题目要求 输入一棵二叉排序树 现在要将该二叉排序树转换成一个有序的双向链表 而且在转换的过程中 不能创建任何新的结点 只能调整树中的结点指针的指向来实现 include

  • 直线检测方法—LSD论文翻译

    附原文链接 LSD a Line Segment Detector 摘 要 LSD是一个线段检测器 能够在线性时间内得到亚像素级精度的检测结果 它无需调试参数就可以适用于任何数字图像上 并且能够自我控制错误数量的检测 平均来说 一个图像中允

  • 一文弄懂循环链表、双向链表、静态链表

    循环链表 双向链表 静态链表 三遍定律 理解了单链表本文的理解易如反掌 单链表请点击这里 理解了单链表本文的理解易如反掌 单链表请点击这里 理解了单链表本文的理解易如反掌 单链表请点击这里 1 循环链表 将单链表中终端结点的指针端由空指针改

  • (笔试前准备)字符串匹配算法总结

    我想说一句 我日 我讨厌KMP KMP虽然经典 但是理解起来极其复杂 好不容易理解好了 便起码来巨麻烦 老子就是今天图书馆在写了几个小时才勉强写了一个有bug的 效率不高的KMP 特别是计算next数组的部分 其实 比KMP算法速度快的算法

  • PCL—低层次视觉—点云分割（RanSaC）

    点云分割 点云分割可谓点云处理的精髓 也是三维图像相对二维图像最大优势的体现 不过多插一句 自Niloy J Mitra教授的Global contrast based salient region detection出现 最优分割到底鹿死

  • findBug 错误修改指南

    FindBugs错误修改指南 1 EC UNRELATED TYPES Bug Call to equals comparing different types Pattern id EC UNRELATED TYPES type EC c

  • 链表和线性表的优缺点

    链表和线性表的优缺点 作为我们最先接触的两个数据结构 链表和线性表的优缺点都较为明显 并且二者互相补足 文章目录 链表和线性表的优缺点 线性表 线性表的组成 线性表的缺点 线性表的优点 链表 链表的组成 链表的优点 链表的缺点 总结 线性表

  • 逆波兰表达式求值（C语言实现）

    实验项目 从文本文件输入任意一个语法正确的 中缀 表达式 显示并保存该表达式 利用栈结构 把上述 中缀 表达式转换成后缀表达式 并显示栈的状态变化过程和所得到的后缀表达式 利用栈结构 对上述后缀表达式进行求值 并显示栈的状态变化过程和最终结

  • SDUT--OJ《数据结构与算法》实践能力专题训练6 图论

    A 数据结构实验之图论一 基于邻接矩阵的广度优先搜索遍历 Description 给定一个无向连通图 顶点编号从0到n 1 用广度优先搜索 BFS 遍历 输出从某个顶点出发的遍历序列 同一个结点的同层邻接点 节点编号小的优先遍历 Input

  • 循环单链表（C语言版）

    前言 小可爱们 本次一起来看看循环单链表吧 嘻嘻 一 循环单链表的定义 循环单链表是单链表的另一种形式 其结构特点链表中最后一个结点的指针域不再是结束标记 而是指向整个链表的第一个结点 从而使链表形成一个环 和单链表相同 循环链表也有带头结

  • 如何根据链表节点数据大小对链表节点进行排序

    对链表排序有两种方法 1 比较了两个节点的大小后 对指针进行改变 从而交换节点的顺序 2 比较了两个节点的大小后 只交换数据域 而不改变指针 从而交换节点的顺序 第二种办法比较简单 本文主要对第二种方法进行讲解 链表节点排序算法 采用 冒泡

  • 数据结构小白之插入排序算法

    1 插入排序 1 1 思路 将n个需要排序的元素看成两个部分 一个是有序部分 一个是无序部分 开始的时候有序表只有一个元素 无序表有n 1个元素 排序过程中每次从无序表中取出元素 然后插入到有序表的适当位置 从而成为新的有序表 类似排队 如

  • Python 实现列队

    1 列队定义 队列是项的有序结合 其中添加新项的一端称为队尾 移除项的一端称为队首 当一个元素从队尾进入队列时 一直向队首移动 直到它成为下一个需要移除的元素为止 最近添加的元素必须在队尾等待 集合中存活时间最长的元素在队首 这种排序成为

  • 数据结构之图的两种遍历实现（C语言版）

    上一期文章分享完了图的两种遍历方式 也是两种很重要的算法 DFS和BFS 这两种算法的应用和重要性我就不多说了 内行的人懂的都懂 今天这文章重要就是来上机实现这两种算法 又由于这两种算法都可以由邻接矩阵和邻接表来表示 博主分享的代码都是上机

  • CRC校验（二）

    CRC校验 二 参考 https blog csdn net liyuanbhu article details 7882789 https www cnblogs com esestt archive 2007 08 09 848856

  • Linux下进程退出的几种形式

    进程退出 Linux 下进程的退出分为正常退出和异常退出两种 1 正常退出 a 在main 函数中执行return b 调用exit 函数 c 调用 exit 函数 2 异常退出 a 调用about函数 b 进程收到某个信号 而该信号使程序

  • C++ AVL树(四种旋转,插入)

    C AVL树 四种旋转 插入 一 AVL树的概念及性质 二 我们要实现的大致框架 1 AVL树的节点定义 2 AVL树的大致框架 三 插入 1 插入逻辑跟BST相同的那一部分 2 修改平衡因子

  • 排序：计数排序

    一 概念 计数排序是非比较排序 是对哈希直接定址法的变形应用 二 思想 利用数组统计相同数据出现的次数 例如整型数据m出现n次 就在数组m位置记录数据为n 最后从头遍历数组打印数据即可 通俗来讲就是 数组下标即为数据 下标所指位置的值即为数

  • 最大流-Dinic算法，原理详解，四大优化，详细代码

    文章目录 零 前言 一 概念回顾 可略过 1 1流网络 1 2流 1 3最大流 1 4残留网络 1 5增广路

随机推荐

  • 小程序iOS兼容问题总结

    1 IOS 上 JS 只支持 new Date YYYY MM DD 这一种格式 YYYY MM DD 等格式都不支持

  • Raft 一致性算法

    文章目录 1 CAP 定理 1 Raft 基本概念 2 Raft 算法核心 2 1 Leader 选举 2 2 日志复制 3 总结 1 CAP 定理 文章参考 lt 零声教育 gt 的C C linux服务期高级架构系统教程学习 服务器高级

  • POI框架导出EXCEL的简单列子（跨行跨列）合并单元格

    public static void main String args throws IOException try HSSFWorkbook wb new HSSFWorkbook HSSFSheet sheet wb createShe

  • 十八. Kubernetes Ingress

    目录 一 Ingress 基础解释 二 ingressController 安装 六 ingress 使用示例 pathType 详细 annotations 基于k8s注解为 nginx 添加功能示例 路径重写 Session Affin

  • （二）selenium IDE 插件下载与安装

    前面selenium已经下载安装成功 接下来尝试录制下脚本 此时有个IDE插件是必备的 1 下载Chrome插件 进入网址 https www extfans com 搜索 selenium IDE 然后下载 2 安装插件 打开Chrome

  • plsql 返回结果集的存储过程

    返回结果集的存储过程 1 创建一个包 在该包中定义了一个游标类型test corsor create or replace package testpackage as type test cursor is ref cursor end

  • Linux内核自带SPI设备驱动测试程序分析：spidev_test.c

    在Linux系统中 SPI 的用户模式设备接口的驱动源码位于 drivers spi spidev c 在应用层生成 dev spidev 的节点 可以通过 read write 达到与硬件设备的 SPI 通信 下面介绍spidev驱动移植

  • js获取当前月、上一月和下一月

    获得当前月 function getNowMonth var date new Date var year date getFullYear var month date getMonth 1 month month gt 9 month

  • K8S 基础概念学习

    1 K8S 通过Deployment 实现滚动发布 比如左边的ReplicatSet 的 pod 中 是V1版本的镜像 Deployment通过 再启动一个 ReplicatSet 中启动 pod中 镜像就是V2 2 每个pod 中都有一个

  • 渗透测试工程师面试题大全（二）

    渗透测试工程师面试题大全 二 from backlion大佬 整理 51 sql 注入写文件都有哪些函数 1 select 一句话 into outfile 路径 2 select 一句话 into dumpfile 路径 3 select

  • 如何安装 IntelliJ IDEA 最新版本——详细教程

    IntelliJ IDEA 简称 IDEA 被业界公认为最好的 Java 集成开发工具 尤其在智能代码助手 代码自动提示 代码重构 代码版本管理 Git SVN Maven 单元测试 代码分析等方面有着亮眼的发挥 IDEA 产于捷克 开发人

  • Allure在自动化测试中的应用！

    01 Allure的简介及使用 1 应用场景 自动化的结果一定是通过一个报告来进行体现 Allure 是一个独立的报告插件 生成美观易读的报告 目前支持Python Java PHP C 等语言 为dev QA 提供详尽的测试报告 测试步骤

  • 微信小程序实现视频号跳转

    三种类型 1 跳转到视频号主页 wx openChannelsUserProfile finderUserName 视频号id 2 跳转到视频号视频 wx openChannelsActivity feedId 视频id finderUse

  • 文件上传-图片webshell上传

    图片webshell制作 在服务器端的PHP代码中 对于用户上传的文件做文件类型检查 查看文件格式是否符合上传规范 可以检查文件二进制格式的前几个字节 从而判断文件类型是否正确 针对这种情况可以直接新建要给1 jpg 其中代码内容如下 GI

  • 【数据结构】 二叉树面试题讲解-＞壹

    文章目录 引言 相同的树 https leetcode cn problems same tree description 题目描述 示例 示例一 示例二 示例三 题目解析 代码实现 另一棵树的子树 https leetcode cn pr

  • 华为OD机试-找出重复代码-2022Q4 A卷-Py/Java/JS

    小明负责维护项目下的代码 需要查找出重复代码 用以支撑后续的代码优化 请你帮助小明找出重复的代码 重复代码查找方法 以字符串形式给出两行代码 字符审长度1 lt length lt 100 由英文字母 数字和空格组成 找出两行代码中的最长公

  • 深度学习之感知器的python实现，及用感知器实现鸢尾花的分类

    机器学习一般用来处理结构化的数据 深度学习一般用来处理非结构化的数据 例如图像 视频 文字等 权重更新过程 如果真实是1 预测是0 则权重会增加 相当于为了达到阈值增加权重 如果真实是0 预测是1 则权重会降低 相当于为了达到阈值减少权重

  • 玩客云通过openwrt作为旁路由

    前置条件 玩客云安装 docker 安装 OpenWrt 这边又两套方案可供选择 下面是具体教程的链接镜像一 https www right com cn forum thread 8024126 1 1 html镜像二 https hub

  • 在Idea中调试ant应用

    Ant调试 Ant调试 ant 是一种非常方便的打包 部署的工具 通过ant 可以一键构建整个项目 虽然MVN也支持这种功能 但是MVN混杂了package管理的功能 并且不是很自由 学习成本比较高 通常 我们调试ant构成的程序 是通过远

  • 零散算法

    1 字符串匹配 朴素的串匹配算法 KMP匹配算法 2 广度优先搜索BFS 3 深度优先搜索DFS 4 狄克斯特拉算法Dijkstra 5 贪婪算法 6 动态规划 7 安全散列算法SHA 用递归分析问题 基于循环写代码 10 关于查找算法 1

热门标签