数据结构和算法

新的硬币找零问题。假设我们有⼏种不同币值的硬币v1，v2，……，vn（单位是元）。如果我们要⽀付w元，求最少需要多少个硬币。⽐如，我们有3种不同的硬币，1元、3元、5元，我们要⽀付9元，最少需要3个硬币（3个3元的硬币）。

0/1 背包问题

如何量化两个字符串的相似度？

如何编程计算莱⽂斯坦距离？

如何编程计算最⻓公共⼦串⻓度？

0-1背包问题升级版

淘宝的“双⼗⼀”购物节有各种促销活动，⽐如“满200元减50元”。假设你⼥朋友的购物⻋中有n个（n>100）想买的商品，她希望从⾥⾯选⼏个，在凑够满减条件的前提下，让选出来的商品价格总和最⼤程度地接近满减条件（200元），这样就可以极⼤限度地“薅⽺⽑”。

实战

什么是“⼀个模型”？它指的是动态规划适合解决的问题的模型。我把这个模型定义为“多阶段决策最优解模型”。

1.最优⼦结构最优⼦结构指的是，问题的最优解包含⼦问题的最优解。反过来说就是，我们可以通过⼦问题的最优解，推导出问题的最优解。如果我们把最优⼦结构，对应到我们前⾯定义的动态规划问题模型上，那我们也可以理解为，后⾯阶段的状态可以通过前⾯阶段的状态推导出来。

2.⽆后效性⽆后效性有两层含义，第⼀层含义是，在推导后⾯阶段的状态的时候，我们只关⼼前⾯阶段的状态值，不关⼼这个状态是怎么⼀步⼀步推导出来的。第⼆层含义是，某阶段状态⼀旦确定，就不受之后阶段的决策影响。⽆后效性是⼀个⾮常“宽松”的要求。只要满⾜前⾯提到的动态规划问题模型，其实基本上都会满⾜⽆后效性。

3.重复⼦问题这个概念⽐较好理解。前⾯⼀节，我已经多次提过。如果⽤⼀句话概括⼀下，那就是，不同的决策序列，到达某个相同的阶段时，可能会产⽣重复的状态。

理论  ⼀个模型三个特征

1.状态转移表法

2.状态转移⽅程法

解题思路

动态规划

分治算法（divide and conquer）的核⼼思想其实就是四个字，分⽽治之 ，也就是将原问题划分成n个规模较⼩，并且结构与原问题相似的⼦问题，递归地解决这些⼦问题，然后再合并其结果，就得到原问题的解。

MapReduce框架只是⼀个任务调度器，底层依赖GFS来存储数据，依赖Borg管理机器。它从GFS中拿数据，交给Borg中的机器执⾏，并且时刻监控机器执⾏的进度，⼀旦出现机器宕机、进度卡壳等，就重新从Borg中调度⼀台机器执⾏。

⼀台机器过于低效，那我们就把任务拆分到多台机器上来处理。如果拆分之后的⼩任务之间互不⼲扰，独⽴计算，最后再将结果合并。这不就是分治思想吗？

MapRedue的本质就是分治算法

O(n)时间复杂度内求⽆序数组中的第K⼤元素。

如何编程求出⼀组数据的有序对个数或者逆序对个数呢？

⼆维平⾯上有n个点，如何快速计算出两个距离最近的点对？

有两个n*n的矩阵A，B，如何快速求解两个矩阵的乘积C=A*B？

分治思想在海量数据处理中的应⽤

分治思想

1.⼀个问题的解可以分解为⼏个⼦问题的解

2.这个问题与分解之后的⼦问题，除了数据规模不同，求解思路完全⼀样

3.存在递归终⽌条件

递归需要满⾜的三个条件

写递归代码最关键的是写出递推公式，找到终⽌条件

跳台阶问题

递归--数学归纳法

迭代---遍历

迭代和递归

稳定性。这个概念是说，如果待排序的序列中存在值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变。

