穿过长长的隧道，便是雪国
0%

408算法题解法

发表于 更新于 分类于
本文字数： 12k 阅读时长 ≈ 10 分钟

说明

本文整合自王道和里昂学长的PPT（无盈利侵权必删），是完整的408代码大题解题方案，整合好的pdf文档可以联系我获取

快速排序

代码实现

王道强化课快速排序代码

快速排序算法以huafen()函数为核心

如何划分？

第一趟

首先将左指针L对应的数组元素设为mid值，我们之后要将mid值和其他值对比然后找到mid值该在的位置

先从R向前寻找第一个小于mid的值（如果没有R- -一直找），如果有，就把他和目前存着mid值的A[L]互换位置

再从L向后寻找第一个大于mid的值（如果没有L++一直找），如果有，就把上一步的A[R]换过来

第二趟

上一趟完成了第一次交换，把小于mid的换到了右边，而把大于mid的换到了左边

第二趟又在新的R找到了小于mid的元素，放在之前发现的左边覆盖，以此类推

最后一趟

当最后一趟开始时，若是L++导致L==R则

A[L]换上了右边更小一点的元素。

而下一步L++，已不满足L<R的条件。而这一步的L就是上一步的R(L==R)，A[R]的值已经迁移到了其左边。

因此设A[L]=mid，就把两者很好的拆开了

当最后一趟开始时，若是R- -导致L==R则

也就是上一趟将**大于mid的A[L]**的值放到右边时，将较大的值换到了A[R]中。

此时R- -到R==L，因此此时A[L]中的存储的是已经是到了还没有**R–**时的右边。

因此A[L]=mid，即可拆开

快速排序算法

因此在快排中调用这段代码

先将A中的LR成以mid为中间的两段，左边小于mid，右边大于mid

我们的划分传来的是mid的位置，因此要想把整个数组排序好，只需要排好左右一直调用。

将数组的最左边L和mid的前一个位置进行划分，穷举下去即可解决

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Qsort(int A[], int L, int R) {
    if(L > R) return; //递归终止
    int M = huafen(A, L, R);
    Qsort(A, L, M-1); //左半部分快排
    Qsort(A, M+1, R); //右半部分快排
}

int hualen(int A[], int L, int R) {
    int mid = A[L];
    while(L < R) {
        while(A[R] >= mid && L < R) R--;//等于号能保证其相对位置不变，稳定性这一块
        A[L] = A[R];
        while(A[L] <= mid && L < R) L++;
        A[R] = A[L];
    }
    A[L] = mid;
    return L;
}

划分函数的妙用

求数组中第k小元素的方法

王道强化课huafen函数

按理说我们只需要快速排序好，再直接利用数组的随机查找特性找到A[k-1]就可以

但是huafen函数可以直接找到某个元素的具体位置，我们可以直接用M接收huafen函数传来的此时的位置

若这个位置比已知位置小，则k-1在M前面，则设L=M+1继续试

1
2
3
4
5
6
7
8
9
10
int func(int A[], int n, int k) {
    int L = 0, R = n - 1, M = 0;
    while(1) {
        M = huafor(A, L, R);
        if(M == k - 1) break;
        else if(M > k - 1) R = M - 1;
        else if(M < k - 1) L = M + 1;
    }
    return A[k-1];
}

归并排序

归并排序用于两个数组排到一个数组里的排序中

归并排序王道强化课

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Merge(int A[], int N, int B[], int M, int C[]) {
    int i = 0, j = 0, k = 0;
    while (i < N && j < M) {
        if (A[i] <= B[j])
            C[k++] = A[i++];
        else
            C[k++] = B[j++];
    }
    while (i < N)
        C[k++] = A[i++];
    while (j < M)
        C[k++] = B[j++];
    return 1;
}

链表

查找+删除

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//删除值为 x 的结点
void deletX(LinkList L, int x) {
    LNode *pre = L; //pre指向p的前驱结点
    LNode *p = pre->next; //p指向下一个要处理的结点
    while (p != NULL) {
        //对当前结点p进行处理
        if (p->data == x) {
            LNode *q = p; //删除并释放值为x的结点
            p = p->next; //p指向后一个结点
            pre->next = p; //修改前驱结点的next指针
            free(q);
        } else {
            pre = p; // pre、p 后移
            p = p->next;
        }
    }
}

