「 数据结构 」 和 「 算法 」 是密不可分的,两者往往是 「 相辅相成 」 的存在,所以,在学习 「 数据结构 」 的过程中,不免会遇到各种 「 算法 」 。 到底是先学 数据结构 ,还是先学 算法,我认为不必纠结这个问题,一定是一起学的。 数据结构 常用的操作一般为: 「 增 」 「 删 」 「 改 」 「 查 」 。基本上所有的数据结构都是围绕这几个操作进行展开的。 那么这篇文章,作者将主要来聊聊: 「 算法和数据结构 」 在学习数据结构的过程中,如果你能够自己把图画出来,并且能够描述整个 「 增 」 「 删 」 「 改 」 「 查 」 的过程,那么说明你已经真正理解了数据结构的真谛,来看下下面几张图:
「 数据结构 」 和 「 算法 」 是密不可分的,两者往往是 「 相辅相成 」 的存在,所以,在学习 「 数据结构 」 的过程中,不免会遇到各种 「 算法 」 。 到底是先学 数据结构 ,还是先学 算法,我认为不必纠结这个问题,一定是一起学的。 数据结构 常用的操作一般为: 「 增 」 「 删 」 「 改 」 「 查 」 。基本上所有的数据结构都是围绕这几个操作进行展开的。 那么这篇文章,作者将主要来聊聊:
「 算法和数据结构 」 在学习数据结构的过程中,如果你能够自己把图画出来,并且能够描述整个 「 增 」 「 删 」 「 改 」 「 查 」 的过程,那么说明你已经真正理解了数据结构的真谛,来看下下面几张图:
如果你只是想学会写代码,或许 「 算法与数据结构 」 并不是那么重要,但是,想要进一步发展自己的事业, 「 算法与数据结构 」 是必不可少的。 现在一些主流的大厂,诸如:字节、网易、腾讯、阿里、美团、京东、滴滴 等等,在面时都会让候选人写一道 「 算法题 」 ,如果你敲不出来,可能你的 offer 年包就打了骨折,或者直接与 offer 失之交臂,都是有可能的。 当然,它不能完全代表你的编码能力(因为有些算法确实是很巧妙,加上紧张的面试氛围,想不出来其实也是正常的),但是你能确保面试官是这么想的吗?我们要做的是十足的准备,既然决定出来, offer 当然是越高越好,毕竟大家都要养家糊口,房价又这么贵,如果能够在算法这一块取得先机,也不失为一个捷径。 所以,你问我算法和数据结构有什么用?我可以很明确的说,和你的年薪息息相关。当然,面试中 「算法与数据结构」 知识的考察只是面试内容的一部分。其它还有很多面试要考察的内容,当然不是本文主要核心内容,这里就不做展开了。
这篇文章中,我会着重讲解一些常见的 「 算法和数据结构 」 的设计思想,并且配上动图。主要针对面试中常见的问题和新手朋友们比较难理解的点进行解析。当然,后面也会给出面向算法竞赛的提纲,如果有兴趣深入学习的欢迎在评论区留言,一起成长交流。 零基础学算法的最好方法,莫过于 「 刷题 」 了。任何事情都是需要 「 坚持 」 的,刷题也一样,没有刷够足够的题,就很难做出系统性的总结。所以上大学的时候,我花了三年的时间来刷题, 工作以后还是会抽点时间出来刷题。 当然,每天不需要花太多时间在这个上面,把这个事情做成一个 「 规划 」 ,按照长期去推进。反正也没有 KPI 压力,就当成是工作之余的一种消遣,还能够提升思维能力。所谓: 「 十年磨一剑,今朝把示君 」 。
相信看我文章的大多数都是 「 大学生 」 ,能上大学的都是 「 精英 」 ,那么我们自然要 「 精益求精 」 ,如果你还是 「 大一 」 ,那么太好了,你拥有大把时间,当然你可以选择 「 刷剧 」 ,然而, 「 学好算法 」 ,三年后的你自然 「 不能同日而语 」 。 如果你满足如下: ( 1 ) (1) (1) 有强烈欲望「 想要学好C语言 」的人 ( 2 ) (2) (2) 有强烈欲望「 想要学好C++ 」的人 ( 3 ) (3) (3) 有强烈欲望「 想要学好数据结构 」的人 ( 4 ) (4) (4) 有强烈欲望「 想学好算法 」的人 ( 5 ) (5) (5) 有强烈欲望「 想进大厂 」的人 如果你满足以上任意一点,那么,我们就是志同道合的人啦! 🔥联系作者,或者扫作者主页二维码加群,加入我们吧🔥 那么这里,我整理了 「 几十个基础算法 」 的分类,点击开启:
🌌《 算法入门指引 》🌌 如果链接被屏蔽,或者有权限问题,可以私聊作者解决。 大致题集一览: 为了让这件事情变得有趣,以及 「 照顾初学者 」 ,目前题目只开放最简单的算法 「 枚举系列 」 (包括: 线性枚举、双指针、前缀和、二分枚举、三分枚举 ),当有 一半成员刷完 「 枚举系列 」 的所有题以后,会开放下个章节,等这套题全部刷完,你还在群里,那么你就会成为 「 夜深人静写算法 」专家团 的一员。 不要小看这个专家团,三年之后,你将会是别人 望尘莫及 的存在。如果要加入,可以联系我,考虑到大家都是学生, 没有「 主要经济来源 」 ,在你成为神的路上, 「 不会索取任何东西 」 ,也不会产生任何利益输送。
那么在进行算法学习之前,我们需要实际落地,就需要有一门语言基础,可以是 C语言、Java、Python 中的任意一种。当然,作者推荐的是 C语言。可以在作者的专栏中找到学习方法。
学习数据结构之前,选择一款相对来说心仪的教程是必不可少的,我这里准备了一个用动画来解释数据结构的教程,在我这也有,就是:
这是我目前来说,写的最用心的一个教程,里面汇集了大量的动图,目前更新已经过半,好评如潮。 当然,一边学习,一边做一些练习题是必不可少的,接下来就是推荐一个我自己整理的题集了,这个题集汇集了大量的算法。可以帮你在前行的路上扫平不少障碍。
如果你在刷题的过程中,已经爱上了算法,那么恭喜你,你将会无法自拔,一直刷题一直爽,在遇到一些高端的算法时,也不要惊慌,这里推荐一个竞赛选手金典图文教程,如下:
学习算法,数据结构是根基,没有一些数据结构做支撑,这个算法都没有落脚点,任何一个简单的算法都是需要数据结构来支撑的,比如最简单的算法,
内存结构 :内存空间连续 实现难度 :简单 下标访问 :支持 分类 :静态数组、动态数组 插入时间复杂度 : O ( n ) O(n) O(n) 查找时间复杂度 : O ( n ) O(n) O(n) 删除时间复杂度 : O ( n ) O(n) O(n)
顺序存储结构,是指用一段地址连续的存储单元依次存储线性表的数据元素。
在编程语言中,用一维数组来实现顺序存储结构,在C语言中,把第一个数据元素存储到下标为 0 的位置中,把第 2 个数据元素存储到下标为 1 的位置中,以此类推。
数组的长度指的是数组当前有多少个元素,数组的容量指的是数组最大能够存放多少个元素。如果数组元素大于最大能存储的范围,在程序上是不允许的,可能会产生意想不到的问题,实现上是需要规避的。 如上图所示,数组的长度为 5,即红色部分;容量为 8,即红色 加 蓝色部分。
#define MAXN 1024 #define DataType int // (1) struct SeqList { DataType data[MAXN]; // (2) int length; // (3) };
DataType
int
SeqList
MAXN
length
索引 就是通过 数组下标 寻找 数组元素 的过程。C语言实现如下:
DataType SeqListIndex(struct SeqList *sq, int i) { return sq->data[i]; // (1) }
查找 就是通过 数组元素 寻找 数组下标 的过程,是索引的逆过程。 对于有序数组,可以采用 二分 进行查找,时间复杂度为 O ( l o g 2 n ) O(log_2n)O(log2n);对于无序数组,只能通过遍历比较,由于元素可能不在数组中,可能遍历全表,所以查找的最坏时间复杂度为 O ( n ) O(n) O(n)。 简单介绍一个线性查找的例子,实现如下:
DataType SeqListFind(struct SeqList *sq, DataType dt) { int i; for(i = 0; i < sq->length; ++i) { // (1) if(sq->data[i] == dt) { return i; // (2) } } return -1; // (3) }
获取 数组的长度 指的是查询当前有多少元素。可以直接用结构体的内部变量。C语言代码实现如下:
DataType SeqListGetLength(struct SeqList *sq) { return sq->length; }
插入接口定义为:在数组的第 k k k 个元素前插入一个数 v v v。由于数组是连续存储的,那么从 k k k 个元素往后的元素都必须往后移动一位,当 k = 0 k=0 k=0 时,所有元素都必须移动,所以最坏时间复杂度为 O ( n ) O(n) O(n)。C语言代码实现如下:
int SeqListInsert(struct SeqList *sq, int k, DataType v) { int i; if(sq->length == MAXN) { return 0; // (1) } for(i = sq->length; i > k; --i) { sq->data[i] = sq->data[i-1]; // (2) } sq->data[k] = v; // (3) sq->length ++; // (4) return 1; // (5) }
插入接口定义为:将数组的第 k k k 个元素删除。由于数组是连续存储的,那么第 k k k 个元素删除,往后的元素势必要往前移动一位,当 k = 0 k=0 k=0 时,所有元素都必须移动,所以最坏时间复杂度为 O ( n ) O(n) O(n)。C语言代码实现如下:
int SeqListDelete(struct SeqList *sq, int k) { int i; if(sq->length == 0) { return 0; // (1) } for(i = k; i < sq->length - 1; ++i) { sq->data[i] = sq->data[i+1]; // (2) } sq->length --; // (3) return 1; // (4) }
内存结构 :内存空间连续不连续,看具体实现 实现难度 :一般 下标访问 :不支持 分类 :单向链表、双向链表、循环链表、DancingLinks 插入时间复杂度 : O ( 1 ) O(1) O(1) 查找时间复杂度 : O ( n ) O(n) O(n) 删除时间复杂度 : O ( 1 ) O(1) O(1)
链表 是由一个个 结点 组成,每个 结点 之间通过 链接关系 串联起来,每个 结点 都有一个 后继节点 ,最后一个 结点 的 后继结点 为 空结点 。如下图所示:
A -> B
B
A
typedef int DataType; struct ListNode { DataType data; // (1) ListNode *next; // (2) };
typedef
malloc
ListNode *ListCreateNode(DataType data) { ListNode *node = (ListNode *) malloc ( sizeof(ListNode) ); // (1) node->data = data; // (2) node->next = NULL; // (3) return node; // (4) }
ListNode
data
首先介绍 尾插法 ,顾名思义,即 从链表尾部插入 的意思,就是记录一个 链表尾结点 ,然后遍历给定数组,将数组元素一个一个插到链表的尾部,每插入一个结点,则将它更新为新的 链表尾结点 。注意初始情况下, 链表尾结点 为空。
上图演示的是 尾插法 的整个过程,其中: head 代表链表头结点,创建完一个结点以后,它就保持不变了; tail 代表链表尾结点,即动图中的 绿色结点 ; vtx 代表正在插入链表尾部的结点,即动图中的 橙色结点 ,插入完毕以后, vtx 变成 tail ;
ListNode *ListCreateListByTail(int n, int a[]) { ListNode *head, *tail, *vtx; // (1) int idx; if(n <= 0) return NULL; // (2) idx = 0; vtx = ListCreateNode(a[0]); // (3) head = tail = vtx; // (4) while(++idx < n) { // (5) vtx = ListCreateNode(a[idx]); // (6) tail->next = vtx; // (7) tail = vtx; // (8) } return head; // (9) }
对应的注释如下: ( 1 ) (1) (1) head存储头结点的地址,tail存储尾结点的地址,vtx存储当前正在插入结点的地址; ( 2 ) (2) (2) 当需要创建的元素个数为 0 时,直接返回空链表; ( 3 ) (3) (3) 创建一个 数据域 为a[0]的链表结点; ( 4 ) (4) (4) 由于初始情况下只有一个结点,所以将链表头结点head和链表尾结点tail都置为vtx; ( 5 ) (5) (5) 从数组第 1 个元素 (0 - based) 开始,循环遍历数组; ( 6 ) (6) (6) 由于数组中第 0 个元素已经创建过了,所以这里只需要对除了第 0 个元素以外的数据创建链表结点; ( 7 ) (7) (7) 结点创建出来后,将当前链表尾结点tail的 后继结点 置为vtx; ( 8 ) (8) (8) 将最近创建的结点vtx作为新的 链表尾结点 ; ( 9 ) (9) (9) 返回链表头结点;
head
tail
vtx
a[0]
头插法 ,顾名思义,就是每次从头结点前面进行插入,但是这样一来,就会导致插入的数据元素是 逆序 的,所以我们需要 逆序访问数组 执行插入,此所谓 负负得正 的思想。
上图所示的是 头插法 的整个插入过程,其中: head 代表链表头结点,即动图中的 绿色结点 ,每新加一个结点,头结点就变成了新加入的结点; tail 代表链表尾结点,创建完一个结点以后,它就保持不变了; vtx 代表正在插入链表头部的结点,即动图中的 橙色结点 ,插入完毕以后, vtx 变成 head ;
ListNode *ListCreateListByHead(int n, int *a) { ListNode *head = NULL, *vtx; // (1) while(n--) { // (2) vtx = ListCreateNode(a[n]); // (3) vtx->next = head; // (4) head = vtx; // (5) } return head; // (6) }
对应的注释如下: ( 1 ) (1) (1) head存储头结点的地址,初始为空链表, vtx存储当前正在插入结点的地址; ( 2 ) (2) (2) 总共需要插入 n n n 个结点,所以采用逆序的 n n n 次循环; ( 3 ) (3) (3) 创建一个元素值为a[i]的链表结点,注意,由于逆序,所以这里 i i i 的取值为 n − 1 → 0 n-1 \to 0 n−1→0; ( 4 ) (4) (4) 将当前创建的结点的 后继结点 置为 链表的头结点head; ( 5 ) (5) (5) 将链表头结点head置为vtx; ( 6 ) (6) (6) 返回链表头结点;
a[i]
头插法 的代码量比 尾插法 少了三分之一,而且将 创建结点的逻辑 统一起来了。这句话什么意思呢?仔细观察可以发现, 尾插法 在实现过程中,ListCreateNode在代码里出现了两次,而 头插法 只出现了一次,将流程简化了,所以还是推荐使用 头插法 。
ListCreateNode
想要了解更多链表相关内容,可以参考: 《画解数据结构》(1 - 3)- 链表 。
内存结构 :哈希表本身连续,但是衍生出来的结点逻辑上不连续 实现难度 :一般 下标访问 :不支持 分类 :正数哈希、字符串哈希、滚动哈希 插入时间复杂度 : O ( 1 ) O(1) O(1) 查找时间复杂度 : O ( 1 ) O(1) O(1) 删除时间复杂度 : O ( 1 ) O(1) O(1)
当我们在一个 链表 或者 顺序表 中 查找 一个数据元素 是否存在 的时候,唯一的方法就是遍历整个表,这种方法称为 线性枚举 。 如果这时候,顺序表是有序的情况下,我们可以采用折半的方式去查找,这种方法称为 二分枚举 。 线性枚举 的时间复杂度为 O ( n ) O(n) O(n)。 二分枚举 的时间复杂度为 O ( l o g 2 n ) O(log_2n) O(log2n)。是否存在更快速的查找方式呢?这就是本要介绍的一种新的数据结构 —— 哈希表。
由于它不是顺序结构,所以很多数据结构书上称之为 散列表 ,下文会统一采用 哈希表 的形式来说明,作为读者,只需要知道这两者是同一种数据结构即可。 我们把需要 查找的数据 ,通过一个 函数映射 ,找到 存储数据的位置 的过程称为 哈希 。这里涉及到几个概念: a)需要 查找的数据 本身被称为 关键字 ; b)通过 函数映射 将 关键字 变成一个 哈希值 的过程中,这里的 函数 被称为 哈希函数 ; c)生成 哈希值 的过程过程可能产生冲突,需要进行 冲突解决 ; d)解决完冲突以后,实际 存储数据的位置 被称为 哈希地址 ,通俗的说,它就是一个数组下标; e)存储所有这些数据的数据结构就是 哈希表 ,程序实现上一般采用数组实现,所以又叫 哈希数组 。整个过程如下图所示:
为了方便下标索引, 哈希表 的底层实现结构是一个数组,数组类型可以是任意类型,每个位置被称为一个槽。如下图所示,它代表的是一个长度为 8 的 哈希表 ,又叫 哈希数组 。
关键字 是哈希数组中的元素,可以是任意类型的,它可以是整型、浮点型、字符型、字符串,甚至是结构体或者类。如下的 A、C、M 都可以是关键字;
int A = 5; char C[100] = "Hello World!"; struct Obj { }; Obj M;
哈希表的实现过程中,我们需要通过一些手段,将一个非整型的 关键字 转换成 数组下标 ,也就是 哈希值 ,从而通过 O ( 1 ) O(1) O(1) 的时间快速索引到它所对应的位置。 而将一个非整型的 关键字 转换成 整型 的手段就是 哈希函数 。
哈希函数可以简单的理解为就是小学课本上那个函数,即 y = f ( x ) y = f(x) y=f(x),这里的 f ( x ) f(x) f(x) 就是哈希函数, x x x 是关键字, y y y 是哈希值。好的哈希函数应该具备以下两个特质: a)单射; b)雪崩效应:输入值 x x x 的 1 1 1 比特的变化,能够造成输出值 y y y 至少一半比特的变化; 单射很容易理解,图 ( a ) (a) (a) 中已知哈希值 y y y 时,键 x x x 可能有两种情况,不是一个单射;而图 ( b ) (b) (b) 中已知哈希值 y y y 时,键 x x x 一定是唯一确定的,所以它是单射。由于 x x x 和 y y y 一一对应,这样就从本原上减少了冲突。 雪崩效应是为了让哈希值更加符合随机分布的原则,哈希表中的键分布的越随机,利用率越高,效率也越高。 常用的哈希函数有: 直接定址法 、 除留余数法 、 数字分析法 、 平方取中法 、 折叠法 、 随机数法 等等。有关哈希函数的内容,下文会进行详细讲解。
哈希函数在生成 哈希值 的过程中,如果产生 不同的关键字得到相同的哈希值 的情况,就被称为 哈希冲突 。 即对于哈希函数 y = f ( x ) y = f(x) y=f(x),当关键字 x 1 ≠ x 2 x_1 \neq x_2 x1=x2,但是却有 f ( x 1 ) = f ( x 2 ) f(x_1) = f(x_2) f(x1)=f(x2),这时候,我们需要进行冲突解决。 冲突解决方法有很多,主要有: 开放定址法 、 再散列函数法 、 链地址法 、 公共溢出区法 等等。有关解决冲突的内容,下文会进行详细讲解。
哈希地址 就是一个 数组下标 ,即哈希数组的下标。通过下标获得数据,被称为 索引 。通过数据获得下标,被称为 哈希 。平时工作的时候,和同事交流时用到的一个词 反查 就是说的 哈希 。
直接定址法 就是 关键字 本身就是 哈希值 ,表示成函数值就是 f ( x ) = x f(x) = x f(x)=x 例如,我们需要统计一个字符串中每个字符的出现次数,就可以通过这种方法。任何一个字符的范围都是 [ 0 , 255 ] [0, 255] [0,255],所以只要用一个长度为 256 的哈希数组就可以存储每个字符对应的出现次数,利用一次遍历枚举就可以解决这个问题。C代码实现如下:
int i, hash[256]; for(i = 0; str[i]; ++i) { ++hash[ str[i] ]; }
这个就是最基础的直接定址法的实现。hash[c]代表字符c在这个字符串str中的出现次数。
hash[c]
c
str
平方取中法 就是对 关键字 进行平方,再取中间的某几位作为 哈希值 。 例如,对于关键字 1314 1314 1314,得到平方为 1726596 1726596 1726596,取中间三位作为哈希值,即 265 265 265。 平方取中法 比较适用于 不清楚关键字的分布,且位数也不是很大 的情况。
折叠法 是将关键字分割成位数相等的几部分(注意最后一部分位数不够可以短一些),然后再进行求和,得到一个 哈希值 。 例如,对于关键字 5201314 5201314 5201314,将它分为四组,并且相加得到: 52 + 01 + 31 + 4 = 88 52+01+31+4 = 88 52+01+31+4=88,这就是哈希值。 折叠法 比较适用于 不清楚关键字的分布,但是关键字位数较多 的情况。
除留余数法 就是 关键字 模上 哈希表 长度,表示成函数值就是 f ( x ) = x m o d m f(x) = x \ mod \ m f(x)=x mod m 其中 m m m 代表了哈希表的长度,这种方法,不仅可以对关键字直接取模,也可以在 平方取中法、折叠法 之后再取模。 例如,对于一个长度为 4 的哈希数组,我们可以将关键字 模 4 得到哈希值,如图所示:
哈希数组的长度一般选择 2 的幂,因为我们知道取模运算是比较耗时的,而位运算相对较为高效。 选择 2 的幂作为数组长度,可以将 取模运算 转换成 二进制位与。 令 m = 2 k m = 2^k m=2k,那么它的二进制表示就是: m = ( 1 000...000 ⏟ k ) 2 m = (1\underbrace{000...000}_{\rm k})2 m=(1k 000...000)2,任何一个数模上 m m m,就相当于取了 m m m 的二进制低 k k k 位,而 m − 1 = ( 111...111 ⏟ k ) 2 m-1 = (\underbrace{111...111}{\rm k})_2 m−1=(k 111...111)2 ,所以和 位与 m − 1 m-1 m−1 的效果是一样的。即: x % S = = x & ( S − 1 ) x \ \% \ S == x \ \& \ (S - 1) x % S==x & (S−1) 除了直接定址法,其它三种方法都有可能导致哈希冲突,接下来,我们就来讨论下常用的一些哈希冲突的解决方案。
开放定址法 就是一旦发生冲突,就去寻找下一个空的地址,只要哈希表足够大,总能找到一个空的位置,并且记录下来作为它的 哈希地址 。公式如下: f i ( x ) = ( f ( x ) + d i ) m o d m f_i(x) = (f(x)+d_i) \ mod \ m fi(x)=(f(x)+di) mod m 这里的 d i d_i di 是一个数列,可以是常数列 ( 1 , 1 , 1 , . . . , 1 ) (1, 1, 1, ...,1) (1,1,1,...,1),也可以是等差数列 ( 1 , 2 , 3 , . . . , m − 1 ) (1,2,3,...,m-1) (1,2,3,...,m−1)。
上图中,采用的是哈希函数算法是 除留余数法 ,采用的哈希冲突解决方案是 开放定址法 ,哈希表的每个数据就是一个关键字,插入之前需要先进行查找,如果找到的位置未被插入,则执行插入;否则,找到下一个未被插入的位置进行插入;总共插入了 6 个数据,分别为:11、12、13、20、19、28。 这种方法需要注意的是,当插入数据超过哈希表长度时,不能再执行插入。
本文在第四章讲解 哈希表的现实 时采用的就是常数列的开放定址法。
再散列函数法 就是一旦发生冲突,就采用另一个哈希函数,可以是 平方取中法、折叠法、除留余数法 等等的组合,一般用两个哈希函数,产生冲突的概率已经微乎其微了。 再散列函数法 能够使关键字不产生聚集,当然,也会增加不少哈希函数的计算时间。
当然,产生冲突后,我们也可以选择不换位置,还是在原来的位置,只是把 哈希值 相同的用链表串联起来。这种方法被称为 链地址法 。
上图中,采用的是哈希函数算法是 除留余数法 ,采用的哈希冲突解决方案是 链地址法 ,哈希表的每个数据保留了一个 链表头结点 和 尾结点 ,插入之前需要先进行查找,如果找到的位置,链表非空,则插入尾结点并且更新尾结点;否则,生成一个新的链表头结点和尾结点;总共插入了 6 个数据,分别为:11、12、13、20、19、28。
一旦产生冲突的数据,统一放到另外一个顺序表中,每次查找数据,在哈希数组中到的关键字和给定关键字相等,则认为查找成功;否则,就去公共溢出区顺序查找,这种方法被称为 公共溢出区法 。
内存结构 :看用数组实现,还是链表实现 实现难度 :一般 下标访问 :不支持 分类 :FIFO、单调队列、双端队列 插入时间复杂度 : O ( 1 ) O(1) O(1) 查找时间复杂度 :理论上不支持 删除时间复杂度 : O ( 1 ) O(1) O(1)
队列 是仅限在 一端 进行 插入 , 另一端 进行 删除 的 线性表 。 队列 又被称为 先进先出 (First In First Out) 的线性表,简称 FIFO 。
允许进行元素删除的一端称为 队首 。如下图所示:
允许进行元素插入的一端称为 队尾 。如下图所示:
队列的插入操作,叫做 入队 。它是将 数据元素 从 队尾 进行插入的过程,如图所示,表示的是 插入 两个数据(绿色 和 蓝色)的过程:
队列的删除操作,叫做 出队 。它是将 队首 元素进行删除的过程,如图所示,表示的是 依次 删除 两个数据(红色 和 橙色)的过程:
队列的清空操作,就是一直 出队 ,直到队列为空的过程,当 队首 和 队尾 重合时,就代表队尾为空了,如图所示:
对于一个队列来说只能获取 队首 数据,一般不支持获取 其它数据。
队列元素个数一般用一个额外变量存储, 入队 时加一, 出队 时减一。这样获取队列元素的时候就不需要遍历整个队列。通过 O ( 1 ) O(1) O(1) 的时间复杂度获取队列元素个数。
当队列元素个数为零时,就是一个 空队 , 空队 不允许 出队 操作。
内存结构 :看用数组实现,还是链表实现 实现难度 :一般 下标访问 :不支持 分类 :FILO、单调栈 插入时间复杂度 : O ( 1 ) O(1) O(1) 查找时间复杂度 :理论上不支持 删除时间复杂度 : O ( 1 ) O(1) O(1)
栈 是仅限在 表尾 进行 插入 和 删除 的 线性表 。 栈 又被称为 后进先出 (Last In First Out) 的线性表,简称 LIFO 。
栈 是一个线性表,我们把允许 插入 和 删除 的一端称为 栈顶 。
和 栈顶 相对,另一端称为 栈底 ,实际上,栈底的元素我们不需要关心。
栈的插入操作,叫做 入栈 ,也可称为 进栈、压栈。如下图所示,代表了三次入栈操作:
栈的删除操作,叫做 出栈 ,也可称为 弹栈。如下图所示,代表了两次出栈操作:
一直 出栈 ,直到栈为空,如下图所示:
对于一个栈来说只能获取 栈顶 数据,一般不支持获取 其它数据。
栈元素个数一般用一个额外变量存储, 入栈 时加一, 出栈 时减一。这样获取栈元素的时候就不需要遍历整个栈。通过 O ( 1 ) O(1) O(1) 的时间复杂度获取栈元素个数。
当栈元素个数为零时,就是一个空栈,空栈不允许 出栈 操作。
优先队列 是 堆实现的,所以也属于 二叉树 范畴。它和队列不同,不属于线性表。 内存结构 :内存结构一般不连续,但是有时候实现的时候,为了方便,一般是物理连续,逻辑不连续 实现难度 :较难 下标访问 :不支持 分类 :二叉树 和 多叉树 插入时间复杂度 :看情况而定 查找时间复杂度 :理论上 O ( l o g 2 n ) O(log_2n) O(log2n) 删除时间复杂度 :看情况而定
内存结构 :内存结构一般不连续,但是有时候实现的时候,为了方便,一般是物理连续,逻辑不连续 实现难度 :较难 下标访问 :不支持 分类 :二叉树 和 多叉树 插入时间复杂度 :看情况而定 查找时间复杂度 :理论上 O ( l o g 2 n ) O(log_2n) O(log2n) 删除时间复杂度 :看情况而定
内存结构 :不一定 实现难度 :难 下标访问 :不支持 分类 :有向图、无向图 插入时间复杂度 :根据算法而定 查找时间复杂度 :根据算法而定 删除时间复杂度 :根据算法而定
1、图的概念
2、图的存储
1)邻接矩阵
2)邻接表
如图所示, d a t a data data 即 ( v , w ) (v, w) (v,w) 二元组,代表和对应顶点 u u u 直接相连的顶点数据, w w w 代表 u → v u \to v u→v 的边权, n e x t next next 是一个指针,指向下一个 ( v , w ) (v, w) (v,w) 二元组。
在 C++ 中,还可以使用 vector 这个容器来代替链表的功能;
vector<Edge> edges[maxn];
3)前向星
如图所示,表示的是三元组 ( u , v , w ) (u, v, w) (u,v,w) 的数组, i d x idx idx 代表数组下标。
那么用哪种数据结构才能满足所有图的需求呢?
4)链式前向星
edge[maxm]
maxm
head[i]
struct Edge { int u, v, w, next; Edge() {} Edge(int _u, int _v, int _w, int _next) : u(_u), v(_v), w(_w), next(_next) { } }edge[maxm];
head[i] = -1
edgeCount = 0
addEdge(u, v, w)
void addEdge(int u, int v, int w) { edge[edgeCount] = Edge(u, v, w, head[u]); head[u] = edgeCount++; }
edge
next
for (int e = head[u]; ~e; e = edges[e].next) { int v = edges[e].v; ValueType w = edges[e].w; ... }
~e
e != -1
e
I、例题描述
给你两个有序整数数组 n u m s 1 nums1 nums1 和 n u m s 2 nums2 nums2,请你将 n u m s 2 nums2 nums2 合并到 n u m s 1 nums1 nums1 中,使 n u m s 1 nums1 nums1 成为一个有序数组。初始化 n u m s 1 nums1 nums1 和 n u m s 2 nums2 nums2 的元素数量分别为 m m m 和 n n n 。你可以假设 n u m s 1 nums1 nums1 的空间大小等于 m + n m + n m+n,这样它就有足够的空间保存来自 n u m s 2 nums2 nums2 的元素。 样例输入: n u m s 1 = [ 1 , 2 , 3 , 0 , 0 , 0 ] , m = 3 , n u m s 2 = [ 2 , 5 , 6 ] , n = 3 nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 nums1=[1,2,3,0,0,0],m=3,nums2=[2,5,6],n=3 样例输出: [ 1 , 2 , 2 , 3 , 5 , 6 ] [1,2,2,3,5,6] [1,2,2,3,5,6] 原题出处: LeetCode 88. 合并两个有序数组
II、基础框架
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { } };
III、思路分析
IV、时间复杂度
IV、源码详解
class Solution { public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for(int i = m; i < n + m; ++i) { nums1[i] = nums2[i-m]; // (1) } sort(nums1.begin(), nums1.end()); // (2) } };
VI、本题小知识
只要能够达到最终的结果, O ( n ) O(n) O(n) 和 O ( n l o g 2 n ) O(nlog_2n) O(nlog2n) 的差距其实并没有那么大。只要是和有序相关的,就可以调用这个函数,直接就出来了。
给定单链表的头节点 h e a d head head ,要求反转链表,并返回反转后的链表头。 样例输入: [ 1 , 2 , 3 , 4 ] [1,2,3,4] [1,2,3,4] 样例输出: [ 4 , 3 , 2 , 1 ] [4, 3, 2, 1] [4,3,2,1] 原题出处: LeetCode 206. 反转链表
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { } };
val
如图所示:
我们发现,图中的蓝色指针永远固定在最开始的链表头结点上,那么可以以它为契机,每次删除它的next,并且插到最新的头结点前面,不断改变头结点head的指向,迭代 n − 1 n-1 n−1 次就能得到答案了。
V、源码详解
class Solution { ListNode *removeNextAndReturn(ListNode* now) { // (1) if(now == nullptr || now->next == nullptr) { return nullptr; // (2) } ListNode *retNode = now->next; // (3) now->next = now->next->next; // (4) return retNode; } public: ListNode* reverseList(ListNode* head) { ListNode *doRemoveNode = head; // (5) while(doRemoveNode) { // (6) ListNode *newHead = removeNextAndReturn(doRemoveNode); // (7) if(newHead) { // (8) newHead->next = head; head = newHead; }else { break; // (9) } } return head; } };
ListNode *removeNextAndReturn(ListNode* now)
now
doRemoveNode
复杂问题简单化的最好办法就是将问题拆细,比如这个问题中,将一个节点取出来插到头部这件事情可以分为两步: 1)删除给定节点; 2)将删除的节点插入头部;
编写一个函数,将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 样例输入: [ “ a ” , “ b ” , “ c ” , “ d ” ] [“a”, “b”, “c”, “d”] [“a”,“b”,“c”,“d”] 样例输出: [ “ d ” , “ c ” , “ b ” , “ a ” ] [ “d”, “c”, “b”, “a”] [“d”,“c”,“b”,“a”] 原题出处: LeetCode 344. 反转字符串
class Solution { public: void reverseString(vector<char>& s) { } };
翻转的含义,相当于就是 第一个字符 和 最后一个交换,第二个字符 和 最后第二个交换,… 以此类推,所以我们首先实现一个交换变量的函数 swap,然后再枚举 第一个字符、第二个字符、第三个字符 …… 即可。 对于第 i i i 个字符,它的交换对象是 第 l e n − i − 1 len-i-1 len−i−1 个字符 (其中 l e n len len 为字符串长度)。swap函数的实现
swap
class Solution { public: void swap(char& a, char& b) { // (1) char tmp = a; a = b; b = tmp; } void reverseString(vector<char>& s) { int len = s.size(); for(int i = 0; i < len / 2; ++i) { // (2) swap(s[i], s[len-i-1]); } } };
&
简而言之,函数调用的参数,可以传引用,从而使得函数返回时,传参值的改变依旧生效。
函数调用的参数,可以传引用,从而使得函数返回时,传参值的改变依旧生效。
软件开发的时候,会有版本的概念。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。假设你有 n n n 个版本 [ 1 , 2 , . . . , n ] [1, 2, ..., n] [1,2,...,n],你想找出导致之后所有版本出错的第一个错误的版本。可以通过调用bool isBadVersion(version)接口来判断版本号version是否在单元测试中出错。实现一个函数来查找第一个错误的版本。应该尽量减少对调用 API 的次数。 样例输入: 5 5 5 和 b a d = 4 bad = 4 bad=4 样例输出: 4 4 4 原题出处: LeetCode 278. 第一个错误的版本
bool isBadVersion(version)
version
bool isBadVersion(int version)
true
false
// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { } };
归纳总结为 2 种情况,如下: 1)当前二分到的位置 m i d mid mid,给出的版本是错误,那么从当前位置以后的版本不需要再检测了(因为一定也是错误的),并且我们可以肯定,出错的位置一定在 [ l , m i d ] [l, mid] [l,mid];并且 m i d mid mid 是一个可行解,记录下来; 2)当前二分到的位置 m i d mid mid,给出的版本是正确,则出错位置可能在 [ m i d + 1 , r ] [mid+1, r] [mid+1,r];
// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { long long l = 1, r = n; // (1) long long ans = (long long)n + 1; while(l <= r) { long long mid = (l + r) / 2; if( isBadVersion(mid) ) { ans = mid; // (2) r = mid - 1; }else { l = mid + 1; // (3) } } return ans; } };
long long
VI、本题小知识 二分时,如果区间范围过大,int难以招架时,需要动用long long;
《算法和数据结构》数据结构到底有多重要介绍到这里,更多java学习请参考编程字典java教程和问答部分,谢谢大家对编程字典的支持。
原文链接:https://blog.csdn.net/WhereIsHeroFrom/article/details/120192935