原地排序（Sorted in place）。原地排序算法，就是特指空间复杂度是O(1)的排序算法。

概念

原地排序，稳定的

将数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有⼀个元素，就是数组的第⼀个元素。插⼊算法的核⼼思想是取未排序区间中的元素，在已排序区间中找到合适的插⼊位置将其插⼊，并保证已排序区间数据⼀直有序。重复这个过程，直到未排序区间中元素为空，算法结束。

插入

原地排序，不稳定的

选择排序算法的实现思路有点类似插⼊排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最⼩的元素，将其放到已排序区间的末尾。

选择

冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进⾏⽐较，看是否满⾜⼤⼩关系要求。如果不满⾜就让它俩互换。⼀次冒泡会让⾄少⼀个元素移动到它应该在的位置，重复n次，就完成了n个数据的排序⼯作。

冒泡

非原地排序，稳定的

如果要排序⼀个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在⼀起，这样整个数组就都有序了。

归并

如果要排序数组中下标从p到r之间的⼀组数据，我们选择p到r之间的任意⼀个数据作为pivot（分区点）。我们遍历p到r之间的数据，将⼩于pivot的放到左边，将⼤于     pivot的放到右边，将pivot放到中间。根据分治、递归的处理思想，我们可以⽤递归排序下标从p到q-1之间的数据和下标从q+1到r之间的数据，直到区间缩⼩为1，就说明所有的数据都有序了。

1.三数取中法，2.随机法

优化快排

快排

⼼思想是将要排序的数据分到⼏个有序的桶⾥，每个桶⾥的数据再单独进⾏排序。桶内排完序之后，再把每个桶⾥的数据按照顺序依次取出，组成的序列就是有序的了。

如何根据年龄给100万⽤户数据排序

桶排序

基本排序算法

霍夫曼编码不仅会考察⽂本中有多少个不同字符，还会考察每个字符出现的频率，根据频率的不同，选择不同⻓度的编码。霍夫曼编码试图⽤这种不等⻓的编码⽅法，来进⼀步增加压缩的效率。如何给不同频率的字符选择不同⻓度的编码呢？根据贪⼼的思想，我们可以把出现频率⽐较多的字符，⽤稍微短⼀些的编码；出现频率⽐较少的字符，⽤稍微⻓⼀些的编码。

霍夫曼编码是不等⻓的，每次应该读取1位还是2位、3位等等来解压缩呢？这个问题就导致霍夫曼编码解压缩起来⽐较复杂。为了避免解压缩过程中的歧义，霍夫曼编码要求各个字符的编码之间，不会出现某个编码是另⼀个编码前缀的情况。

假设我有⼀个包含1000个字符的⽂件，每个字符占1个byte（1byte=8bits），存储这1000个字符就⼀共需要8000bits，那有没有更加节省空间的存储⽅式呢？

哈夫曼编码利⽤贪⼼算法来实现对数据压缩编码，有效节省数据存储空间的。

1.分糖果我们有m个糖果和n个孩⼦。我们现在要把糖果分给这些孩⼦吃，但是糖果少，孩⼦多（m

2.钱币找零这个问题在我们的⽇常⽣活中更加普遍。假设我们有1元、2元、5元、10元、20元、50元、100元这些⾯额的纸币，它们的张数分别是c1、c2、c5、c10、c20、c50、c100。我们现在要⽤这些钱来⽀付K元，最少要⽤多少张纸币呢？

4. 在⼀个⾮负整数a中，我们希望从中移除k个数字，让剩下的数字值最⼩，如何选择移除哪k个数字呢？

2. 假设有n个⼈等待被服务，但是服务窗⼝只有⼀个，每个⼈需要被服务的时间⻓度是不同的，如何安排被服务的先后顺序，才能让这n个⼈总的等待时间最短？

贪心算法

暴力破解

KMP算法等难理解

字符串匹配