查找+插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//在递增有序链表中插入值为 x 的信息
void InsertX(LinkList L, int x) {
    LNode *pre = L; //pre指向p的前驱结点
    LNode *p = pre->next; //p指向下一个要处理的结点
    while (p != NULL) {
        //对当前结点p进行处理
        if (p->data > x) {
            break; //应插入到p的前面
        } else {
            pre = p; // pre, p 后移
            p = p->next;
        }
    }
    LNode *q = (LNode *)malloc(sizeof(LNode));
    q->data = x;
    q->next = p;
    pre->next = q;
}

头插法（原地逆转链表）

在勾画的绿色部分正是逆置的核心出装，将新插入的结点（在原链表中更靠后）不断放前，而实现逆置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ListReserve(LinkList L){
    //分配一个辅助头结点
    LinkList head = (LNode *) malloc(sizeof(LNode));
    head->next = NULL;

    while (L->next != NULL){
        LNode *p = L->next;
        L->next = L->next->next;
        p->next = head->next;
        head->next = p;
    }
    L->next = head->next;
    free(head); //释放辅助头结点
}

尾插法保持原序

以下是我自己写的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void ListPart(LinkList C){
    LinkList A=(LNode*)malloc(sizeof(LNode))//A和B的头结点来也
    LinkList B=(LNode*)malloc(sizeof(LNode))
    A->next=NULL;
    B->next=NULL;
    int count=1;//计数器：判断奇偶结点
    LNode *q=A;//A的尾指针
    while(C->next != NULL){
        if(count%2 == 1)//若为奇数，尾插法
        {
            LNode*p=C->next;//记录目前要拆掉的结点
            C->next=C->next->next;//断开该结点
            q->next=p;//插入尾结点之后
            p->next=NULL;//断掉和原表最后的联系
            q=p;//更新尾指针
            count++;//更新计数值
        }
        if(count%2 == 0)//若为偶数，头插法
        {
        	LNode *p = C->next;//记录目前要拆掉的结点
      	    L->next = C->next->next;//断开该结点
     	    p->next = B->next;//将最新的结点插到最头边，保证逆序
        	B->next = p;//作为头结点的下一个结点
            count++;//更新计数值
        }
    }
    free(C);//正式消灭C表
}

二叉树

前/中/后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//二叉树的结点定义（链式存储）
typedef struct BiTNode{
    int data;    //数据域
    struct BiTNode *lchild,*rchild;    //左、右孩子指针
}BiTNode,*BiTree;

//先序遍历二叉树
void PreOrder (BiTree root){
    if (root==NULL)
        return;
    visit(root);  //访问根节点
    PreOrder(root->lchild);
    PreOrder(root->rchild);
}

//中序遍历二叉树
void InOrder (BiTree root){
    if (root==NULL)
        return;
    InOrder(root->lchild);
    visit(root);  //访问根节点
    InOrder(root->rchild);
}

//后序遍历二叉树
void PostOrder (BiTree root){
    if (root==NULL)
        return;
    PostOrder(root->lchild);
    PostOrder(root->rchild);
    visit(root);  //访问根节点
}

层序遍历

在层序遍历中需要使用到队列，也就需要队列的操作

1
2
3
4
5
6
7
8
//初始化队列
void InitQueue(Queue &Q) 
//判断队列是否为空
bool IsEmpty(Queue Q) 
//新元素x入队
void EnQueue(Queue &Q, BiTNode * x) 
//队头元素出队，并使用x 返回队头元素 
void DeQueue(Queue &Q, BiTNode * &x)//&x 表示引用参数，函数内部对x的修改会影响外部的x
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//层序遍历
void LevelOrder(BiTree T){
    Queue Q;
    InitQueue(Q);    //初始化辅助队列
    BiTree p;
    EnQueue(Q, T);    //将根结点入队
	while(!IsEmpty(Q)){
    	DeQueue(Q, p);
    	visit(p);
    	if(p->lchild != NULL)
        	EnQueue(Q, p->lchild); //左孩子入队
    	if(p->rchild != NULL)
        	EnQueue(Q, p->rchild); //右孩子入队
	}
}

求树高

（方法一）先序遍历

1
2
3
4
5
6
7
8
9
10
/*求树的高度（方法一）*/
int height = 0;    //用全局变量记录树的高度
void PreOrder(BiTree T, int n) {
    if (T == NULL)
        return;
    if (n > height)
        height = n;    //更新树的高度
    PreOrder(T->lchild, n + 1);    //遍历左子树
    PreOrder(T->rchild, n + 1);    //遍历右子树
}

调用时用**PreOrder(T, 1**)

原理是每过一层则+1并和目前高度比较

（方法二）后序遍历

