哈希算法实例详解 1.什么是哈希Hash,一般翻译做散列、杂凑,或音译为哈希,是一个典型的利用空间换取时间的算法,把任意长度的输入(又叫做预映射pre-image)通过散列算法变换成固定长度的输出,该输出就是散列值。如有一个学生信息表:学生的学号为:年纪+学院号+班级号+顺序排序号【如:19(年纪)+002(2号学院) 算法和竞赛 2022年05月18日 182 点赞 0 评论 114301 浏览
简述随机化算法 本篇将主要讲解随机化算法,在正式进入主题之前,我们先谈谈什么是随机化?随机化是一种可能影响试验结果的无关或可能在试验过程中变化,从而影响到最终结果。随机化算法,是在算法中使用了随机函数,且随机函数的返回值直接或间接的影响了算法的执行流程或结果。 其他算法 2022年05月14日 113 点赞 0 评论 77022 浏览
简述最小树形图 一、什么是最小树形图?就是指有向图上的最小生成树,英文是DirectedMinimumSpanningTree。常用的算法是朱刘算法(也称Edmonds算法),可以在O(nm)时间内解决最小树形图问题。(1)过程对于每个点,选择它入度最小的那条边如果没有环, 图论 2022年03月27日 222 点赞 0 评论 96712 浏览
DFS求有向图(无向图)两点间路径 本文会围绕算法中DFS求有向图或无向图两点间所有路径,先讲解DFS以及有向图或无向图的意思。有向图在图中的边是有方向的,表现出来就是有个箭头指示方向,节点只能单向通信或传递消息,相当于单行道,无向图边没方向是双向的,边连接的两个节点有通路可以双向通信,类似于双行道。 图论 2022年03月08日 227 点赞 0 评论 100964 浏览
什么是状态压缩DP? 状态压缩DP一般是基于二进制进行的。状态压缩DP一般分为两类:①基于连通性DP(棋盘式)②集合式(表示每一个元素是否在集合中)一、概述1.状态压缩状态压缩就是使用某种方法,简明扼要地以最小代价来表示某种状态,通常是用一串01数字(二进制数)来表示各个点的状态。 动态规划 2022年05月27日 148 点赞 0 评论 77878 浏览
什么是Lyndon分解? 我们定义一个串是Lyndon串,当且仅当这个串的最小后缀就是这个串本身。该命题等价于这个串是它的所有循环表示中字典序最小的。引理1:如果u和v都是Lyndon串并且u<v,则uv也是Lyndon串。证明:1、若len(u)≥len(v)这时, 字符串相关 2022年02月28日 69 点赞 0 评论 85293 浏览
二叉树(树)与森林的相互转换 1.什么是森林森林,顾名思义,就是由众多的树构成的一组数据结构,这些树本身没有什么联系,用系统的语言描述就是:森林:m(>=0)棵互不相交的树的集合【注意这里森林是可以有0颗树的,同数学上的空集】如果把一棵树当作一个独立的点,那么森林就是一个点的集合。 树 2022年05月23日 141 点赞 0 评论 165544 浏览
结合实例解析深度优先搜索(DFS)搜索 当你从一个顶点开始,沿着某条路往下走,一直走到底,如果走完后发现不能达到目标解,就回溯,返回到上一个节点,换条路,然后继续走到底,如此往复,直至所有可能的结果都被搜索完。通俗理解就是不撞南墙不回头这种感觉,这个就是我们这篇要讲解的内容,下面带领大家结合实例系统的学习一下。 搜索算法 2022年02月01日 213 点赞 0 评论 115138 浏览
二叉树的存储(C语言实现) 二叉树存储1.简介根据前文的介绍,我们知道了二叉树的性值,其就是一种每一个结点中只允许拥有左右孩子(或为空)的树,这种数据结构在我们的实际设计中非常常用,如前文提到的STL中的set集合,其底层就是一颗标准的红黑树(二叉树的一种),我们这里以创建一颗二叉树并实现通过特定的插入顺序和读取顺序达成读取为顺 树 2022年02月17日 241 点赞 0 评论 100538 浏览
简述LGV引理 LGV引理可以用于在DAG上求解不相交路径方案数问题,下面我们简单介绍一下。一、简介LGV引理英文全称是Lindström–Gessel–Viennotlemma,可以用来处理有向无环图上不相交路径计数等问题。在此之前,大家要先了解图论相关概念、矩阵、高斯消元求行列式等知识, 图论 2022年04月20日 249 点赞 0 评论 65870 浏览