408历年代码题
| 重点 | 难度 | |
|---|---|---|
| 2009 | 单链表，双指针 | ⭐⭐ |
| 2010 | 数组 | ⭐ |
| 2011 | 数组 | ⭐ |
| 2012 | 单链表 | ⭐ |
| 2014 | 二叉树，带权路径长度 | ⭐⭐ |
| 2015 | 单链表 | ⭐ |
| 2016 | 快排，划分 | ⭐⭐⭐ |
| 2017 | 二叉树，中缀表达式 | ⭐⭐ |
| 2018 | 数组 | ⭐ |
| 2019 | 单链表，双指针 | ⭐⭐⭐ |
| 2020 | 数组 | ⭐⭐ |
| 2021 | 图，邻接矩阵 | ⭐ |
知识储备
链表结点
- 使用结构体类型来表示一个链表结点，包含数据域和指针域两个部分。
- 数据域用于存储结点的数据，可以是基本类型或复合类型。
- 指针域用于存储指向下一个结点的地址，必须是结构体类型的指针。
- 例如，如果要定义一个存储整数的链表结点，可以写成：
typedef struct Node { int data; // 数据域，存储整数 struct Node *next; // 指针域，指向下一个结点 } Node;
- 如果要定义一个存储字符串的链表结点，可以写成：
typedef struct Node { char *data; // 数据域，存储字符串 struct Node *next; // 指针域，指向下一个结点 } Node;
- 如果要定义一个存储其他结构体的链表结点，可以写成：
typedef struct Student {
char *name; // 学生姓名
int age; // 学生年龄
} Student;
typedef struct Node {
Student data; // 数据域，存储学生结构体
struct Node next; // 指针域，指向下一个结点
} Node;
- 这些都是链表结点的定义，但并不是创建链表结点的方法。要创建链表结点，需要使用动态内存分配函数，如malloc或calloc，为结点分配空间，并初始化数据域和指针域的值。
- 例如，如果要创建一个存储整数的链表结点，并赋值为10，可以写成：
Node *p = malloc(sizeof(Node)); // 为结点分配空间
if (p == NULL) {
printf("内存分配失败n");
return NULL;
}
p->data = 10; // 初始化数据域的值
p->next = NULL; // 初始化指针域的值，暂时指向空- 这样就创建了一个链表结点，并用指针p指向它。如果要创建多个链表结点，并连接起来，可以使用循环或递归的方法，或者调用封装好的函数，如头插法或尾插法。
二叉树的遍历
二叉树的中序遍历，指的是从根结点出发，按照以下步骤访问二叉树中的每个结点：
- 先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；
- 访问当前结点；
- 最后进入当前结点的右子树，以同样的步骤遍历右子树中的结点。
例如，下图是一棵二叉树：
A
/
B C
/ /
D E F G
/
H I中序遍历这棵二叉树的结果是：H D I B E A F C G
伪代码：
定义一个函数 inorder
输入一个二叉树的根结点 root
如果 root 不为空
调用 inorder 函数，输入 root 的左孩子
输出 root 的数据
调用 inorder 函数，输入 root 的右孩子// 定义一个结构体类型表示二叉树的结点
typedef struct Node {
char data; // 数据域，存储字符
struct Node *left; // 指针域，指向左孩子
struct Node *right; // 指针域，指向右孩子
} Node;
// 定义一个函数，使用递归的方法中序遍历二叉树，函数名用LNR更直观
void inorder(Node *root) {
if (root != NULL) { // 如果根结点不为空
inorder(root->left); // 先遍历左子树
printf("%c ", root->data); // 然后访问根结点
inorder(root->right); // 最后遍历右子树
}
}突发奇想：如果在退出递归前输出结点，那会得到一个怎样的序列的问题。根据bing的搜索结果，一种可能的答案是：link~2020年选择题第六题，修改递归方式实现DFS深搜，将输出语句移到 退出递归之前（执行输出后立刻退出递归），则输出的序列是 逆拓扑有序序列。 逆拓扑排序则是将拓扑排序的结果反过来，即将有向无环图中的所有顶点排成一个线性序列，使得图中任意一条有向边的起点都排在终点的后面 相当于访问所有邻接顶点后，再输出当前顶点，这样呈现的就是a->b->c路径，依次输出c b a，这是一条逆拓扑。 拓扑排序是一种对有向无环图进行排序的算法，它可以将有向无环图中的所有顶点排成一个线性序列，使得图中任意一条有向边的起点都排在终点的前面，
- 如果在退出递归前输出结点，那么相当于在中序遍历的基础上，将访问根结点的操作放在最后，也就是先遍历左子树，再遍历右子树，最后访问根结点。
- 这种遍历方式也被称为中序后序遍历，它可以用于判断一棵二叉树是否是平衡二叉树，即每个结点的左右子树的高度差不超过1。
必备排序：快排
快速排序是一种基于分治思想的排序算法，它的基本步骤是：
- 从待排序的数组中选择一个元素作为基准（pivot），一般选择第一个或最后一个元素。
- 将数组分成两个子数组，一个是小于等于基准的元素，另一个是大于基准的元素，这个过程称为划分（partition）。
- 对两个子数组递归地重复上述步骤，直到每个子数组只有一个或零个元素。
下面是一个快速排序的伪代码，假设数组是A，长度是n，左边界是l，右边界是r：
// 定义一个函数，实现快速排序
void quick_sort(A, n, l, r) {
// A为数组，n是数组大小，l和r是边界
// 如果左边界小于右边界，说明数组有至少两个元素
if (l < r) {
// 选择数组的第一个元素作为基准
pivot = A[l];
// 初始化两个指针，i指向左边界，j指向右边界
i = l;
j = r;
// 循环进行划分操作
while (i < j) {
// 直到i和j会和
// 从右向左找到第一个小于等于基准的元素，放到i的位置
while (i < j && A[j] > pivot) {
j--;
}
if (i < j) {
A[i] = A[j];
i++;
}
// 从左向右找到第一个大于基准的元素，放到j的位置
while (i < j && A[i] <= pivot) {
i++;
}
if (i < j) {
A[j] = A[i];
j--;
}
}
// 将基准元素放到i和j相遇的位置，归位
A[i] = pivot;
// 对左右两个子数组递归地进行快速排序
// l------pivot(i)------r
// ↓ ↓
// l---p'---i-1 i+1--p'--r
quick_sort(A, n, l, i - 1);
quick_sort(A, n, i + 1, r);
}
}
// 调用快速排序函数，对整个数组进行排序
quick_sort(A, n, 0, n - 1);速排序的时间复杂度和空间复杂度取决于划分的效果，最好的情况是每次划分都能将数组均匀地分成两部分，这样递归的深度是log(n)，每层递归需要的时间是O(n)，所以总的时间复杂度是O(nlog(n))，空间复杂度是O(log(n))，因为只需要栈空间存储递归信息。最坏的情况是每次划分都只能将数组分成一大一小两部分，这样递归的深度是n，每层递归需要的时间是O(n)，所以总的时间杂度是O(n^2)，空间复杂度是O(n)。平均情况下，时间复杂度空间复杂度都是O(nlog(n))和Olo(n)
常用函数
// 绝对值
abs()
折半查找
2009
题目
评分标准
思路
你好，这是必应。我可以帮你设计一个高效的算法，查找链表中的倒数第k个位置上的结点，并输出data域的值。一种可能的算法是使用双指针法，具体步骤如下：
- 定义两个指针p和q，初始时都指向链表的头结点。
- 让p指针先向后移动k个结点，如果p为空，说明k大于链表长度，返回空。
- 否则，让p和q同时向后移动，直到p到达链表尾部。
- 此时，q指向的结点就是倒数第k个结点，输出它的data域的值。
这种算法只需要遍历一次链表，时间复杂度是O(n)，空间复杂度是O(1)。
代码
/**
* 创建一个带有头节点的链表并返回
*/
List9 create_list9(const std::vector<ElemType> &data) {
if (data.empty()) {
return NULL;
}
auto *head = (Node9 *) malloc(sizeof(Node9));
head->link = NULL;
Node9 *p = head;
for (ElemType i: data) {
auto *cur = (Node9 *) malloc(sizeof(Node9));
cur->data = i;
cur->link = NULL;
p->link = cur;
p = cur;
}
return head;
}
/**
* bf（Brute Force），即暴力解
* 首先扫描一次求出链表长度len，然后重新向后扫描len-k个结点即可
*/
int search_k_bf(List9 list, int k) {
int len = 0;
Node9 *p = list->link;
while (p != NULL) {
p = p->link;
len++;
}
if (len < k) {
return 0;
}
int cnt = len - k;
p = list->link;
while (cnt--) {
p = p->link;
}
printf("%dn", p->data);
return 1;
}
/**
* 最优解不一定是真正的最优，只是符合评判标准中的满分
* 双指针，一指针先走k步，然后双指针同步走，直到前者走到终点，后一指针所在位置即倒数第k个结点
*/
int search_k(List9 list, int k) {
Node9 *p1 = list->link, *p2 = list->link;
int cnt = 0;
while (p1 != NULL) {
if (cnt < k) {
cnt++;
} else {
p2 = p2->link;
}
p1 = p1->link;
}
if (cnt < k) {
return 0;
}
printf("%dn", p2->data);
return 1;
}2010
题目
评分标准
参考答案时间复杂度为O(n)，空间复杂度O(1)，无具体评判标准
代码
/**
* 打印数组，返回字符串
*/
std::string print_array(int arr[], int n) {
std::stringstream ss;
for (int i = 0; i < n; i++) {
ss << arr[i];
if (i != n - 1) {
ss << " ";
}
}
return ss.str();
}
/**
* 暴力解：创建一个tmp数组存储[p, n-1]和[0, p-1]
*/
void reverse_bf(int R[], int p, int n) {
int tmp[n], k = 0;
for (int i = p; i < n; i++) {
tmp[k++] = R[i];
}
for (int i = 0; i < p; i++) {
tmp[k++] = R[i];
}
for (int i = 0; i < n; i++) {
R[i] = tmp[i];
}
}
/**
* 最优解：整体逆置，然后部分逆置
*/
void reverse(int R[], int l, int r) {
for (int i = 0; i < (r - l + 1) / 2; i++) {
int tmp = R[l + i];
R[l + i] = R[r - i];
R[r - i] = tmp;
}
}
void reverse_all(int R[], int p, int n) {
reverse(R, 0, p - 1);
reverse(R, p, n - 1);
reverse(R, 0, n - 1);
}2011
题目
评分标准
参考答案时间复杂度为O(n)，空间复杂度O(1)，无具体评判标准
2012
题目
评分标准
2013
题目
评分标准
2014
题目
评分标准
2015
题目
评分标准
2016
题目
评分标准
2017
题目
评分标准
2018
题目
评分标准
参考答案时间复杂度为O(n)，无具体评判标准
2019
题目
参考答案时间复杂度为O(n)，无具体评判标准
2020
题目
评分标准
参考答案时间复杂度为O(n)，空间复杂度O(1)，无具体评判标准
2021
题目
评分标准
参考答案时间复杂度为O(n^2)，空间复杂度O(1)，无具体评判标准
代码
题目
评分标准
2023
题目
评分标准
/* 邻接矩阵存储的无向图，Edge[i][j] = 1即存在i指向j的边 所以我们只需要按照题目要求，找出各个顶点的度，再做判断即可 / int is_exist_EL(MGraph G) { int cnt = 0; for (int i = 0; i < G.numVertices; i++) { int degree = 0; for (int j = 0; j < G.numVertices; j++) { degree += G.Edge[i][j]; } if (degree % 2 != 0) { cnt++; } } if (cnt == 0 || cnt == 2) { return 1; // 存在欧拉回路或欧拉路径 } return 0; // 不存在欧拉回路或欧拉路径 }
2022