1
2
3
4
5
6
7
8
9
10
int PostOrder(BiTree T){
    if (T == NULL)
        return 0;
    int left = PostOrder(T->lchild);
    int right = PostOrder(T->rchild);
    if (left > right) 
        return left + 1;
    else 
        return right + 1;
}

以该图为例，g和h没有左右结点了，故直接返回0+1给e作为e的left和right，e再进行比较以大的深度+1作为自己的深度交给b，b也这么做并和c一起交给a

后序遍历以孩子出发从孩子开始数并返给根节点最长的版本

求树宽

此处先用先序遍历统计每一层的结点数，也就是使用先序遍历先根后孩子的特点来统计

1
2
3
4
5
6
7
8
9
int width[MAX];  //用于统计各层的结点总数

//先序遍历，同时统计各层结点总数
void PreOrder(BiTree T, int level) {
    if (T == NULL) return;
    width[level]++;  //累加该层结点总数
    PreOrder(T->lchild, level + 1);  //遍历左子树
    PreOrder(T->rchild, level + 1);  //遍历右子树
}

再找到宽度数组中最大的一项，将其作为树宽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void treeWidth(BiTree T) {
    // 初始化宽度数组
    for (int i = 0; i < MAX; i++)
        width[i] = 0;
    PreOrder(T, 0);  // 从第0层开始遍历
    
    // 找出最大宽度（某一层最多的节点数）
    int maxWidth = 0;
    for (int i = 0; i < MAX; i++) {
        if (width[i] > maxWidth)
            maxWidth = width[i];
    }
    printf("树的宽度是%d", maxWidth);
}

求树WPL

求树的WPL还是要使用树的先序遍历

使用了求树高和树宽的思想

先找到叶子节点（也就是左右孩子为空）并且将此处的带权路径长度加入WPL

如果不是叶子结点则向下找到其他叶子节点高度

1
2
3
4
5
6
7
void PreOrder (BiTree T, int level){
    if (T == NULL) return;
    if(T->lchild==NULL && T->rchild==NULL)
    WPL += level*T->weight; //累加叶结点带权路径长度
    PreOrder(T->lchild, level + 1); //遍历左子树
    PreOrder(T->rchild, level + 1); 
}

特殊树型判断

二叉排序树判定

中序遍历出来的序列是升序序列，所以二叉排序树序列中下一个结点必然大于前面所有的结点（也就是MAX{前面结点}）这里用temp表示

所以只要后面遍历到的小于temp，则直接判定失败

若不小于则继续向右子树遍历，直到为NULL退回

1
2
3
4
5
6
7
8
9
10
int temp=MIN_INT; //记录当前遍历到的最小值
bool isBST=true;    //是否为二叉排序树？

void InOrder(BiTree T){
    if (T == NULL) return;
    InOrder(T->lchild);
    if (T->data >= temp)    temp=T->data;
    else    isBST=false;
    InOrder(T->rchild);
}

平衡二叉树判定

此树判定和方法二找树深一样

通过后序遍历的特点：先访问孩子再进行操作，由最后的孩子也就是结点A的左右子树都退回来自己的高度之后，再进行左右子树高度判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool isBalance=true;    //二叉树是否平衡
int PostOrder(BiTree T){
    if (T == NULL)
    return 0;
    int left = PostOder(T->lchild);
    int right = PostOder(T->rchild);

    if (left-right>1)    isBalance=false;
    if (left-right<-1)    isBalance=false;

    //树的深度=Max(左子树深度，右子树深度)+1
    if (left>right)   return left+1;
    else    return right+1;
}

完全二叉树判定

这里先借用一下层序遍历的图

层序遍历，因为完全二叉树是按顺序排放，所以要看每一层的结点的逐个讨论、

四种情况分别在访问这个结点时讨论一次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// 特殊树形判定：完全二叉树？

bool isComplete = true;    // 是否为完全二叉树
bool flag = false;         // flag=true，表示层序遍历时出现过叶子或只有左孩子的分支节点

void visit(BiTNode * p) {
    if (p->lchild == NULL && p->rchild == NULL) {
        // 当前节点为叶子节点
        if (flag) {
            isComplete = false;  // 不是完全二叉树
        }
        flag = true;
    } else if (p->lchild != NULL && p->rchild == NULL) {
        // 只有左孩子，没有右孩子
        if (flag) {
            isComplete = false;  // 不是完全二叉树
        }
        flag = true;
    } else if (p->lchild == NULL && p->rchild != NULL) {
        // 只有右孩子，没有左孩子 - 肯定不是完全二叉树
        isComplete = false;
    } else {
        // 有两个孩子
        if (flag) {
            isComplete = false;  // 不是完全二叉树
        }
    }
}

