作者
L的存在
来源
我是程序员小贱(ID:LanjQ)
基础数据结构的融合是成为庞大系统的基石。比如Redis中的跳跃表，数据库索引B+树等，只有对基础的数据结构足够的熟悉才能更容易去理解稍微复杂的结构，就仿佛我们闯关打怪一样，一步一步解锁直到结局。今天想和大家一起分享的是常见数据结构以及面试中的高频手撕算法题，一定要去手动写这些代码，可说百分之七八十都是这些题，一定要好好掌握。
高频手撕算法合集
数据结构
链表属于数据结构中的线性结构的一种，我们先看看什么是数据结构
数据结构是：结构的定义+结构的操作想必大伙儿应该玩儿过拼图，拼图之前我们先看看说明书，看看包含几个部分，然后对这些部分进行拼装，随后拼好候进行组合直到完成。
那么数据结构中的结构定义是这个数据结构长什么样子，有些什么性质？结构的操作意思是这个结构可以支持什么操作，但是不管你怎么的操作，不能破坏了它的结构。
链表定义
一个链表是由1个或者多个节点组成，每个节点包含两个信息，一个是数据信息，用来存储数据，一个是地址信息，用来存储下个节点的地址。
链表节点
链表结构由一个个节点组成，我们不需要对结构做任何改变，只需要按照需求修改链表结构中的数据域即可。从上图我们知道此事数据域类型为整型，指针域为0x，这个地址正好是第二个节点的地址，所以这两个节点在逻辑上是有个指向关系，也是通过这种方式将两个节点进行了关联。
第二个节点中的指针域为0x0，这是一个特殊的地址，叫做空地址，指向空地址意味着它是这个链表结构的最后一个节点。
那在代码中是什么样子呢？
structNode{
intdata;
structNode*next;
};
这个结构很清晰，数据域根据我们的需求而定，想存整型就改成整型，想存字符串就写字符串。而指针域用来维护整个链表结构，一般来说直接用即可，如果需要内存中的链表结构，一定要修改节点内部next指针域中存储的地址值。
链表操作
说到链表结构，我们习惯性的和数组联系在一起。只是数组结构在内存中是连续的，而链表结构因为指针域的存在，每个节点在内存中存储的位置未必连续。下面我们按照数组的方式给链表也编个号。
单链表
下面我们定义一个向链表插入节点的函数
structNode*insert(structNode*head,intind,structNode*a);
第一个参数为待操作的链表的头结点地址，也就是第一个节点的地址。第二个参数为插入位置。第三个参数为指针变量，指向要插入的新节点。简单的说就是向head指向的链表的ind位置插入一个由a指向的节点，返回值为插入新节点后的表头地址。为什么要返回它呢？因为我们插入的节点很可能在头部，此时就会改变链表的结构且改变头结点地址，所以需要返回。
那么我们插入一个元素，显然会改变链表的节点，操作方法为修改链表节点的next指针域即可，那么为了插入成功，我们需要修改哪些节点呢？
首先是让ind-1位置的节点指向a节点，然后是a节点指向原ind位置的节点，也就是说，涉及到两个节点的next指针域的值的修改，一个是ind-1位置的节点，一个是a节点自身。我们就可以先找到ind-1位置的节点，然后再进行相关操作即可。
structNode*insert(structNode*head,intind,structNode*a){
structNoderet,*p=ret;
ret.next=head;
//从虚拟头节点开始向后走ind步
while(ind--)p=p-next;
//完成节点的插入操作
a-next=p-next;
p-next=a;
//返回真正的链表头节点地址
returnret.next;
}
这里非常关心且非常重要的是虚拟节点。我们为什么引入虚拟节点？是为了让我们的插入操作统一化？什么是统一化？举个例子，假设我们现在是在第5个位置插入元素，我们自然需要从头遍历到第四个节点，确定了第四个节点后，修改相关的next指针域，也就是如果我们想插入到nid位，就需要从头节点向后移动ind-1步，那么如果插入的位置为0呢？我们总不能走-1步吧，所以这个时候我们只好对ind=0的情况进行单独的判断了，这样明显是不完美了，所以我们为了统一ind在等于0和不等于0时的情况，引入虚拟节点。
ok，我们看看是不是方便了。增加了虚拟节点，如果插入第5个位置，我们只需要向后移动5位，如果插入到0号位置，向后移动0步即可，即p指针指向虚拟节点不懂，直接将新的节点插入到虚拟头结点后面完事儿。
虚拟节点
好勒，这里出现了第一个重要的技巧。在我们插入链表节点的时候，加上虚拟节点是个实用技巧。
那么我们看看插入和删除的操作动态以及实现方式。
案例
案例1
我们看个题吧，定义一个快乐数，什么是快乐数，所谓快乐数即通过有限次变换后等于1的数字。怎么变换呢，给出一个非1的数字，然后出去位数，求各个位数的平方和，得到数字A，假设A不死1，那就继续对元素A的每一位进行平方和，得到数字B。。。。知道最后能够=1。
例如，一开始的数字是19，经过变换规则，得到数字82；因为不是1，所以接着做变换，就是，再做一次变换，最后一次做变换，得到了1以后，停止。
这个题的难点不是判断数是不是快乐数，而是如何判断一个数不是快乐数，如果不是快乐数，说明没有办法通过有限的次数到达数字1，那么到底是经过多少次呢？1k次，10w次？很难确定上限。在说这个问题之前我们先看几个高频链表练习题。
例题1用数组判断链表中是否有环
在上面我们介绍了最后一个节点指向空，可是你有没有想过如果链表的最后一个节点不是空地址而是指向链表中的一个节点，这不就是环了？
链表环
如上图所示，节点8指向了3，这样形成了3,4,5,6,7,8的环状结构，此时使用指针遍历链表将永无止境。那通过什么办法判断是否有环呢？
使用数组标记的方法。记录出现过的节点信息，每次遍历新节点就去数组查看记录，这样的时间复杂度不给力。经过第一个节点，需要在数组查找0次，第2个节点，数组查找1次，第i个节点，在数组查找i-1次，直到遍历第n+1个节点，查找的总次数为(n+1)*n/2，这样时间复杂度为O(n^2)。太慢了，给我优化。快慢指针法。AB两位同学跑步，A同学速度快，B同学速度慢，他们并不知道跑道是环形的，如果是环形，跑得快的，在足够的时间终究会从速度慢的B同学经过，形成相遇的情况。如果不是环形，速度快的先到重点，不会相遇---快慢指针法。
快慢指针
在这里，我们将链表当做跑道，跑道上两个指针，指针A每次走两步，指针B每次走两步，如果快的指针先跑到终点注定没有环，如果两指针相遇则有环。
inthasCycle(structNode*head){
if(head==)return0;
//p是慢指针，q是快指针
structNode*p=head,*q=head;
//每次循环，p走1步，q走2步
do{
p=p-next;
q=q-next;
if(q==)return0;
q=q-next;
}while(p!=qq);
returnp==q;
}
二分查找初探
说到二分查找，这里就有个笑话了。
小孙同学去图书馆借书，一次性了借了40本书，出图书馆的时候报警了，不知道哪一本书没有消磁，然后把书放在地上，准备一本本尝试。
女生的操作被旁边的阿姨看见了，阿姨说你这样操作多慢啊，我来教你。于是将树分为两摞，拿出第一luo过一下安检，安检机器想了，于是阿姨将这摞书分成两部分，拿出一部分继续尝试，就这样，阿姨每次减少一半，没几次就找到了没有消磁的书。阿姨嘚瑟的来一句：小姑凉，这就是书中的二分查找算法，你这还得好好学习哇，第二天，图书馆发现丢了39本书。哈哈哈哈。
二分查找基础
最简单的二分算法即在一个有序数组中，查找一个数字X是否存在。注意有序性。那么如何在数组中查找一个数。
从头到尾一个一个查找，找到即有数字x。二分算法即通过确定一个区间，然后查找区间的一半和x比较，如果比x大则在x前半段查找。如果比x小则在后半段查找，只需要log2n的比较即可确定结果。
二分初探
图中呢，我们以查找17这个数字为例，L和R所圈定的，就是当前的查找区间，一开始L=0，R=6，mid所指向的就是数组的中间位置，根据L和R计算得到mid的值是3。查看数组第3位的值是12，比待查找值17要小，说明如果17在这个有序数组中，那它一定在mid所指向位置的后面，而mid本身所指向的数字已经确定不是17了，所以下一次我们可以将查找区间，定位到mid+1到R，也就是将L调整到mid+1（即数组第4位）的位置。
1、第一种小白写法
intBinarySerach(vectorintnums,intn,inttarget){
intleft=0,right=n-1;
while(left=right){
intmid=(left+right)/2;
if(nums[mid]==target)returnmid;
elseif(nums[mid]target)left=mid+1;
elseright=mid-1;
}
return-1;
}
面试官发话了：可以优化下。
2.方法二优化版
如果right和left比较的时候，两者之和可能溢出。那么改进的方法是mid=left+(right-left)/2.还可以继续优化，我们将除以2这种操作转换为位运算mid=left+((right-left)1).
哪有这么简单的事儿，大多数的笔试面试中可能会出现下面的几种情况。
二分的各种变种
这里主要是看看原始数组有重复数的情况。
二分
1、查找第一个值等于给定值的情况(查找元素7)
思路
首先7与中间值a[4]比较，发现小于7，于是在5到9中继续查找，中间a[7]=7,但是这个数7不是第一次出现的。那么我们检查这个值的前面是不是等于7，如果等于7，说明目前这个值不是第一次出现的7，此时更新rihgt=mid-1。ok我们看看代码。
intBinarySerach(vectorintnums,intn,inttarget){
intleft=0,right=n-1;
while(left=right){
intmid=left+((right-left)1);
if(nums[mid]value)
{
right=mid-1;
}elseif(nums[mid]value)
{
left=mid+1;
}else
{
if((mid==0)
(nums[mid-1]!=value))
{
returnmid;
}else
{
left=mid-1;
}
}
return-1;
}
2、查找最后一个值等于给定值的情况
假设nums[mid]这个值已经是最后一个元素了，那么它肯定是要找到最后一个值。如果nums[mid]的下一个不等于value，那说明nums[mid]就是我们需要找到最后一个等于给定值的值。
intBinarySerach(vectorintnums,intn,inttarget){
intleft=0,right=n-1;
while(left=right){
intmid=left+((right-left)1);
if(nums[mid]value)
{
right=mid-1;
}elseif(nums[mid]value)
{
left=mid+1;
}else
{
if((mid==n-1)
(nums[mid+1]!=value))
{
returnmid;
}else
{
left=mid+1;
}
}
return-1;
}
3、查找第一个大于等于给定值的情况
如果nums[mid]小于要查找的值，那么我们需要查找在[mid+1,right]之间，所以此时更新为left=mid+1。如果nums[mid]大于给定值value,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素，如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值。如果nums[mid-1]也是大于等于查找的值，那么说明查找的元素在[left,mid-1]之间，所以我们需要将right更新为mid-1。intBinarySerach(vectorintnums,intn,inttarget){
intleft=0,right=n-1;
while(left=right){
intmid=left+((right-left)1);
if(nums[mid]value)
{
right=mid-1;
}elseif(nums[mid]value)
{
left=mid+1;
}else
{
if((mid==n-1)
(nums[mid+1]!=value))
{
returnmid;
}else
{
left=mid+1;
}
}
return-1;
}
4、查找第一个大于等于给定值的情况
如果nums[mid]小于要查找的值，那么我们需要查找在[mid+1,right]之间，所以此时更新为left=mid+1。如果nums[mid]大于给定值value,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素，如果nums[mid]前面没有元素或者前面一个元素小于查找的值，那么nums[mid]就是我们需要查找的值。如果nums[mid-1]也是大于等于查找的值，那么说明查找的元素在[left,mid-1]之间，所以我们需要将right更新为mid-1。intBinarySerach(vectorintnums,intn,inttarget){
intleft=0,right=n-1;
while(left=right){
intmid=left+((right-left)1);
if(nums[mid]=value)
{
if(mid==0
nums[mid-1]value)
{
returnmid;
}else
{
right=mid-1;
}
}else
{
left=mid+1;
}
return-1;
}
5、查找最后一个小于等于给定值的情况
如果nums[mid]小于查找的值，那么需要查找的值肯定在[mid+1,right]之间，所以我们需要更新left=mid+1。如果nums[mid]大于等于给定的value，检查nums[mid]是不是我们的第一个值大于等于给定值的元素。intBinarySerach(vectorintnums,intn,inttarget){
intleft=0,right=n-1;
while(left=right){
intmid=left+((right-left)1);
if(nums[mid]value)
{
right=mid-1;
}else
{
if(mid==n-1
(nums[mid+1]value))
{
returnmid;
}else
{
left=mid+1;
}
}
return-1;
}
队列
例子：滑动窗口最大值
队列回忆：
火车站买票应该都经历过，窗口小姐姐每次服务排在最前面的那个人，买完票则从头部离开，后面人往前一步接替离开的人继续购票，这就是典型的队列结构。
计算机中的队列和其类似，先到先得，先入先出，每个元素从尾部入队，从头部处理完出队。
队列定义
单调队列
假设将学生从高年级到低年级排列，随着时间的推移，高年级同学从队列头部毕业，低年级从尾部进入。大部分学校都有校队，假设小林高三，我高二，小七高一，小林毕业接班的是我，我毕业，很可能就是小七接班，而当我进队的那一刻，小七即使进的早但是战斗力没我高，所以小七是永远没计划被选中啦。所以，纵观全队，不仅有着队列的性质，也有着单调的性质，所以就是单调队列。
为什么需要单调队列
比较明显的作用是，用来维护队列处理顺序中的区间最大值。
高频面试题----滑动窗口最大值
滑动窗口没向后滑动一位，就有一个元素从队首出队，同时也会有个元素从队尾入队。这个题需要求区间的最大值：意味着需要维护在队列处理顺序中的区间最大值，直接上代码附上注释。
#defineMAX_N
intq[MAX_N+5],head,tail;
voidinterval_max_number(int*a,intn,intm){
head=tail=0;
for(inti=0;in;i++){
//a入队，将违反单调性的从队列q中踢出
while(headtaila[q[tail-1]]a)tail--;
q[tail++]=i;//i入队
//判断队列头部元素是否出了窗口范围
if(i-m==q[head])head++;
//输出区间内最大值
if(i+1=m){
printf(interval(%d,%d),i-m+1,i);
printf(=%d\n,a[q[head]]);
}
}
return;
}
栈与单调栈
栈结构对应于队列，可以将栈想象为一个只有单出口的羽毛球筒，羽毛球只能从单一的入口放入和取出。假设我们将1，2,3三个球放进球桶，如果取出来此时就是3,2,1。性质就很明显了，先进后出的结构。
栈结构本身维护的是一种完全包含的关系。这种包含关系在函数之间的运行体现的玲离尽致，也就是一种包含关系，如果主函数调用函数B，那么函数B一定会在主函数结束之前结束。
单调栈
此时应该了解了栈和队列，那么我问你，你觉得栈和队列最大的区别是啥？
你可能毫不犹豫的可以回答栈是先进后出，队列是先进先出。ok，那我再问你，堵住了出口的单调队列和栈有什么区别？这是不是就没什么区别了，单调队列为了维护其单调性，在入队的时候会将违反单调性的元素弹出去，这就相当于栈的同一段进出，是的，堵住出口的单调队列就是我们现在要说的单调栈，目前以单调递减栈为例。
单调栈
当序列中的12号元素入栈以后，此时单调栈有4个元素，从栈底到栈顶分别为23,18,15,9，按照原始序列为。此时我们