首页  思维导图  详情

数据结构和算法

2022-07-30 21:06:13   1  举报





AI智能生成

数据结构总结

数据结构与算法

作者其他创作

大纲/内容

动态规划

实战

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

0/1 背包问题

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

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

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

我们有⼀个数字序列包含n个不同的数字，如何求出这个序列中的最⻓递增⼦序列⻓度？⽐如2, 9, 3, 6, 5, 1, 7这样⼀组数字序
列，它的最⻓递增⼦序列就是2, 3, 5, 7，所以最⻓递增⼦序列的⻓度是4。

0-1背包问题升级版

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

理论⼀个模型三个特征

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

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

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

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

解题思路

1.状态转移表法

2.状态转移⽅程法

分治思想

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

MapRedue的本质就是分治算法

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

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

实战

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元，最少要⽤多少张纸币呢？

3.区间覆盖
假设我们有n个区间，区间的起始端点和结束端点分别是[l1, r1]，[l2, r2]，[l3, r3]，……，[ln, rn]。我们从这n个区间中选出⼀
部分区间，这部分区间满⾜两两不相交（端点相交的情况不算相交），最多能选出多少个区间呢？

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.如何快速判断图⽚是否在图库中？

应⽤七：分布式存储

⼀致性哈希算法

子主题

将哈希空间 [0, 2n-1] 看成一个哈希环，每个服务器节点都配置到哈希环上。每个数据对象通过哈希取模得到哈希值之后，存放到哈希环中顺时针方向第一个大于等于该哈希值的节点上。

虚拟节点

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

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

数组

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

容器和数组的比较

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

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

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（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来说，就是多了⼀次减
法指令。

链表

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

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

解决问题

循环链表的约瑟夫问题

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

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

练习

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

散列表

图示结构

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

散列函数

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

散列冲突

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

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

如何设计散列函数

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

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

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

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

实现

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

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

树

二叉树

分类

满二叉树

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

完全⼆叉树

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

堆

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

应用

堆的应⽤⼀：优先级队列

1.合并有序⼩⽂件

2.⾼性能定时器

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

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

⼆叉查找树

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

平衡二叉树

AVL树

红黑树

遍历

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

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

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

层遍历

多叉树

B树

B+树

字典树/Trie/前缀树

图示

子主题

代码

leetcode 208. 实现 Trie (前缀树)

leetcode 820. 单词的压缩编码

图

相关概念

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

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

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

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

存储⽅法

邻接矩阵

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

邻接表

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

遍历

广度优先遍历BFS

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

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

子主题

深度优先遍历DFS

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

子主题

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

问题