图

图的数据结构定义

邻接矩阵

这是邻接矩阵的数据结构

这是邻接矩阵的初始化操作

邻接表

这是邻接表的数据结构，在图ALGraph中存储一个顶点表数组和顶点数和边数

在顶点表中存储这个结点的数据和第一个依附该点的边

边表则是指出这条边指向的点和下一条边的指针以及该边权值

这个表依旧要执行初始化操作

先将顶点表数组中的第一条边全部置为NULL

再将其顶点数和边数先更新

用封装好的AddEdge(图,出点，入点，权值)函数添加边

AddEdge函数是这么写的

首先先创建一个边结点，将其的权值和指向的结点j配置好

再将他连接到i结点第一条边之前，让这条新边指向老的第一条边（类似头插法将靠后的插在头边）

最后让i的点表连接到这条边作为first

最后可以看到他的逻辑结构长这样

图的遍历

深度优先遍历

里昂学长的pdf

1
2
3
4
5
6
7
8
9
10
//邻接矩阵实现深度优先搜索
void DFS(MGraph G,int i){
    visit(i);
    //访问初始顶点
    visited[i]=true;//对做已访问标记
    for(int j=0;j<G.G.numVertices;j++)
    if(visited[j]==false&&G.edge[i][j]==1){
    DFS(G,j);//为的尚未访问的邻接点，递归访问
    }
}

首先先把第一个访问的结点打上true，对第一结点比如A，找他向别人发射过的边，直到j<G.vexnum（穷尽了所有点）

当遇到没有遍历到过的且存在的邻接点时，将其投入DPS

然后一直DPS递归下去，直到再没有邻接的点，逐层返回没有访问完邻接点的结点中继续访问他们邻接点

1
2
3
4
5
6
7
8
9
10
11
12
13
//邻接表实现深度优先搜索
void DFS(ALGraph G,int i){
    visit(i);
    //访问初始顶点
    visited[i]=true;//对做已访问标记
    for(EdgeNode* p=G.VertexList[i].first ; p!=NULL; p=p->next){
    //检测的所有邻接点
    int j=p->index;
    if(visited[j]==false){
    DFS(G,j);//为的尚未访问的邻接点，递归访问
    }
    }
}

前面步骤一样，依旧从i点开始遍历。先找到i点的第一个边，将其位置存放到p中

j就是此时p指向的点，若此点没有被访问过则开始深度遍历

直到遍历到最后一个能遍历到的点，就往上返回，继续访问之前没有访问完其他边的结点。

广度优先遍历

里昂学长的pdf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//邻接矩阵实现广度优先搜索
void BFS(MGraph G, int v){
    visit(v); //访问初始顶点
    visited[v]=true; //对v做已访问标记
    EnQueue(Q, v); //顶点v入队
    while(!isEmpty(Q)){
        DeQueue(Q, v); //从队首取出顶点v
        for(int w=0; w<G.numVertices; w++){
            //检测v的所有邻接顶点
            if(visited[w]==false && G.edge[v][w]==1){
                visit(w); //w为v的尚未访问的邻接点，访问w
                visited[w]=true; //标记w为已访问
                EnQueue(Q, w); //顶点w入队
            }
        }
    }
}

广度优先遍历类似于图的层序遍历

从v出发，先将v存入队列中

当队列不为空时就出队一个结点，并且从第0个结点开始遍历，寻找v指向的且没有被访问过的结点，找到一个入队一个直到找不到为止

然后从i结点找到的第一个结点开始继续重复这个步骤，直到所有结点都找完使队列为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//邻接表实现广度优先搜索
void BFS(ALGraph G, int v){
    visit(v); //访问初始顶点
    visited[v]=true; //对v做已访问标记
    EnQueue(Q, v); //顶点v入队
    while(!isEmpty(Q)){
        DeQueue(Q, v); //从队首取出顶点v
        for(EdgeNode *p=G.VertexList[v].first; p!=NULL; p=p->next){
            //检测v的所有邻接顶点
            int w = p->index;
            if(visited[w]==false){
                visit(w); //w为v的尚未访问的邻接点，访问w
                visited[w]=true; //标记w为已访问
                EnQueue(Q, w); //顶点w入队
            }
        }
    }
}

套路和上面一样，入队之后先找到第一个边指向的结点看是否被访问过，若没有则全部入队直到v结点没有邻接的点为止。