回溯的处理思想，有点类似枚举搜索。我们枚举所有的解，找到满⾜期望的解。为了有规律地枚举所有可能的解，避免遗漏和重复，我们把问题求解的过程分为多个阶段。每个阶段，我们都会⾯对⼀个岔路⼝，我们先随意选⼀条路⾛，当发现这条路⾛不通的时候（不符合期望的解），就回退到上⼀个岔路⼝，另选⼀种⾛法继续⾛。

8皇后问题

0-1背包

正则表达式

回溯思想

⼆分查找针对的是⼀个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对⽐，将待查找的区间缩⼩为之前的⼀半，直到找到要查找的元素，或者区间被缩⼩为0。O(logn)惊⼈的查找速度

如何在1000万个整数中快速查找某个整数？

⼆分查找依赖的是顺序表结构，简单点说就是数组。针对的是有序数据。数据量太⼩不适合⼆分查找，，数据量太⼤也不适合⼆分查找。

注意

基本形式

变体⼀：查找第⼀个值等于给定值的元素

变体⼆：查找最后⼀个值等于给定值的元素

变体三：查找第⼀个⼤于等于给定值的元素

变体四：查找最后⼀个⼩于等于给定值的元素

如何快速定位出⼀个IP地址的归属地？

变体

二分查找算法

将任意⻓度的⼆进制值串映射为固定⻓度的⼆进制值串，这个映射的规则就是哈希算法，⽽通过原始数据映射之后得到的⼆进制值串就是哈希值。

最常⽤于加密的哈希算法是MD5（MD5 Message-DigestAlgorithm，MD5消息摘要算法）和SHA（Secure Hash Algorithm，安全散列算法）。

应⽤⼀：安全加密

如果要在海量的图库中，搜索⼀张图是否存在，我们不能单纯地⽤图⽚的元信息（⽐如图⽚名称）来⽐对，因为有可能存在名称相同但图⽚内容不同，或者名称不同图⽚内容相同的情况。那我们该如何搜索呢？

应⽤⼆：唯⼀标识

BT下载

应⽤三：数据校验

应⽤四：散列函数

区块链是⼀块块区块组成的，每个区块分为两部分：区块头和区块体。区块头保存着 ⾃⼰区块体 和 上⼀个区块头 的哈希值。因为这种链式关系和哈希值的唯⼀性，只要区块链上任意⼀个区块被修改过，后⾯所有区块保存的哈希值就不对了。区块链使⽤的是 SHA256 哈希算法，计算哈希值⾮常耗时，如果要篡改⼀个区块，就必须重新计算该区块后⾯所有的区块的哈希值，短时间内⼏乎不可能做到

区块链

应用

如何才能实现⼀个会话粘滞（session sticky）的负载均衡算法呢？也就是说，我们需要在同⼀个客户端上，在⼀次会话中的所有请求都路由到同⼀个服务器上。

应⽤五：负载均衡

1.如何统计“搜索关键词”出现的次数？

2.如何快速判断图⽚是否在图库中？

应⽤六：数据分⽚

子主题

一致性哈希存在数据分布不均匀的问题，节点存储的数据量有可能会存在很大的不同。数据不均匀主要是因为节点在哈希环上分布的不均匀，这种情况在节点数量很少的情况下尤其明显。解决方式是通过增加虚拟节点，然后将虚拟节点映射到真实节点上。虚拟节点的数量比真实节点来得多，那么虚拟节点在哈希环上分布的均匀性就会比原来的真实节点好，从而使得数据分布也更加均匀。

虚拟节点

⼀致性哈希算法

应⽤七：分布式存储

在分布式中应用

在负载均衡应⽤中，利⽤哈希算法替代映射表，可以实现⼀个会话粘滞的负载均衡策略。在数据分⽚应⽤中，通过哈希算法对处理的海量数据进⾏分⽚，多机分布式处理，可以突破单机资源的限制。在分布式存储应⽤中，利⽤⼀致性哈希算法，可以解决缓存等分布式系统的扩容、缩容导致数据⼤量搬移的难题。

