「手撕算法」锁定大厂看这就可

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

高频手撕算法合集

1 数据结构

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

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

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

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

2 链表定义

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

链表节点

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

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

那在代码中是什么样子呢

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

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

3 链表操作

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

单链表

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

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指针指向虚拟节点不懂，直接将新的节点插入到虚拟头结点后面完事儿。

虚拟节点

好勒，这里出现了第一个重要的技巧。在我们插入链表节点的时候，加上虚拟节点是个实用技巧。

那么我们看看插入和删除的操作动态以及实现方式

3 案例

案例1

我们看个题吧，定义一个快乐数，什么是快乐数，所谓快乐数即通过有限次变换后等于1 的数字。怎么变换呢，给出一个非1的数字，然后出去位数，求各个位数的平方和，得到数字A，假设A不死1，那就继续对元素A的每一位进行平方和，得到数字B。。。。知道最后能够=1

例如，一开始的数字是 19，经过变换规则 ，得到数字 82;因为不是 1 ，所以接着做变换，就是 ，再做一次变换 ，最后一次做变换，得到了 1 以后，停止

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!