分类 /

数据结构与算法19

雪花算法原理以及JS精度丢失问题

雪花算法原理以及JS精度丢失问题背景最近项目上遇到一个改造主键生成策略的问题:需要将原Redis自增id改造成雪花算法。一个好消息是项目用的ORM框架(Mybatis-Plus)自带雪花算法生成策略,只需在id字段上加上特定的注解。而问题在于该策略生...

Trie树

Trie树一切知识都从一个小问题开始:​给定一些命令,如set, setbit, setnx, strlen,get, getbit, exists 实现自动补全功能,例如输入se, 提示set, setbit, setnx...

布隆过滤器

布隆过滤器前置知识:位图算法在讲位图算法时我们说到位图算法的缺陷是不能处理数据重复问题,也就是数据hash值产生冲突时,只知道这里有值,但是不知道有几个,是谁的。最经典的问题就像这个:假设有一个10亿的email黑名单,怎么通过这个黑名单过滤邮件?当...

位图算法(BitMap)

位图算法(BitMap)问题假设有2亿个数,范围在0~3亿,给出一个数,判断这个数是否存在该2亿个数之内?使用内存不得超过500M解决方式定义一个3亿长度的整型数组int[],预先将所有数初始化,判断是否存在时只需int[number] != 0...

数据结构与算法(十五)堆树

定义是一颗完全二叉树每一个结点都大于等于它的子结点(大顶堆),或者小于等于它的子结点(小顶堆)图解堆的插入过程从下往上从上往下其插入的过程就叫做堆化堆的删除过程初始化堆的过程代码实现publicclassHeapTree{privateint[]ar...

数据结构与算法(十四)哈夫曼树

问题给定一串字符串:abcd,如何压缩?我们知道每个字节在计算机中占8bit,假使我们定义二进制00表示a,01表示b,10表示c,11表示d那么abcd转为二进制后就变成了00011011,看,原本占4*8=32bit的一串字符串,现在只占8bit...

数据结构与算法(十三)B+树

性质M阶的B+数据每个结点最多存储m-1个元素每个结点最多有m个子结点根结点要么为空,要么为独根,否则至少有2个子结点除根节点外,每个结点至少有m/2个子结点,除不尽则往上取整,7/2=3.5-->4叶子结点的高度一致只有叶子结点才存储数据叶子...

数据结构与算法(十二)红黑树

数据结构可视化学习网址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html性质1.每个结点不是红色就是黑色2.每个叶子节点都是黑色的空节点(NIL),根结点都是黑色3.不可能有...

数据结构与算法(十一)二叉搜索树

特点左子树的每个结点的值都比根节点小,右子树的每个结点的值都比根节点大中序遍历为一个有序序列图时间复杂度查找O(logn)插入O(1)删除O(logn)寻找前继结点或者后继结点替换删除的结点前继结点:第一个比根节点小的数后继结点:第一个比根节点大的数...

数据结构与算法(十)树

树形结构的相关术语结点:树里面的元素父子关系:结点之间相连的边子树:当结点大于1时,其余结点分为的互不相交的集合度:一个结点拥有的子树数量称为结点的度叶子:度为0的结点孩子:结点的子树的根节点双亲:兄弟:同一个双亲结点森林:由N个互不相交的树构成深林...

数据结构与算法(九)动态规划

特点局部最优解:也就是它会有一个最优子结构子问题可以重复状态转移方程:通过把问题分成很多小阶段一段段的转移。从而得出最优解.状态转移方程是解决动态规划的关键。如果我们能写出状态转移方程,那动态规划问题基本上就解决一大半了,翻译成代码非常简单。但是很多...

数据结构与算法(八)贪心算法

定义贪心算法又叫做贪婪算法,它在求解某个问题是,总是做出眼前最大利益。特点局部最优解通过局部最优推出全局最优习题某天早上公司领导找你解决一个问题,明天公司有N个同等级的会议需要使用同一个会议室,现在给你这个N个会议的开始和结束时间,你怎么样安排才能使...

数据结构与算法(二)数组

什么是数组数组是有序的元素序列,若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中,为了处理方便,把具有相同类...