干货！高频手撕算法合集来了

作者 | L的存在

来源 | 我是程序员小贱(ID:Lanj1995Q)

基础数据结构的融合是成为庞大系统的基石。比如Redis中的跳跃表，数据库索引B+树等，只有对基础的数据结构足够的熟悉才能更容易去理解稍微复杂的结构，就仿佛我们闯关打怪一样，一步一步解锁直到结局。今天想和大家一起分享的是常见数据结构以及面试中的高频手撕算法题，一定要去手动写这些代码，可说百分之七八十都是这些题，一定要好好掌握。

高频手撕算法合集

数据结构

链表属于数据结构中的线性结构的一种，我们先看看什么是数据结构

• 数据结构是：结构的定义+结构的操作

想必大伙儿应该玩儿过拼图，拼图之前我们先看看说明书，看看包含几个部分，然后对这些部分进行拼装，随后拼好候进行组合直到完成。

那么数据结构中的结构定义是这个数据结构长什么样子，有些什么性质？结构的操作意思是这个结构可以支持什么操作，但是不管你怎么的操作，不能破坏了它的结构。

链表定义

一个链表是由1个或者多个节点组成，每个节点包含两个信息，一个是数据信息，用来存储数据，一个是地址信息，用来存储下个节点的地址。

链表节点

链表结构由一个个节点组成，我们不需要对结构做任何改变，只需要按照需求修改链表结构中的数据域即可。从上图我们知道此事数据域类型为整型763，指针域为0x56432，这个地址正好是第二个节点的地址，所以这两个节点在逻辑上是有个指向关系，也是通过这种方式将两个节点进行了关联。

第二个节点中的指针域为0x0，这是一个特殊的地址，叫做空地址，指向空地址意味着它是这个链表结构的最后一个节点。

那在代码中是什么样子呢？

struct Node {
    int data;
    struct Node *next;
};

这个结构很清晰，数据域根据我们的需求而定，想存整型就改成整型，想存字符串就写字符串。而指针域用来维护整个链表结构，一般来说直接用即可，如果需要内存中的链表结构，一定要修改节点内部next指针域中存储的地址值。

链表操作

说到链表结构，我们习惯性的和数组联系在一起。只是数组结构在内存中是连续的，而链表结构因为指针域的存在，每个节点在内存中存储的位置未必连续。下面我们按照数组的方式给链表也编个号。

单链表

下面我们定义一个向链表插入节点的函数

struct Node *insert(struct Node *head, int ind, struct Node *a);

• 第一个参数为待操作的链表的头结点地址，也就是第一个节点的地址。

• 第二个参数为插入位置。

• 第三个参数为指针变量，指向要插入的新节点。

简单的说就是向 head 指向的链表的 ind 位置插入一个由 a 指向的节点，返回值为插入新节点后的表头地址。为什么要返回它呢？因为我们插入的节点很可能在头部，此时就会改变链表的结构且改变头结点地址，所以需要返回。

那么我们插入一个元素，显然会改变链表的节点，操作方法为修改链表节点的 next 指针域即可，那么为了插入成功，我们需要修改哪些节点呢？

首先是让 ind - 1 位置的节点指向 a 节点，然后是 a 节点指向原 ind 位置的节点，也就是说，涉及到两个节点的 next 指针域的值的修改，一个是 ind - 1 位置的节点，一个是 a 节点自身。我们就可以先找到 ind - 1 位置的节点，然后再进行相关操作即可。

struct Node *insert(struct Node *head, int ind, struct Node *a) {
    struct Node ret, *p = &ret;
    ret.next = head;
    // 从虚拟头节点开始向后走 ind 步
    while (ind--) p = p->next;
    // 完成节点的插入操作
    a->next = p->next;
    p->next = a;
    // 返回真正的链表头节点地址
    return ret.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每次走两步，如果快的指针先跑到终点注定没有环，如果两指针相遇则有环。

int hasCycle(struct Node *head) {
    if (head == NULL) return 0;
    // p 是慢指针，q 是快指针
    struct Node *p = head, *q = head;
    // 每次循环，p 走1步，q 走2步
    do {
            p = p->next;
            q = q->next;
            if (q == NULL) return 0;
            q = q->next;
        } while (p != q && q);
    return p == 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、 第一种小白写法

int BinarySerach(vector& nums,int n, int target) {
    int left = 0, right = n-1;
    while (left 1).
 
  
  
  
哪有这么简单的事儿，大多数的笔试面试中可能会出现下面的几种情况。
 
  
  
 
 
 二分的各种变种 
 
这里主要是看看原始数组有重复数的情况。
 
  
 
二分
 
 
1、查找第一个值等于给定值的情况(查找元素7)思路
 
  
  
首先7与中间值a[4]比较，发现小于7，于是在5到9中继续查找，中间a[7]=7,但是这个数7不是第一次出现的。那么我们检查这个值的前面是不是等于7，如果等于7，说明目前这个值不是第一次出现的7，此时更新rihgt=mid-1。ok我们看看代码。
 
  
 
int BinarySerach(vector& nums, int n,int target) {
    int left = 0, right = n-1;
    while (left >1);
        if (nums[mid]>value)
        {
            right=mid-1;
        } else if(nums[mid]1);
        if (nums[mid]>value)
        {
            right=mid-1;
        } else if(nums[mid]1);
        if (nums[mid]>value)
        {
            right=mid-1;
        } else if(nums[mid]1);
        if (nums[mid]>=value)
        {
            if(mid==0||nums[mid-1]1);
        if (nums[mid]>value)
        {
            right=mid-1;
        }else
        {
            if(mid==n-1||(nums[mid+1]>value))
            {
                return mid;
            }else
            {
                left=mid+1;
            }
        }
    return -1;
}

 
  
 
 
 队列 
  
  
例子：滑动窗口最大值
 
  
 
队列回忆：
 
  
  
火车站买票应该都经历过，窗口小姐姐每次服务排在最前面的那个人，买完票则从头部离开，后面人往前一步接替离开的人继续购票，这就是典型的队列结构。
 
  
 
计算机中的队列和其类似，先到先得，先入先出，每个元素从尾部入队，从头部处理完出队。
 
  
 
队列定义
 
 
单调队列
 
  
  
假设将学生从高年级到低年级排列，随着时间的推移，高年级同学从队列头部毕业，低年级从尾部进入。大部分学校都有校队，假设小林高三，我高二，小七高一，小林毕业接班的是我，我毕业，很可能就是小七接班，而当我进队的那一刻，小七即使进的早但是战斗力没我高，所以小七是永远没计划被选中啦。所以，纵观全队，不仅有着队列的性质，也有着单调的性质，所以就是单调队列。
 
  
 
为什么需要单调队列
 
  
  
比较明显的作用是，用来维护队列处理顺序中的区间最大值。
 
  
 
高频面试题----滑动窗口最大值
 
  
  
滑动窗口没向后滑动一位，就有一个元素从队首出队，同时也会有个元素从队尾入队。这个题需要求区间的最大值：意味着需要维护在队列处理顺序中的区间最大值，直接上代码附上注释。
 
  
 
#define MAX_N 1000
int q[MAX_N + 5], head, tail;
void interval_max_number(int *a, int n, int m) {
    head = tail = 0;
    for (int i = 0; i