哈希算法

数组（Array）是⼀种线性表数据结构。它⽤⼀组连续的内存空间，来存储⼀组具有相同类型的数据。

ArrayList最⼤的优势就是可以将很多数组操作的细节封装起来。⽐如前⾯提到的数组插⼊、删除数据时需要搬移其他数据等。另外，它还有⼀个优势，就是⽀持动态扩容。

容器和数组的比较

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前⾯也讲到，如果⽤a来表示数组的⾸地址，a[0]就是偏移为0的位置，也就是⾸地址，a[k]就表示偏移k个type_size的位置，所以计算a[k]的内存地址只需要⽤这个公式：但是，如果数组从1开始计数，那我们计算数组元素a[k]的内存地址就会变为：ArrayList users = new ArrayList(10000);for (int i = 0; i < 10000; ++i) {users.add(xxx);}a[k]_address = base_address + k * type_size对⽐两个公式，我们不难发现，从1开始编号，每次随机访问数组元素都多了⼀次减法运算，对于CPU来说，就是多了⼀次减法指令。

为什么⼤多数编程语⾔中，数组要从0开始编号，⽽不是从1开始呢？

数组

链表通过“指针”将⼀组零散的内存块串联起来使⽤，常用链表结构 单链表、双向链表和循环链表

快慢指针，哨兵机制（头），指针（引用），警惕指针丢失，边界处理，举例画图辅助思考等编码技巧

循环链表的约瑟夫问题

https://crossoverjie.top/JCSprout/#/algorithm/LRU-cache

基于链表实现LRU缓存淘汰算法

解决问题

单链表反转链表中环的检测两个有序的链表合并删除链表倒数第n个结点求链表的中间结点

练习

链表

图示结构

散列表⽤的是数组⽀持按照下标随机访问数据的特性，所以散列表其实就是数组的⼀种扩展，由数组演化⽽来。可以说，如果没有数组，就没有散列表。

散列函数，顾名思义，它是⼀个函数。我们可以把它定义成hash(key)，其中key表示元素的键值，hash(key)的值表示经过散列函数计算得到的散列值。

即便像业界著名的MD5、SHA、CRC等哈希算法，也⽆法完全避免这种散列冲突。

1.开放寻址法，2.链表法

散列冲突

散列函数的设计不能太复杂

散列函数⽣成的值要尽可能随机并且均匀分布

定义装载因⼦阈值，并且设计动态扩容策略；

选择合适的散列冲突解决⽅法。

如何设计散列函数

散列函数

Word⽂档中单词拼写检查功能是如何实现的？

LinkedHashMap是通过双向链表和散列表这两种数据结构组合实现的。LinkedHashMap中的“Linked”实际上是指的是双向链表，并⾮指⽤链表法解决散列冲突。

实现

散列表

叶⼦节点全都在最底层，除了叶⼦节点之外，每个节点都有左右两个⼦节点，这种⼆叉树就叫作满⼆叉树。

满二叉树

叶⼦节点都在最底下两层，最后⼀层的叶⼦节点都靠左排列，并且除了最后⼀层，其他层的节点个数都要达到最⼤，这种⼆叉树叫作完全⼆叉树。

堆是⼀个完全⼆叉树；堆中每⼀个节点的值都必须⼤于等于（或⼩于等于）其⼦树中每个节点的值。

1.合并有序⼩⽂件

2.⾼性能定时器

堆的应⽤⼀：优先级队列

堆的应⽤⼆：利⽤堆求Top K

堆的应⽤三：利⽤堆求中位数

堆

完全⼆叉树

⼆叉查找树要求，在树中的任意⼀个节点，其左⼦树中的每个节点的值，都要⼩于这个节点的值，⽽右⼦树节点的值都⼤于这个节点的值。