然后又从v第一条边邻接点继续广度优先遍历

拓扑排序

先按一下思路分析

拓扑排序的步骤:

  1. 选择入度为0的顶点并输出
  2. 从图中删除该顶点与所有以它为弧的边
  3. 重复步骤1、2，直到不存在入度为0的顶点
拓扑序列 条件
存在且唯一 每次选择结点都只有一个结点可选
存在不唯一 选择结点时不止一个结点可选
不存在 图中有环，环中顶点未被访问

先拿王道的流程图说一下思想

首先我们需要循环找到入度为0的点并且全部入队。

此处如果队列里元素个数超过1，

  • 入度为0的点肯定超过2个也就是拓扑排序不唯一。
  • 若是有多个连通分量，一个连通分量多个入度为0，另一个连通分量是有环图，则很明显不存在拓扑排序

然后当我们出队时，我们将计数器+1，来记录已经出队的数

出队之后将所有出队的点指向的点，把他们的入度-1，然后继续寻找入度为0的点循环这个过程

当队空之后我们根据count数进行判断

  • 如果count等于顶点数，那么说明从顶点到最后一个点只有一条路径。没错，拓扑排序唯一
  • 若count数不等于也就是小于顶点数，说明存在环路，始终有点入度不为0互相堵着
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//邻接表实现
int uniquely1(MGraph G){
    int inDegree[MAXV] = {0}; // 存储每个顶点的入度
	int queue[MAXV];    // 用于存储入度为0的顶点
	int front = 0, rear = 0;    // 队列的前后指针
	int count = 0;    // 拓扑序列中的顶点计数

// 计算每个顶点的入度
	for (int i = 0; i < G.vexnum; i++)
	{
    	ArcNode *p = G.AdjList[i].firstarc;//从i的第一条边开始找
    	while (p != NULL)
    	{
        	inDegree[p->adjvex]++;
        	p = p->nextarc;
    	}
	}

// 将所有入度为0的顶点入队
	for (int i = 0; i < G.vexnum; i++)
	{
    	if (inDegree[i] == 0)
        	queue[rear++] = i;
	}

// 进行拓扑排序
	while (front < rear)//非空队列
	{
    	// 如果队列中有多个顶点，说明图的拓扑序列不唯一
    	if (rear - front > 1)
        return 0;
    	int v = queue[front++]; // 取出队首顶点
    	count++;
    	// 更新该顶点的所有邻接顶点的入度
    	ArcNode *p = G.AdjList[v].firstarc;
    	while (p != NULL)
    	{
        	inDegree[p->adjvex]--;
        	// 如果入度变为0，则加入队列
        	if (inDegree[p->adjvex] == 0)
            	queue[rear++] = p->adjvex;
        	p = p->nextarc;
    	}
	}

	if (count == G.vexnum)
    	return 1; // 当前拓扑序列包含所有顶点，则图的拓扑序列唯一
	else
    	return 0; // 当前拓扑序列不包含所有顶点，则图的拓扑序列不存在
}
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
//邻接矩阵实现
int uniquely1(MGraph G)
{
    int inDegree[MAXV] = {0}; // 存储每个顶点的入度
    int queue[MAXV]; // 用于存储入度为0的顶点
    int front = 0, rear = 0; // 队列的前后指针
    int count = 0; // 拓扑序列中的顶点计数
    
    // 计算每个顶点的入度
    for (int i = 0; i < G.numVertices; i++)
        for (int j = 0; j < G.numVertices; j++)
            if (G.Edge[i][j] != 0)
                inDegree[j]++;
    
    // 将所有入度为0的顶点入队
    for (int i = 0; i < G.numVertices; i++)
        if (inDegree[i] == 0)
            queue[rear++] = i;

    
    // 进行拓扑排序
    while (front < rear)
    {
        // 如果队列中有多个顶点，说明图的拓扑序列不唯一
        if (rear - front > 1)
            return 0;
        int v = queue[front++]; // 取出队首顶点
        count++;
        // 更新该顶点的所有邻接顶点的入度
        for (int i = 0; i < G.numVertices; i++)
            if (G.Edge[v][i] != 0)
            {
                inDegree[i]--; // 如果入度变为0，则加入队列
                if (inDegree[i] == 0)
                    queue[rear++] = i;
            }
    }
    
    if (count == G.numVertices)
        return 1; // 当前拓扑序列包含所有顶点，则图的拓扑序列唯一
    else
        return 0; // 当前拓扑序列不包含所有顶点，则图的拓扑序列不存在
}