⼆叉查找树

AVL树

平衡二叉树

红黑树

分类

前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左⼦树，最后打印它的右⼦树。

中序遍历是指，对于树中的任意节点来说，先打印它的左⼦树，然后再打印它本身，最后打印它的右⼦树。

后序遍历是指，对于树中的任意节点来说，先打印它的左⼦树，然后再打印它的右⼦树，最后打印这个节点本身。

层遍历

遍历

二叉树

B树

B+树

多叉树

图示

leetcode 208. 实现 Trie (前缀树)

leetcode 820. 单词的压缩编码

代码

字典树/Trie/前缀树

树

图中的元素我们就叫作顶点（vertex）。图中的⼀个顶点可以与任意其他顶点建⽴连接关系。我们把这种建⽴的关系叫作边（edge）。

度（degree），就是跟顶点相连接的边的条数。

在有向图中，我们把度分为⼊度（In-degree）和出度（Out-degree）。顶点的⼊度，表示有多少条边指向这个顶点；顶点的出度，表示有多少条边是以这个顶点为起点指向其他顶点。

带权图（weighted graph）。在带权图中，每条边都有⼀个权重（weight）

相关概念

如果我们存储的是稀疏图（Sparse Matrix），也就是说，顶点很多，但每个顶点的边并不多，那邻接矩阵的存储⽅法就更加浪费空间了。⽐如微信有好⼏亿的⽤户，对应到图上就是好⼏亿的顶点。但是每个⽤户的好友并不会很多，⼀般也就三五百个⽽已。如果我们⽤邻接矩阵来存储，那绝⼤部分的存储空间都被浪费了。

邻接矩阵

每个顶点对应⼀条链表，链表中存储的是与这个顶点相连接的其他顶点。（有点像散列表）

邻接表

存储⽅法

从图中的某一个顶点Vi触发，访问此顶点后，依次访问Vi的各个为层访问过的邻接点，然后分别从这些邻接点出发，直至图中所有顶点都被访问到。广度优先遍历类似树的层序遍历。

它其实就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

广度优先遍历BFS

走迷宫：假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到

深度优先遍历DFS

如何存储微博、微信等社交⽹络中的好友关系？

问题

https://www.cnblogs.com/polly333/p/4760275.html

图

理解为索引

这种链表加多级索引的结构，就是跳表。

Redis中的有序集合是通过跳表来实现的

跳表

先进者先出，这就是典型的“队列”。

有效的处理一般队列的数据搬移问题

最关键的是，确定好队空和队满的判定条件。

循环队列

阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插⼊数据的操作就会被阻塞，直到队列中有空闲位置后再插⼊数据，然后再返回。

线程安全的队列我们叫作并发队列

阻塞队列和并发队列

先进后出队列

大根堆

小根堆

优先级队列

队列

后进者先出，先进者后出，这就是典型的“栈”结构。

⽐较经典的⼀个应⽤场景就是函数调⽤栈。

如何实现浏览器的前进、后退功能？其实，⽤两个栈就可以⾮常完美地解决这个问题。

栈

所谓bitmap，是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

算法思想： 将大数据量经过hash映射保存到一个bit数组 中，大大减小了存储空间

bigMap位图算法

布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。

用于高效检测数据元素是否在给的集合中，是BigMap的扩展

鉴别垃圾邮件，URL白名单和黑名单过滤

Bloom Filter 布隆过滤器

https://snailclimb.gitee.io/javaguide/#/docs/dataStructures-algorithms/data-structure/bloom-filter

布隆过滤器

位图 

https://zhuanlan.zhihu.com/p/93647900

合并（Union）：把两个不相交的集合合并为一个集合。

查询（Find）：查询两个元素是否在同一个集合中。

并查集被很多OIer认为是最简洁而优雅的数据结构之一，主要用于解决一些元素分组的问题。它管理一系列不相交的集合，并支持两种操作。

并查集

数据结构和算法