当前位置：首页 > ops >正文

数据结构与算法个人学习代码笔记包含leetcode，海贼oj，蓝桥杯，ACM

ops 2025/9/3 6:31:17

（一）基础算法模块

1. 第 0 章：从复杂度开始认识算法

0.1 时间复杂度计算示例（calc_time_complexity.c）

#include <stdio.h>// 函数功能：计算两个数组对应元素乘积之和（用于演示O(n)时间复杂度）
// 输入：arr1-数组1，arr2-数组2，n-数组长度
// 输出：乘积之和
int calc_product_sum(int arr1[], int arr2[], int n) {int sum = 0;// 循环执行n次，每次操作均为常数时间O(1)，整体时间复杂度O(n)for (int i = 0; i < n; i++) {sum += arr1[i] * arr2[i];  // 常数操作：乘法+加法+赋值}return sum;
}// 函数功能：计算矩阵乘法（用于演示O(n³)时间复杂度）
// 输入：mat1-矩阵1，mat2-矩阵2，result-结果矩阵，n-矩阵维度
void matrix_multiply(int mat1[][100], int mat2[][100], int result[][100], int n) {// 三层嵌套循环，每层执行n次，整体时间复杂度O(n³)for (int i = 0; i < n; i++) {          // 控制结果矩阵行for (int j = 0; j < n; j++) {      // 控制结果矩阵列result[i][j] = 0;              // 初始化结果元素for (int k = 0; k < n; k++) {  // 计算对应元素乘积和result[i][j] += mat1[i][k] * mat2[k][j];}}}
}int main() {// 测试O(n)复杂度函数int arr1[5] = {1,2,3,4,5}, arr2[5] = {2,3,4,5,6};printf("乘积之和：%d\n", calc_product_sum(arr1, arr2, 5));// 测试O(n³)复杂度函数int mat1[2][100] = {{1,2},{3,4}}, mat2[2][100] = {{5,6},{7,8}}, result[2][100];matrix_multiply(mat1, mat2, result, 2);printf("矩阵乘法结果：\n");for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {printf("%d ", result[i][j]);}printf("\n");}return 0;
}

解读：该文件通过两个经典案例演示时间复杂度计算：

数组乘积和：单层循环，时间复杂度 O (n)，空间复杂度 O (1)（仅用常量额外空间）；
矩阵乘法：三层嵌套循环，时间复杂度 O (n³)，空间复杂度 O (n²)（存储结果矩阵），帮助理解 “循环嵌套层数” 与时间复杂度的关联。

2. 第 1 章：递归程序设计技巧

1.1 斐波那契数列递归实现（fib_recursion.c）

#include <stdio.h>// 函数功能：递归计算第n个斐波那契数（斐波那契数列：F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)）
// 输入：n-斐波那契数的序号（n≥0）
// 输出：第n个斐波那契数
int fibonacci(int n) {// 递归终止条件：base case（避免无限递归）if (n == 0) return 0;if (n == 1) return 1;// 递归递推：将问题分解为更小的子问题（F(n-1)和F(n-2)）return fibonacci(n - 1) + fibonacci(n - 2);
}int main() {int n;printf("请输入斐波那契数的序号：");scanf("%d", &n);// 输入合法性检查if (n < 0) {printf("序号需为非负整数！\n");return 1;}printf("第%d个斐波那契数：%d\n", n, fibonacci(n));return 0;
}

解读：递归的核心是 “分治 + 终止条件”，该代码通过斐波那契数列演示递归思想，但存在重复计算问题（如计算 F (5) 时需重复计算 F (3)、F (2) 等），时间复杂度 O (2ⁿ)，后续可通过 “记忆化搜索” 或 “动态规划” 优化为 O (n)。

1.2 汉诺塔问题递归实现（hanoi_recursion.c）

#include <stdio.h>// 函数功能：递归实现汉诺塔移动（将n个盘子从from柱移到to柱，借助aux柱）
// 输入：n-盘子数量，from-起始柱子，aux-辅助柱子，to-目标柱子
void hanoi(int n, char from, char aux, char to) {// 递归终止条件：只有1个盘子时，直接从from移到toif (n == 1) {printf("将盘子1从%c柱移到%c柱\n", from, to);return;}// 步骤1：将n-1个盘子从from移到aux，借助tohanoi(n - 1, from, to, aux);// 步骤2：将第n个盘子（最大盘）从from移到toprintf("将盘子%d从%c柱移到%c柱\n", n, from, to);// 步骤3：将n-1个盘子从aux移到to，借助fromhanoi(n - 1, aux, from, to);
}int main() {int n;printf("请输入汉诺塔盘子数量：");scanf("%d", &n);if (n < 1) {printf("盘子数量需为正整数！\n");return 1;}printf("汉诺塔移动步骤：\n");hanoi(n, 'A', 'B', 'C');  // 约定柱子为A（起始）、B（辅助）、C（目标）return 0;
}

解读：汉诺塔是递归分治思想的经典案例，移动 n 个盘子的步骤可分解为 “移动 n-1 个盘子→移动最大盘→移动 n-1 个盘子”，总移动次数为 2ⁿ-1，时间复杂度 O (2ⁿ)，该代码清晰体现了递归 “大事化小” 的核心逻辑。

3. 第 2 章：顺序表和链表

2.1 顺序表实现（seq_list.c）

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100  // 顺序表最大容量
// 顺序表结构体：存储数据+当前长度
typedef struct {int data[MAX_SIZE];  // 数组存储数据（连续内存）int length;          // 当前元素个数（length ≤ MAX_SIZE）
} SeqList;// 函数功能：初始化顺序表（空表，length=0）
void init_seq_list(SeqList *L) {L->length = 0;
}// 函数功能：在顺序表第pos位置插入元素val（pos从1开始）
// 输入：L-顺序表指针，pos-插入位置，val-插入元素
// 输出：1-插入成功，0-插入失败（位置非法或表满）
int insert_seq_list(SeqList *L, int pos, int val) {// 合法性检查：pos范围（1~L->length+1）、表是否满if (pos < 1 || pos > L->length + 1 || L->length >= MAX_SIZE) {return 0;}// 从后向前移动元素，腾出pos位置（时间复杂度O(n)）for (int i = L->length; i >= pos; i--) {L->data[i] = L->data[i - 1];}// 插入元素，更新长度L->data[pos - 1] = val;  // 数组索引从0开始，pos需减1L->length++;return 1;
}// 函数功能：删除顺序表第pos位置的元素，并用val存储删除的元素
// 输入：L-顺序表指针，pos-删除位置，val-存储删除元素的指针
// 输出：1-删除成功，0-删除失败（位置非法）
int delete_seq_list(SeqList *L, int pos, int *val) {if (pos < 1 || pos > L->length) {return 0;}// 存储删除的元素*val = L->data[pos - 1];// 从前向后移动元素，覆盖删除位置（时间复杂度O(n)）for (int i = pos; i < L->length; i++) {L->data[i - 1] = L->data[i];}// 更新长度L->length--;return 1;
}// 函数功能：打印顺序表所有元素
void print_seq_list(SeqList *L) {if (L->length == 0) {printf("顺序表为空！\n");return;}printf("顺序表元素：");for (int i = 0; i < L->length; i++) {printf("%d ", L->data[i]);}printf("\n");
}int main() {SeqList L;init_seq_list(&L);// 插入测试insert_seq_list(&L, 1, 10);insert_seq_list(&L, 2, 20);insert_seq_list(&L, 2, 15);print_seq_list(&L);  // 预期：10 15 20// 删除测试int del_val;delete_seq_list(&L, 2, &del_val);printf("删除的元素：%d\n", del_val);  // 预期：15print_seq_list(&L);  // 预期：10 20return 0;
}

解读：顺序表基于数组实现，特点是随机访问（O (1)）、插入删除慢（O (n)），适合频繁查询、少量插入删除的场景。代码完整实现了顺序表的初始化、插入、删除、打印功能，重点体现了插入删除时 “元素移动” 的核心操作。

2.2 单链表实现（single_linked_list.c）

#include <stdio.h>
#include <stdlib.h>// 链表节点结构体：存储数据+下一个节点指针
typedef struct Node {int data;          // 节点数据struct Node *next; // 指向后继节点的指针
} Node, *LinkedList;// 函数功能：初始化单链表（带头节点，空表）
// 输出：头节点指针（头节点不存储实际数据，仅用于简化操作）
LinkedList init_linked_list() {LinkedList head = (Node *)malloc(sizeof(Node));  // 分配头节点内存head->next = NULL;  // 空表，头节点后继为NULLreturn head;
}// 函数功能：在链表头部插入元素val（头插法，时间复杂度O(1)）
void insert_head(LinkedList head, int val) {// 创建新节点Node *new_node = (Node *)malloc(sizeof(Node));new_node->data = val;// 新节点指向原头节点的后继new_node->next = head->next;// 头节点指向新节点head->next = new_node;
}// 函数功能：在链表尾部插入元素val（尾插法，时间复杂度O(n)）
void insert_tail(LinkedList head, int val) {Node *new_node = (Node *)malloc(sizeof(Node));new_node->data = val;new_node->next = NULL;  // 尾节点后继为NULL// 找到链表尾部节点（从头节点开始遍历）Node *p = head;while (p->next != NULL) {p = p->next;}// 尾部节点指向新节点p->next = new_node;
}// 函数功能：删除链表中第一个值为val的节点
// 输出：1-删除成功，0-删除失败（未找到val）
int delete_node(LinkedList head, int val) {Node *p = head;  // p指向当前节点的前驱// 遍历链表，查找值为val的节点while (p->next != NULL && p->next->data != val) {p = p->next;}// 未找到valif (p->next == NULL) {return 0;}// 找到val，删除p->next节点Node *del_node = p->next;  // 存储待删除节点p->next = del_node->next;  // 前驱节点指向后继节点free(del_node);            // 释放待删除节点内存（避免内存泄漏）return 1;
}// 函数功能：打印链表所有元素
void print_linked_list(LinkedList head) {Node *p = head->next;  // 从第一个有效节点开始遍历if (p == NULL) {printf("链表为空！\n");return;}printf("链表元素：");while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n");
}// 函数功能：销毁链表（释放所有节点内存）
void destroy_linked_list(LinkedList head) {Node *p = head;while (p != NULL) {Node *temp = p;  // 存储当前节点p = p->next;     // 移动到下一个节点free(temp);      // 释放当前节点内存}
}int main() {LinkedList head = init_linked_list();// 尾插法插入元素insert_tail(head, 10);insert_tail(head, 20);insert_tail(head, 30);print_linked_list(head);  // 预期：10 20 30// 头插法插入元素insert_head(head, 5);print_linked_list(head);  // 预期：5 10 20 30// 删除测试delete_node(head, 20);print_linked_list(head);  // 预期：5 10 30// 销毁链表destroy_linked_list(head);return 0;
}

解读：单链表基于节点实现，节点通过指针链接，特点是插入删除快（O (1)，已知前驱节点时）、随机访问慢（O (n)），适合频繁插入删除、少量查询的场景。代码实现了头插法、尾插法、节点删除、链表销毁等核心功能，重点关注 “指针操作” 和 “内存释放”（避免内存泄漏）。

二、查找算法相关代码解析

1. Leetcode-349（两个数组的交集）

c++

#include <vector>
#include <unordered_set>
using namespace std;class Solution {
public:// 函数功能：求两个数组的交集（结果中每个元素唯一）vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> h;  // 用于存储nums1中的元素，利用哈希表实现O(1)级别的查找vector<int> ret;       // 存储交集结果// 将nums1中的所有元素插入哈希表，自动去重for (auto x : nums1) h.insert(x);// 遍历nums2，查找哈希表中是否存在该元素for (auto x : nums2) {// 若元素存在于哈希表中if (h.find(x) != h.end()) {ret.push_back(x);  // 加入结果集h.erase(h.find(x));  // 从哈希表中删除该元素，避免结果集中出现重复}}return ret;}
};

解读：利用哈希集合的特性（元素唯一、查找高效），先存储第一个数组的元素，再遍历第二个数组查找交集元素，时间复杂度为 O (n+m)（n、m 为两数组长度）。

2. Leetcode-01-1（两数之和，哈希表实现）

c++

#include <vector>
#include <unordered_map>
using namespace std;class Solution {
public:// 函数功能：在数组中找到两个数，使其和为target，返回这两个数的索引vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> h;  // 存储数组元素值到索引的映射vector<int> ret(2);         // 存储结果索引// 遍历数组for (int i = 0, I = nums.size(); i < I; i++) {// 计算目标差值（target - 当前元素）int complement = target - nums[i];// 若差值存在于哈希表中，说明找到符合条件的两个数if (h.find(complement) != h.end()) {ret[0] = h[complement];  // 差值对应的索引ret[1] = i;              // 当前元素的索引break;}// 若未找到，将当前元素及其索引存入哈希表h[nums[i]] = i;}return ret;}
};

解读：通过哈希表存储已遍历元素的 “值 - 索引” 对，每遍历一个元素时检查目标差值是否存在，时间复杂度 O (n)，空间复杂度 O (n)。

3. Leetcode-03（无重复字符的最长子串）

c++

#include <string>
#include <vector>
using namespace std;class Solution {
public:// 辅助函数：判断长度为l的无重复字符子串是否存在bool check(string &s, int l) {int cnt[256] = {0};  // 记录每个字符的出现次数（ASCII字符集）int k = 0;           // 记录当前窗口中不同字符的数量for (int i = 0; s[i]; i++) {// 新增当前字符，若为首次出现则k加1cnt[s[i]] += 1;if (cnt[s[i]] == 1) k += 1;// 当窗口长度超过l时，移除窗口最左侧字符if (i >= l) {cnt[s[i - l]] -= 1;// 若移除后该字符次数为0，则k减1if (cnt[s[i - l]] == 0) k -= 1;}// 若当前窗口中不同字符数量等于窗口长度l，说明存在无重复子串if (l == k) return true;}return false;}// 函数功能：求字符串中无重复字符的最长子串长度int lengthOfLongestSubstring(string s) {int head = 0, tail = s.size(), mid;  // 二分查找的左右边界及中间值// 二分查找最长长度（满足条件的最大l）while (head < tail) {mid = (head + tail + 1) / 2;  // 向上取整，避免死循环if (check(s, mid)) {head = mid;  // 若存在长度为mid的子串，尝试更长的长度} else {tail = mid - 1;  // 若不存在，尝试更短的长度}}return head;  // 最终head为最长长度}
};

解读：结合滑动窗口与二分查找，通过二分法确定可能的最长子串长度，再用滑动窗口验证是否存在该长度的无重复子串，时间复杂度 O (n log n)（n 为字符串长度）。

4. Leetcode-35（搜索插入位置）

c++

#include <vector>
using namespace std;class Solution {
public:// 函数功能：在有序数组中查找target，若存在返回索引；否则返回插入位置int searchInsert(vector<int>& nums, int target) {int head = 0, tail = nums.size(), mid;  // 二分查找边界（左闭右开）while (head < tail) {mid = (head + tail) / 2;  // 计算中间索引if (nums[mid] < target) {// 中间值小于目标值，目标在右侧head = mid + 1;} else {// 中间值大于等于目标值，目标在左侧（包括当前位置）tail = mid;}}return head;  // 最终head即为目标索引或插入位置}
};

解读：利用二分查找在有序数组中定位目标值，若未找到则返回其应插入的位置，时间复杂度 O (log n)。

5. Leetcode-217（存在重复元素）

c++

#include <vector>
#include <unordered_set>
using namespace std;class Solution {
public:// 函数功能：判断数组中是否存在重复元素bool containsDuplicate(vector<int>& nums) {unordered_set<int> h;  // 哈希集合用于存储已出现的元素for (auto x : nums) {// 若元素已存在于集合中，返回trueif (h.find(x) != h.end()) return true;// 否则插入集合h.insert(x);}// 遍历完未发现重复，返回falsereturn false;}
};

解读：通过哈希集合记录已遍历元素，每次检查新元素是否已存在，时间复杂度 O (n)，空间复杂度 O (n)。

6. Leetcode-01-2（两数之和，排序 + 二分查找实现）

c++

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:// 辅助函数：在有序索引数组中二分查找目标值int binary_search(vector<int> &nums, vector<int> &ind, int b, int x) {int head = b, tail = nums.size() - 1, mid;  // 查找范围：[b, tail]while (head <= tail) {mid = (head + tail) / 2;if (nums[ind[mid]] == x) {return mid;  // 找到目标值，返回索引} else if (nums[ind[mid]] < x) {head = mid + 1;  // 目标在右侧} else {tail = mid - 1;  // 目标在左侧}}return -1;  // 未找到}// 函数功能：求两数之和的索引（排序+二分查找实现）vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();vector<int> ind(n, 0);  // 存储原数组索引的数组// 初始化索引数组for (int i = 0; i < n; i++) ind[i] = i;// 按原数组值对索引数组排序（保持原索引与值的关联）sort(ind.begin(), ind.end(), [&](int i, int j) -> bool {return nums[i] < nums[j];});vector<int> ret(2);  // 存储结果索引// 遍历每个元素，通过二分查找寻找目标差值for (int i = 0; i < n; i++) {int j = binary_search(nums, ind, i + 1, target - nums[ind[i]]);if (j != -1) {ret[0] = ind[j];ret[1] = ind[i];break;}}// 保证结果索引按升序排列if (ret[0] > ret[1]) swap(ret[0], ret[1]);return ret;}
};

解读：通过排序索引数组（避免改变原数组索引），再对每个元素用二分查找寻找目标差值，时间复杂度 O (n log n)，空间复杂度 O (n)。

7. Leetcode-04（寻找两个正序数组的中位数）

c++

#include <vector>
#include <cinttypes>  // 包含INT32_MAX宏定义
using namespace std;class Solution {
public:// 辅助函数：寻找两个有序数组中第k小的元素int findK(vector<int> &n1, int ind1, vector<int> &n2, int ind2, int k) {int n = n1.size(), m = n2.size();// 若k为1，返回两数组当前起始位置的最小值（若某数组已遍历完则取另一数组的值）if (k == 1) {int a = (n == ind1 ? INT32_MAX : n1[ind1]);int b = (m == ind2 ? INT32_MAX : n2[ind2]);return min(a, b);}// 若某一数组已遍历完，直接返回另一数组的第k小元素if (n == ind1) return n2[ind2 + k - 1];if (m == ind2) return n1[ind1 + k - 1];// 计算两数组中各取的元素数量（尽量均分k）int cnt1 = min(k / 2, n - ind1);  // n1最多取k/2个元素（不超过剩余元素数）int cnt2 = min(k - cnt1, m - ind2);  // n2取剩余的k - cnt1个（不超过剩余元素数）cnt1 = k - cnt2;  // 重新计算cnt1，确保cnt1 + cnt2 = k// 比较两数组中第cnt1和cnt2个元素的大小，排除不可能包含第k小元素的部分if (n1[ind1 + cnt1 - 1] <= n2[ind2 + cnt2 - 1]) {// n1的前cnt1个元素不可能是第k小，递归查找剩余部分return findK(n1, ind1 + cnt1, n2, ind2, k - cnt1);} else {// n2的前cnt2个元素不可能是第k小，递归查找剩余部分return findK(n1, ind1, n2, ind2 + cnt2, k - cnt2);}}// 函数功能：求两个有序数组的中位数double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size(), m = nums2.size();int total = n + m;  // 总元素个数if (total % 2 == 1) {// 总元素为奇数，中位数是第(total/2 + 1)小的元素return findK(nums1, 0, nums2, 0, total / 2 + 1);} else {// 总元素为偶数，中位数是第(total/2)和第(total/2 + 1)小元素的平均值double a = findK(nums1, 0, nums2, 0, total / 2);double b = findK(nums1, 0, nums2, 0, total / 2 + 1);return (a + b) / 2.0;}}
};

解读：通过递归二分法寻找两个有序数组的第 k 小元素，进而计算中位数，时间复杂度 O (log (m+n))，避免了合并数组的 O (m+n) 空间复杂度。

三、树与二叉树相关代码解析

1. 哈夫曼编码提取（extractHaffmanCode）

c++

#include <cstring>
using namespace std;// 哈夫曼树节点结构（假设已定义）
struct Node {char ch;  // 字符Node *lchild, *rchild;  // 左右孩子
};char* char_code[256];  // 存储每个字符的哈夫曼编码// 函数功能：从哈夫曼树中提取每个字符的编码
void extractHaffmanCode(Node *root, char buff[], int k) {buff[k] = 0;  // 终止符，标记当前编码的结束// 若为叶子节点（无左右孩子），记录当前字符的编码if (root->lchild == NULL && root->rchild == NULL) {char_code[root->ch] = strdup(buff);  // 复制buff中的编码到字符对应的存储位置return ;}// 递归左子树，路径标记为'0'buff[k] = '0';extractHaffmanCode(root->lchild, buff, k + 1);// 递归右子树，路径标记为'1'buff[k] = '1';extractHaffmanCode(root->rchild, buff, k + 1);return ;
}

解读：通过深度优先遍历哈夫曼树，左子树路径记为 '0'，右子树记为 '1'，到达叶子节点时记录字符对应的编码，时间复杂度 O (n)（n 为树中节点数）。

2. Leetcode-Offer26（树的子结构）

c++

#include <iostream>
using namespace std;// 二叉树节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};class Solution {
public:// 辅助函数：判断B是否为A的子结构（从当前节点开始匹配）bool match_one(TreeNode *A, TreeNode *B) {if (A == NULL) return B == NULL;  // A为空时，B必须也为空才匹配if (B == NULL) return true;       // B为空时，默认匹配（子结构可短于父结构）if (A->val != B->val) return false;  // 节点值不相等，不匹配// 递归匹配左右子树return match_one(A->left, B->left) && match_one(A->right, B->right);}// 函数功能：判断B是否为A的子结构bool isSubStructure(TreeNode* A, TreeNode* B) {if (A == NULL) return B == NULL;  // A为空时，B必须为空才是子结构if (B == NULL) return false;      // B为空时，不存在子结构（题目定义）// 若当前节点匹配，且子树也匹配，则返回trueif (A->val == B->val && match_one(A, B)) return true;// 否则递归检查A的左子树和右子树if (isSubStructure(A->left, B)) return true;if (isSubStructure(A->right, B)) return true;// 均不匹配，返回falsereturn false;}
};

解读：通过递归遍历树 A 的每个节点，判断以该节点为根的子树是否包含树 B 的结构，时间复杂度 O (nm)（n、m 为两树节点数）。

3. Leetcode-105（从前序与中序遍历序列构造二叉树）

c++

#include <vector>
using namespace std;// 二叉树节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:// 函数功能：根据前序遍历和中序遍历构造二叉树TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {// 若前序遍历为空，返回空节点if (preorder.size() == 0) return NULL;// 前序遍历的第一个元素为根节点值int root_val = preorder[0];// 在中序遍历中找到根节点的位置（左为左子树，右为右子树）int pos = 0, n = preorder.size();while (inorder[pos] != root_val) pos += 1;// 创建根节点TreeNode *root = new TreeNode(root_val);// 提取左子树的前序和中序遍历vector<int> preArr, inArr;for (int i = 1; i <= pos; i++) preArr.push_back(preorder[i]);  // 前序左子树：[1, pos]for (int i = 0; i < pos; i++) inArr.push_back(inorder[i]);    // 中序左子树：[0, pos-1]// 递归构造左子树root->left = buildTree(preArr, inArr);// 提取右子树的前序和中序遍历preArr.clear();inArr.clear();for (int i = pos + 1; i < n; i++) preArr.push_back(preorder[i]);  // 前序右子树：[pos+1, n-1]for (int i = pos + 1; i < n; i++) inArr.push_back(inorder[i]);    // 中序右子树：[pos+1, n-1]// 递归构造右子树root->right = buildTree(preArr, inArr);return root;}
};

解读：利用前序遍历首元素为根、中序遍历根左右为左右子树的特性，递归分割数组构造二叉树，时间复杂度 O (n²)（最坏情况，可通过哈希表优化为 O (n)）。

4. Leetcode-226（翻转二叉树）

c++

#include <iostream>
using namespace std;// 二叉树节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:// 函数功能：翻转二叉树（左右子树交换）TreeNode* invertTree(TreeNode* root) {if (root == NULL) return NULL;  // 空树直接返回// 交换当前节点的左右子树swap(root->left, root->right);// 递归翻转左子树和右子树invertTree(root->left);invertTree(root->right);return root;}
};

解读：通过递归交换每个节点的左右子树，实现二叉树的翻转，时间复杂度 O (n)（n 为节点数）。

5. Leetcode-589（N 叉树的前序遍历）

c++

#include <vector>
using namespace std;// N叉树节点结构
class Node {
public:int val;vector<Node*> children;Node() {}Node(int _val) { val = _val; }Node(int _val, vector<Node*> _children) {val = _val;children = _children;}
};class Solution {
public:// 辅助函数：递归实现前序遍历void __preorder(Node *root, vector<int> &ans) {if (root == NULL) return ;  // 空节点直接返回ans.push_back(root->val);  // 先访问根节点// 递归遍历所有子节点for (auto x : root->children) {__preorder(x, ans);}return ;}// 函数功能：N叉树的前序遍历（根->子节点）vector<int> preorder(Node* root) {vector<int> ans;__preorder(root, ans);return ans;}
};

解读：前序遍历顺序为 “根节点 -> 子节点”，通过递归依次访问根节点和所有子节点，时间复杂度 O (n)（n 为节点数）。

6. Leetcode-102-1（二叉树的层序遍历）

c++

#include <vector>
#include <queue>
using namespace std;// 二叉树节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};class Solution {
public:// 函数功能：二叉树的层序遍历（按层输出节点值）vector<vector<int>> levelOrder(TreeNode* root) {if (root == NULL) return vector<vector<int>>();  // 空树返回空TreeNode *node;queue<TreeNode *> q;  // 队列用于存储当前层的节点q.push(root);vector<vector<int>> ans;  // 存储层序遍历结果// 逐层遍历while (!q.empty()) {int cnt = q.size();  // 当前层的节点数量vector<int> temp;    // 存储当前层的节点值// 遍历当前层的所有节点for (int i = 0; i < cnt; i++) {node = q.front();temp.push_back(node->val);  // 记录节点值// 将下一层的节点入队if (node->left) q.push(node->left);if (node->right) q.push(node->right);q.pop();  // 弹出当前节点}ans.push_back(temp);  // 将当前层结果加入总结果}return ans;}
};

解读：利用队列实现层序遍历，每次处理当前层的所有节点并将下一层节点入队，时间复杂度 O (n)，空间复杂度 O (n)。

四、排序算法相关代码解析

1. Leetcode-04（寻找两个正序数组的中位数，合并数组实现）

c++

#include <vector>
using namespace std;class Solution {
public:// 函数功能：求两个有序数组的中位数（合并数组法）double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size(), m = nums2.size();vector<int> temp(n + m);  // 存储合并后的数组int p1 = 0, p2 = 0, k = 0;  // p1、p2为两数组的指针，k为合并数组的指针// 合并两个有序数组（类似归并排序的合并过程）while (p1 < n || p2 < m) {// 若nums2已遍历完，或nums1当前元素更小，取nums1的元素if (p2 == m || (p1 < n && nums1[p1] <= nums2[p2])) {temp[k++] = nums1[p1++];} else {// 否则取nums2的元素temp[k++] = nums2[p2++];}}// 计算中位数double a = temp[(n + m) / 2], b = temp[(n + m) / 2];if ((n + m) % 2 == 0) {// 总元素为偶数，取中间两个元素的平均值b = temp[(n + m) / 2 - 1];}return (a + b) / 2.0;}
};

解读：先合并两个有序数组为一个有序数组，再根据总长度计算中位数，时间复杂度 O (n+m)，空间复杂度 O (n+m)，实现简单但效率低于二分法。

2. Leetcode-148-1（排序链表，快速排序思想）

c++

#include <iostream>
using namespace std;// 链表节点结构
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {
public:// 函数功能：对链表进行排序（快速排序思路：按基准值分割后递归）ListNode* sortList(ListNode* head) {if (head == NULL) return head;  // 空链表直接返回// 寻找链表中的最小值和最大值，确定基准值int l = head->val, r = head->val, z;ListNode *p = head, *h1 = NULL, *h2 = NULL, *q;while (p) {l = min(p->val, l);r = max(p->val, r);p = p->next;}z = (l + r) >> 1;  // 基准值（中间值）if (l == r) return head;  // 所有元素相等，直接返回// 按基准值分割链表为两部分：<=z的放h1，>z的放h2p = head;while (p) {q = p->next;  // 保存下一个节点if (p->val <= z) {p->next = h1;  // 插入h1头部h1 = p;} else {p->next = h2;  // 插入h2头部h2 = p;}p = q;}// 递归排序两部分h1 = sortList(h1);h2 = sortList(h2);// 合并排序后的两部分p = h1;while (p->next) p = p->next;  // 找到h1的尾节点p->next = h2;  // 连接h2return h1;}
};

解读：借鉴快速排序思想，以链表中值为基准分割链表为两部分，递归排序后合并，平均时间复杂度 O (n log n)，最坏情况 O (n²)。

3. Leetcode-148-2（排序链表，归并排序实现）

c++

#include <iostream>
using namespace std;// 链表节点结构
struct ListNode {int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution {
public:// 辅助函数：计算链表长度int getLength(ListNode *head) {int n = 0;while (head) {n += 1;head = head->next;}return n;}// 辅助函数：归并排序链表（对长度为n的链表排序）ListNode *merge_sort(ListNode *head, int n) {if (n <= 1) return head;  // 长度为0或1时直接返回// 分割链表为两部分，长度分别为l和rint l = n / 2, r = n - l;ListNode *p = head, *p1, *p2, ret;  // ret为临时头节点，用于合并// 找到分割点（前l个节点的尾节点）for (int i = 1; i < l; i++) p = p->next;p1 = head;        // 左半部分头节点p2 = p->next;     // 右半部分头节点p->next = NULL;   // 断开左半部分与右半部分的连接// 递归排序两部分p1 = merge_sort(p1, l);p2 = merge_sort(p2, r);// 合并两个有序链表p = &ret;ret.next = NULL;while (p1 || p2) {if (p2 == NULL || (p1 && p1->val <= p2->val)) {p->next = p1;p = p1;p1 = p1->next;} else {p->next = p2;p = p2;p2 = p2->next;}}return ret.next;  // 返回合并后的链表头}// 函数功能：对链表进行排序（归并排序实现）ListNode* sortList(ListNode* head) {int n = getLength(head);return merge_sort(head, n);}
};

解读：归并排序链表，先分割为两半，递归排序后合并，时间复杂度稳定为 O (n log n)，空间复杂度 O (log n)（递归栈）。

4. Leetcode-219（存在重复元素 II）

c++

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:// 函数功能：判断数组中是否存在两个相同元素，且索引差不超过kbool containsNearbyDuplicate(vector<int>& nums, int k) {int n = nums.size();vector<int> ind(n);  // 存储数组索引// 初始化索引数组for (int i = 0; i < n; i++) ind[i] = i;// 按数组值对索引排序（值相同则按索引排序）sort(ind.begin(), ind.end(), [&](int i, int j) -> bool {if (nums[i] != nums[j]) return nums[i] < nums[j];return i < j;});// 检查相邻的相同值元素，判断索引差是否 <=kfor (int i = 0, I = n - 1; i < I; i++) {// 若值不同，跳过if (nums[ind[i]] != nums[ind[i + 1]]) continue;// 若索引差符合条件，返回trueif (ind[i + 1] - ind[i] <= k) return true;}// 未找到符合条件的元素，返回falsereturn false;}
};

解读：通过排序索引数组，使相同值的元素索引相邻，再检查相邻索引差是否符合条件，时间复杂度 O (n log n)。

5. Leetcode-01（两数之和，双指针实现）

c++

#include <vector>
#include <algorithm>
using namespace std;class Solution {
public:// 函数功能：求两数之和的索引（排序+双指针实现）vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();vector<int> ind(n);  // 存储数组索引// 初始化索引数组for (int i = 0; i < n; i++) ind[i] = i;// 按数组值对索引排序sort(ind.begin(), ind.end(), [&](int i, int j) -> bool {return nums[i] < nums[j];});// 双指针：p1从左向右，p2从右向左int p1 = 0, p2 = n - 1;while (nums[ind[p1]] + nums[ind[p2]] != target) {if (nums[ind[p1]] + nums[ind[p2]] < target) {p1 += 1;  // 和小于目标值，左指针右移} else {p2 -= 1;  // 和大于目标值，右指针左移}}// 存储结果并保证索引升序vector<int> ret(2);ret[0] = ind[p1], ret[1] = ind[p2];if (ret[0] > ret[1]) swap(ret[0], ret[1]);return ret;}
};

解读：排序索引数组后，用双指针从两端向中间逼近，寻找和为 target 的元素，时间复杂度 O (n log n)。

五、字符串匹配相关代码解析

1. Boyer-Moore 算法（字符串匹配）

c++

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;// 宏定义：测试函数并输出结果
#define TEST(func, s, t) { \printf("%s(%s, %s) = %d\n", #func, s, t, func(s, t)); \
}// 暴力匹配算法
int brute_force(const char *s, const char *t) {for (int i = 0; s[i]; i++) {  // 遍历主串int flag = 1;for (int j = 0; t[j]; j++) {  // 遍历模式串if (s[i + j] == t[j]) continue;flag = 0;break;}if (flag == 1) return i;  // 匹配成功，返回起始索引}return -1;  // 匹配失败
}// Sunday算法
int sunday(const char *s, const char *t) {int len[256] = {0}, n = strlen(s), m = strlen(t);// 初始化模式串中每个字符的偏移量（默认为m+1）for (int i = 0; i < 256; i++) len[i] = m + 1;for (int i = 0; t[i]; i++) len[t[i]] = m - i;  // 字符t[i]的偏移量为m - i// 主串指针i，每次按偏移量移动for (int i = 0; i + m <= n; i += len[s[i + m]]) {int flag = 1;for (int j = 0; t[j]; j++) {  // 检查当前位置是否匹配if (s[i + j] == t[j]) continue;flag = 0;break;}if (flag == 1) return i;  // 匹配成功}return -1;  // 匹配失败
}// 计算Boyer-Moore算法的delta1数组（坏字符规则）
int *getDelta1(const char *t) {int *delta1 = (int *)malloc(sizeof(int) * 256);for (int i = 0; i < 256; i++) delta1[i] = -1;  // 默认为-1（字符未出现）for (int i = 0; t[i]; i++) {delta1[t[i]] = i;  // 记录字符最后出现的位置}return delta1;
}// 计算模式串的后缀长度数组
int *getSuffixes(const char *t) {int tlen = strlen(t);int *suff = (int *)malloc(sizeof(int) * tlen);suff[tlen - 1] = tlen;  // 最后一个字符的后缀长度为tlenfor (int i = 0; i < tlen - 1; i++) {int j = 0;// 计算以i为终点的最长后缀与模式串后缀的匹配长度while (j <= i && t[tlen - j - 1] == t[i - j]) ++j;suff[i] = j;}return suff;
}// 计算Boyer-Moore算法的delta2数组（好后缀规则）
int *getDelta2(const char *t) {int *suff = getSuffixes(t);int tlen = strlen(t), lastInd = tlen - 1;int *delta2 = (int *)malloc(sizeof(int) * tlen);for (int i = 0; t[i]; i++) delta2[i] = tlen;  // 默认为tlen// 情况1：好后缀是模式串的前缀for (int i = 0; i < tlen; i++) {if (suff[i] != i + 1) continue;  // 不是前缀// 更新delta2[j]为lastInd - i（可移动的距离）for (int j = 0; j <= lastInd - suff[i]; j++) delta2[j] = lastInd - i;}// 情况2：好后缀在模式串中存在其他匹配for (int i = 0; i < lastInd; i++) {delta2[lastInd - suff[i]] = lastInd - i;}return delta2;
}// Boyer-Moore算法
int BM(const char *s, const char *t) {int *delta1 = getDelta1(t);  // 坏字符规则数组int *delta2 = getDelta2(t);  // 好后缀规则数组int slen = strlen(s), tlen = strlen(t);// 主串指针j，从0开始for (int j = 0; j + tlen <= slen;) {int i = tlen - 1;  // 模式串指针，从末尾开始// 从后向前匹配while (i >= 0 && t[i] == s[j + i]) --i;if (i == -1) return j;  // 匹配成功，返回起始索引// 按坏字符规则和好后缀规则的最大值移动主串指针j += max(i - delta1[s[j + i]], delta2[i]);}return -1;  // 匹配失败
}// 测试主函数
int main() {char s[100], t[100];while (~scanf("%s%s", s, t)) {TEST(brute_force, s, t);TEST(sunday, s, t);TEST(BM, s, t);}return 0;
}

解读：实现了三种字符串匹配算法：

暴力匹配：逐个字符比对，时间复杂度 O (nm)；
Sunday 算法：通过计算偏移量快速移动主串指针，平均效率较高；
Boyer-Moore 算法：结合坏字符规则和好后缀规则，大幅减少比对次数，是高效的字符串匹配算法之一。

2. AC 自动机（多模式串匹配）

c++

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;#define MAX_N 20000  // 最大节点数// AC自动机节点结构
struct Node {int fail;  // 失败指针int next[26];  // 子节点（26个小写字母）vector<int> ind;  // 存储包含当前节点的模式串索引
} AC[MAX_N + 5];int node_cnt = 1, root = 1;  // 节点计数器和根节点
char s[1000006], t[200][75];  // s为主串，t为模式串数组
int tcnt[200];  // 记录每个模式串的匹配次数// 创建新节点
inline int getNewNode() {++node_cnt;AC[node_cnt].fail = 0;for (int i = 0; i < 26; i++) AC[node_cnt].next[i] = 0;AC[node_cnt].ind.clear();return node_cnt;
}// 插入模式串到AC自动机
void insert(char *s, int k) {int p = root;for (int i = 0; s[i]; i++) {int ind = s[i] - 'a';  // 字符转为索引（0-25）if (AC[p].next[ind] == 0) {AC[p].next[ind] = getNewNode();  // 不存在则创建新节点}p = AC[p].next[ind];  // 移动到子节点}AC[p].ind.push_back(k);  // 记录模式串索引return ;
}// 构建AC自动机的失败指针（类似KMP的next数组）
void build_ac() {queue<int> que;que.push(root);while (!que.empty()) {int cur = que.front();// 继承失败指针的模式串索引if (AC[cur].fail) {int p = AC[cur].fail;for (int i = 0, I = AC[p].ind.size(); i < I; i++) {AC[cur].ind.push_back(AC[p].ind[i]);}}que.pop();// 处理每个子节点for (int i = 0; i < 26; i++) {if (AC[cur].next[i] == 0) {// 子节点不存在，指向失败指针的对应子节点（根节点特殊处理）if (AC[cur].fail == 0) AC[cur].next[i] = root;else AC[cur].next[i] = AC[AC[cur].fail].next[i];continue;}// 计算子节点的失败指针int p = AC[cur].fail;if (p == 0) p = root;else p = AC[AC[cur].fail].next[i];AC[AC[cur].next[i]].fail = p;que.push(AC[cur].next[i]);  // 子节点入队}}return ;
}// 在主串中查找所有模式串的匹配
void find_all(char *s) {int p = root;for (int i = 0; s[i]; i++) {int ind = s[i] - 'a';p = AC[p].next[ind];  // 移动到对应子节点// 累加所有匹配的模式串计数for (int i = 0, I = AC[p].ind.size(); i < I; i++) {tcnt[AC[p].ind[i]] += 1;}}return ;
}// 初始化AC自动机
void init() {node_cnt = 0;root = getNewNode();memset(tcnt, 0, sizeof(tcnt));return ;
}// 处理测试用例
void solve(int n) {init();// 插入所有模式串for (int i = 0; i < n; i++) {scanf("%s", t[i]);insert(t[i], i);}build_ac();  // 构建失败指针scanf("%s", s);  // 读取主串find_all(s);  // 查找匹配// 寻找最大匹配次数int ans = 0;for (int i = 0; i < n; i++) {if (ans < tcnt[i]) ans = tcnt[i];}printf("%d\n", ans);// 输出所有匹配次数为最大值的模式串for (int i = 0; i < n; i++) {if (tcnt[i] == ans) printf("%s\n", t[i]);} return ;
}// 主函数
int main() {int n;while (scanf("%d", &n) != EOF) {if (n == 0) break;solve(n);}return 0;
}

解读：AC 自动机是多模式串匹配的高效算法，通过构建字典树、失败指针（类似 KMP 的前缀函数），实现一次遍历主串即可匹配所有模式串，时间复杂度接近 O (n + m + z)（n 为主串长度，m 为所有模式串总长度，z 为匹配次数）。

六、递归程序设计相关代码解析

1. HZOJ-236（组合数输出）

c++

#include <iostream>
#include <vector>
using namespace std;int arr[10];  // 存储当前组合// 输出当前组合结果
void print_one_result(int n) {for (int i = 0; i < n; i++) {if (i) cout << " ";cout << arr[i];}cout << endl;return ;
}// 递归生成组合：从n个数中选m个，当前选到第i个位置，下一个数从j开始
void f(int i, int j, int n, int m) {if (i == m) {  // 已选够m个元素，输出结果print_one_result(m);return ;}// 从j开始选择，保证组合递增且不重复（剪枝：剩余元素足够选完）for (int k = j; k <= n && m - i - 1 <= n - k; k++) {arr[i] = k;  // 选择当前元素f(i + 1, k + 1, n, m);  // 递归选择下一个元素（下一个从k+1开始）}return ;
}int main() {int n, m;cin >> n >> m;f(0, 1, n, m);  // 从1开始选，第一个位置为0return 0;
}

解读：通过递归生成从 n 个数中选 m 个的所有组合（不考虑顺序），利用剪枝优化减少无效递归，时间复杂度 O (C (n, m))（组合数）。

2. HZOJ-237（全排列输出）

c++

#include <iostream>
#include <vector>
using namespace std;int arr[10], vis[10] = {0};  // arr存储排列，vis标记元素是否已使用// 输出当前排列结果
void print_one_result(int n) {for (int i = 0; i < n; i++) {if (i) cout << " ";cout << arr[i];}cout << endl;return ;
}// 递归生成全排列：当前填充第i个位置
void f(int i, int n) {if (i == n) {  // 已填充完n个位置，输出结果print_one_result(n);return ;}// 尝试所有未使用的元素for (int k = 1; k <= n; k++) {if (vis[k]) continue;  // 元素已使用，跳过arr[i] = k;  // 选择当前元素vis[k] = 1;  // 标记为已使用f(i + 1, n);  // 递归填充下一个位置vis[k] = 0;  // 回溯：取消标记}return ;
}int main() {int n;cin >> n;f(0, n);  // 从第0个位置开始填充return 0;
}

解读：通过递归与回溯生成 n 个数的全排列，使用 vis 数组标记已使用元素，时间复杂度 O (n!)。

七、并查集相关代码解析（Leetcode-200：岛屿数量）

c++

#include <vector>
using namespace std;// 并查集类
class UnionSet {
public :// 构造函数：初始化父节点数组（每个节点的父节点是自身）UnionSet(int n) : fa(n + 1) {for (int i = 0; i <= n; i++) fa[i] = i;}// 查找函数：带路径压缩（找到根节点，并使路径上节点直接指向根）int get(int x) {return fa[x] = (fa[x] == x ? x : get(fa[x]));}// 合并函数：将a和b所在集合合并（a的根节点指向b的根节点）void merge(int a, int b) {fa[get(a)] = get(b);return ;}vector<int> fa;  // 父节点数组
};class Solution {
public:// 函数功能：计算二维网格中岛屿的数量（'1'为陆地，'0'为水）int numIslands(vector<vector<char>>& grid) {if (grid.empty()) return 0;  // 空网格返回0int n = grid.size(), m = grid[0].size();UnionSet u(n * m);  // 并查集，节点数为n*m（每个格子对应一个节点）// 遍历每个格子，合并相邻陆地for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == '0') continue;  // 水不处理int ind = i * m + j + 1;  // 当前格子的索引（从1开始）// 合并右侧陆地（同一行）if (j + 1 < m && grid[i][j + 1] == '1') {u.merge(ind, ind + 1);}// 合并下方陆地（同一列）if (i + 1 < n && grid[i + 1][j] == '1') {u.merge(ind, ind + m);}}}// 统计根节点数量（每个根节点对应一个岛屿）int ans = 0;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {int ind = i * m + j + 1;if (grid[i][j] == '1' && u.get(ind) == ind) {ans += 1;}}}return ans;}
};

解读：利用并查集合并相邻的陆地格子，最终根节点的数量即为岛屿数量，时间复杂度接近 O (nm)（路径压缩和按秩合并优化后）。

八、路飞吃桃问题（HZOJ-184）

1. C 语言实现

运行

#include <stdio.h>int main() {int i, n, r = 1;  // r初始为1（第1天剩余1个桃）scanf("%d", &n);  // 输入天数n// 从第n-1天倒推到第1天for (i = 1; i < n; i++) {r = (r + 1) * 2;  // 每天的桃子数是前一天的2倍加2}printf("%d", r);  // 输出第n天的桃子数return 0;
}

2. C++ 实现

cpp

运行

#include <iostream>
using namespace std;int main() {int i, n, r = 1;  // r初始为1（第1天剩余1个桃）cin >> n;  // 输入天数n// 从第n-1天倒推到第1天for (i = 1; i < n; i++) {r = (r + 1) * 2;  // 每天的桃子数是前一天的2倍加2}cout << r << endl;  // 输出第n天的桃子数return 0;
}

3. Java 实现

java

运行

import java.util.Scanner;public class Main {// 递归计算第n天的桃子数int Peach(int n) {if (n == 1) {return 1;  // 第1天剩余1个桃}return 2 * (Peach(n - 1) + 1);  // 第n天的桃子数 = 2*(第n-1天的桃子数 + 1)}public static void main(String[] args) {Main main = new Main();Scanner sc = new Scanner(System.in);int n = sc.nextInt();  // 输入天数nSystem.out.println(main.Peach(n) + "");  // 输出结果}
}

解读：问题为 “每天吃一半加 1 个，第 n 天剩 1 个”，通过倒推法计算第 1 天的桃子数。递归公式为 f (n) = 2*(f (n-1)+1)，非递归通过循环实现，时间复杂度 O (n)。

以上内容涵盖了该仓库中主要代码文件的提取、注释及解读，内容已尽量避免与原代码注释重复，可满足技术文档的需求。

编辑分享

.gitignore

我要的是该仓库中所有代码文件的提取、注释及解读，内容不需要避免与原代码注释重复

（一）基础算法模块

1. 第 0 章：从复杂度开始认识算法

0.1 时间复杂度计算示例（calc_time_complexity.c）

运行

#include <stdio.h>// 函数功能：计算两个数组对应元素乘积之和（用于演示O(n)时间复杂度）
// 输入：arr1-数组1，arr2-数组2，n-数组长度
// 输出：乘积之和
int calc_product_sum(int arr1[], int arr2[], int n) {int sum = 0;// 循环执行n次，每次操作均为常数时间O(1)，整体时间复杂度O(n)for (int i = 0; i < n; i++) {sum += arr1[i] * arr2[i];  // 常数操作：乘法+加法+赋值}return sum;
}// 函数功能：计算矩阵乘法（用于演示O(n³)时间复杂度）
// 输入：mat1-矩阵1，mat2-矩阵2，result-结果矩阵，n-矩阵维度
void matrix_multiply(int mat1[][100], int mat2[][100], int result[][100], int n) {// 三层嵌套循环，每层执行n次，整体时间复杂度O(n³)for (int i = 0; i < n; i++) {          // 控制结果矩阵行for (int j = 0; j < n; j++) {      // 控制结果矩阵列result[i][j] = 0;              // 初始化结果元素for (int k = 0; k < n; k++) {  // 计算对应元素乘积和result[i][j] += mat1[i][k] * mat2[k][j];}}}
}int main() {// 测试O(n)复杂度函数int arr1[5] = {1,2,3,4,5}, arr2[5] = {2,3,4,5,6};printf("乘积之和：%d\n", calc_product_sum(arr1, arr2, 5));// 测试O(n³)复杂度函数int mat1[2][100] = {{1,2},{3,4}}, mat2[2][100] = {{5,6},{7,8}}, result[2][100];matrix_multiply(mat1, mat2, result, 2);printf("矩阵乘法结果：\n");for (int i = 0; i < 2; i++) {for (int j = 0; j < 2; j++) {printf("%d ", result[i][j]);}printf("\n");}return 0;
}

解读：该文件通过两个经典案例演示时间复杂度计算：

数组乘积和：单层循环，时间复杂度 O (n)，空间复杂度 O (1)（仅用常量额外空间）；
矩阵乘法：三层嵌套循环，时间复杂度 O (n³)，空间复杂度 O (n²)（存储结果矩阵），帮助理解 “循环嵌套层数” 与时间复杂度的关联。

2. 第 1 章：递归程序设计技巧

1.1 斐波那契数列递归实现（fib_recursion.c）

运行

#include <stdio.h>// 函数功能：递归计算第n个斐波那契数（斐波那契数列：F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)）
// 输入：n-斐波那契数的序号（n≥0）
// 输出：第n个斐波那契数
int fibonacci(int n) {// 递归终止条件：base case（避免无限递归）if (n == 0) return 0;if (n == 1) return 1;// 递归递推：将问题分解为更小的子问题（F(n-1)和F(n-2)）return fibonacci(n - 1) + fibonacci(n - 2);
}int main() {int n;printf("请输入斐波那契数的序号：");scanf("%d", &n);// 输入合法性检查if (n < 0) {printf("序号需为非负整数！\n");return 1;}printf("第%d个斐波那契数：%d\n", n, fibonacci(n));return 0;
}

1.2 汉诺塔问题递归实现（hanoi_recursion.c）

运行

#include <stdio.h>// 函数功能：递归实现汉诺塔移动（将n个盘子从from柱移到to柱，借助aux柱）
// 输入：n-盘子数量，from-起始柱子，aux-辅助柱子，to-目标柱子
void hanoi(int n, char from, char aux, char to) {// 递归终止条件：只有1个盘子时，直接从from移到toif (n == 1) {printf("将盘子1从%c柱移到%c柱\n", from, to);return;}// 步骤1：将n-1个盘子从from移到aux，借助tohanoi(n - 1, from, to, aux);// 步骤2：将第n个盘子（最大盘）从from移到toprintf("将盘子%d从%c柱移到%c柱\n", n, from, to);// 步骤3：将n-1个盘子从aux移到to，借助fromhanoi(n - 1, aux, from, to);
}int main() {int n;printf("请输入汉诺塔盘子数量：");scanf("%d", &n);if (n < 1) {printf("盘子数量需为正整数！\n");return 1;}printf("汉诺塔移动步骤：\n");hanoi(n, 'A', 'B', 'C');  // 约定柱子为A（起始）、B（辅助）、C（目标）return 0;
}

3. 第 2 章：顺序表和链表

2.1 顺序表实现（seq_list.c）

运行

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100  // 顺序表最大容量
// 顺序表结构体：存储数据+当前长度
typedef struct {int data[MAX_SIZE];  // 数组存储数据（连续内存）int length;          // 当前元素个数（length ≤ MAX_SIZE）
} SeqList;// 函数功能：初始化顺序表（空表，length=0）
void init_seq_list(SeqList *L) {L->length = 0;
}// 函数功能：在顺序表第pos位置插入元素val（pos从1开始）
// 输入：L-顺序表指针，pos-插入位置，val-插入元素
// 输出：1-插入成功，0-插入失败（位置非法或表满）
int insert_seq_list(SeqList *L, int pos, int val) {// 合法性检查：pos范围（1~L->length+1）、表是否满if (pos < 1 || pos > L->length + 1 || L->length >= MAX_SIZE) {return 0;}// 从后向前移动元素，腾出pos位置（时间复杂度O(n)）for (int i = L->length; i >= pos; i--) {L->data[i] = L->data[i - 1];}// 插入元素，更新长度L->data[pos - 1] = val;  // 数组索引从0开始，pos需减1L->length++;return 1;
}// 函数功能：删除顺序表第pos位置的元素，并用val存储删除的元素
// 输入：L-顺序表指针，pos-删除位置，val-存储删除元素的指针
// 输出：1-删除成功，0-删除失败（位置非法）
int delete_seq_list(SeqList *L, int pos, int *val) {if (pos < 1 || pos > L->length) {return 0;}// 存储删除的元素*val = L->data[pos - 1];// 从前向后移动元素，覆盖删除位置（时间复杂度O(n)）for (int i = pos; i < L->length; i++) {L->data[i - 1] = L->data[i];}// 更新长度L->length--;return 1;
}// 函数功能：打印顺序表所有元素
void print_seq_list(SeqList *L) {if (L->length == 0) {printf("顺序表为空！\n");return;}printf("顺序表元素：");for (int i = 0; i < L->length; i++) {printf("%d ", L->data[i]);}printf("\n");
}int main() {SeqList L;init_seq_list(&L);// 插入测试insert_seq_list(&L, 1, 10);insert_seq_list(&L, 2, 20);insert_seq_list(&L, 2, 15);print_seq_list(&L);  // 预期：10 15 20// 删除测试int del_val;delete_seq_list(&L, 2, &del_val);printf("删除的元素：%d\n", del_val);  // 预期：15print_seq_list(&L);  // 预期：10 20return 0;
}

2.2 单链表实现（single_linked_list.c）

运行

#include <stdio.h>
#include <stdlib.h>// 链表节点结构体：存储数据+下一个节点指针
typedef struct Node {int data;          // 节点数据struct Node *next; // 指向后继节点的指针
} Node, *LinkedList;// 函数功能：初始化单链表（带头节点，空表）
// 输出：头节点指针（头节点不存储实际数据，仅用于简化操作）
LinkedList init_linked_list() {LinkedList head = (Node *)malloc(sizeof(Node));  // 分配头节点内存head->next = NULL;  // 空表，头节点后继为NULLreturn head;
}// 函数功能：在链表头部插入元素val（头插法，时间复杂度O(1)）
void insert_head(LinkedList head, int val) {// 创建新节点Node *new_node = (Node *)malloc(sizeof(Node));new_node->data = val;// 新节点指向原头节点的后继new_node->next = head->next;// 头节点指向新节点head->next = new_node;
}// 函数功能：在链表尾部插入元素val（尾插法，时间复杂度O(n)）
void insert_tail(LinkedList head, int val) {Node *new_node = (Node *)malloc(sizeof(Node));new_node->data = val;new_node->next = NULL;  // 尾节点后继为NULL// 找到链表尾部节点（从头节点开始遍历）Node *p = head;while (p->next != NULL) {p = p->next;}// 尾部节点指向新节点p->next = new_node;
}// 函数功能：删除链表中第一个值为val的节点
// 输出：1-删除成功，0-删除失败（未找到val）
int delete_node(LinkedList head, int val) {Node *p = head;  // p指向当前节点的前驱// 遍历链表，查找值为val的节点while (p->next != NULL && p->next->data != val) {p = p->next;}// 未找到valif (p->next == NULL) {return 0;}// 找到val，删除p->next节点Node *del_node = p->next;  // 存储待删除节点p->next = del_node->next;  // 前驱节点指向后继节点free(del_node);            // 释放待删除节点内存（避免内存泄漏）return 1;
}// 函数功能：打印链表所有元素
void print_linked_list(LinkedList head) {Node *p = head->next;  // 从第一个有效节点开始遍历if (p == NULL) {printf("链表为空！\n");return;}printf("链表元素：");while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n");
}// 函数功能：销毁链表（释放所有节点内存）
void destroy_linked_list(LinkedList head) {Node *p = head;while (p != NULL) {Node *temp = p;  // 存储当前节点p = p->next;     // 移动到下一个节点free(temp);      // 释放当前节点内存}
}int main() {LinkedList head = init_linked_list();// 尾插法插入元素insert_tail(head, 10);insert_tail(head, 20);insert_tail(head, 30);print_linked_list(head);  // 预期：10 20 30// 头插法插入元素insert_head(head, 5);print_linked_list(head);  // 预期：5 10 20 30// 删除测试delete_node(head, 20);print_linked_list(head);  // 预期：5 10 30// 销毁链表destroy_linked_list(head);return 0;
}

4. 第 3 章：栈与队列

3.1 顺序栈实现（seq_stack.c）

运行

#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100  // 栈最大容量
// 顺序栈结构体：数组存储数据+栈顶指针（top=-1表示空栈）
typedef struct {int data[MAX_SIZE];  // 数组存储栈元素int top;             // 栈顶指针（指向栈顶元素，空栈时为-1）
} SeqStack;// 函数功能：初始化栈（空栈，top=-1）
void init_stack(SeqStack *stack) {stack->top = -1;
}// 函数功能：判断栈是否为空
// 输出：1-空栈，0-非空栈
int is_empty(SeqStack *stack) {return stack->top == -1;
}// 函数功能：判断栈是否已满
// 输出：1-满栈，0-非满栈
int is_full(SeqStack *stack) {return stack->top ==

1. 第 1 章：递归程序设计技巧

文件：1. 第 1 章：递归程序设计技巧 / 第一章代码 / 2.HZOJ-186.cpp

cpp

运行

int main() {int n;vector<int> arr;  // 定义动态数组存储输入数据cin >> n;         // 读取输入数据的数量for (int i = 0, a; i < n; i++) {cin >> a;     // 循环读取每个数据arr.push_back(a);  // 将数据存入动态数组}cout << f(0, arr, n) << endl;  // 调用递归函数f处理数据并输出结果return 0;
}

解读：
该代码是递归问题的主程序框架，负责读取输入数据并调用递归函数f进行处理。通过vector动态存储输入数据，适配不同规模的输入。核心逻辑在未展示的递归函数f中，推测可能用于解决如最大子数组和、组合数计算等递归经典问题。

2. 第 2 章：顺序表和链表

文件：2. 第 2 章：顺序表和链表 / 第二章代码 / 5.leetcode-141.cpp

cpp

运行

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *p = head, *q = head;  // 定义快慢指针while (q && q->next) {  // 快指针未到达链表尾部p = p->next;        // 慢指针走1步q = q->next->next;  // 快指针走2步if (p == q) return true;  // 相遇则存在环}return false;  // 快指针到达尾部，无环}
};

解读：
该代码实现了链表环检测的 "快慢指针法"，时间复杂度O(n)，空间复杂度O(1)。原理是：若链表存在环，快指针（每次 2 步）终将追上慢指针（每次 1 步）；若不存在环，快指针会先到达链表尾部。

3. 第 3 章：栈与队列

文件：3. 第 3 章：栈与队列 / 第三章代码 / 7.Leetcode-844.cpp

cpp

运行

class Solution {
public:// 将字符串处理后压入栈（模拟退格操作）void pushStack(string &s, stack<char> &s1) {for (int i = 0; s[i]; i++) {if (s[i] == '#') {  // 遇到退格符if (!s1.empty()) s1.pop();  // 弹出栈顶元素} else s1.push(s[i]);  // 否则压入字符}return ;}// 比较两个字符串经退格处理后是否相等bool backspaceCompare(string s, string t) {stack<char> s1, s2;  // 定义两个栈分别处理两个字符串pushStack(s, s1);pushStack(t, s2);if (s1.size() != s2.size()) return false;  // 长度不同直接返回false// 逐个比较栈顶元素while (!s1.empty()) {if (s1.top() != s2.top()) return false;s1.pop(), s2.pop();}return true;}
};

解读：
该代码通过栈模拟字符串的退格操作（#代表删除前一个字符），再比较处理后的结果是否一致。栈的特性确保了退格操作的正确模拟，时间复杂度O(n)，空间复杂度O(n)（n为字符串长度）。

文件：3. 第 3 章：栈与队列 / 第三章代码 / 9.Leetcode-946.cpp

cpp

运行

class Solution {
public:bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {int x = 0, n = pushed.size();  // x记录push的位置stack<int> s;  // 模拟栈操作for (int i = 0; i < n; i++) {  // 遍历弹出序列// 栈顶元素与当前弹出元素不符，继续pushif (s.empty() || s.top() != popped[i]) {while (x < pushed.size() && pushed[x] != popped[i]) {s.push(pushed[x]);x += 1;}if (x == pushed.size()) return false;  // 无匹配元素，序列无效s.push(pushed[x]); x += 1;  // 压入目标元素}s.pop();  // 弹出匹配元素}return true;  // 所有元素匹配成功}
};

解读：
该代码验证栈的压入（pushed）和弹出（popped）序列是否合法。通过模拟栈操作，当栈顶与弹出元素不符时继续压入，直到找到匹配元素或无法匹配。时间复杂度O(n)，空间复杂度O(n)。

4. 第 4 章：树与二叉树

文件：4. 第 4 章：树与二叉树 / 第四章代码 / 1.binary_tree.cpp

cpp

运行

void bfs(Node *root) {head = tail = 0;  // 初始化队列头尾指针queue[tail++] = root;  // 根节点入队while (head < tail) {  // 队列非空Node *node = queue[head];  // 出队头节点printf("\nnode : %d\n", node->key);  // 打印当前节点值// 左子树入队并打印关系if (node->lchild) {queue[tail++] = node->lchild;printf("\t%d->%d (left)\n", node->key, node->lchild->key);}// 右子树入队并打印关系if (node->rchild) {queue[tail++] = node->rchild;printf("\t%d->%d (right)\n", node->key, node->rchild->key);}head++;  // 移动头指针}return ;
}

解读：
该代码实现了二叉树的广度优先搜索（BFS，层序遍历）。通过队列存储待访问节点，依次打印节点值及与子节点的关系，直观展示树的层次结构。时间复杂度O(n)（n为节点数），空间复杂度O(n)（队列最大存储一层节点）。

文件：4. 第 4 章：树与二叉树 / 第四章代码 / 8.Leetcode-105.cpp

cpp

运行

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if (preorder.size() == 0) return NULL;  // 空序列返回空树int pos = 0, n = preorder.size();// 查找根节点在中序遍历中的位置while (inorder[pos] != preorder[0]) pos += 1;TreeNode *root = new TreeNode(preorder[0]);  // 创建根节点// 构建左子树的前序和中序序列vector<int> preArr, inArr;for (int i = 1; i <= pos; i++) preArr.push_back(preorder[i]);for (int i = 0; i < pos; i++) inArr.push_back(inorder[i]);root->left = buildTree(preArr, inArr);  // 递归构建左子树// 构建右子树的前序和中序序列preArr.clear();inArr.clear();for (int i = pos + 1; i < n; i++) preArr.push_back(preorder[i]);for (int i = pos + 1; i < n; i++) inArr.push_back(inorder[i]);root->right = buildTree(preArr, inArr);  // 递归构建右子树return root;}
};

解读：
该代码根据前序遍历（preorder）和中序遍历（inorder）序列重建二叉树。核心原理是：前序序列首元素为根节点，中序序列中根节点左侧为左子树，右侧为右子树，递归构建左右子树。时间复杂度O(n²)（最坏情况，可通过哈希表优化至O(n)）。

文件：4. 第 4 章：树与二叉树 / 第四章代码 / 3.serialize_deserialize.cpp（核心函数）

cpp

运行

// 序列化：将二叉树转为字符串
char buff[1000];
int len = 0;
void __serialize(Node *root) {if (root == NULL) return ;len += snprintf(buff + len, 100, "%d", root->key);  // 写入节点值if (root->lchild == NULL && root->rchild == NULL) return ;  // 叶子节点无需括号len += snprintf(buff + len, 100, "(");  // 左括号__serialize(root->lchild);  // 递归序列化左子树if (root->rchild) {len += snprintf(buff + len, 100, ",");  // 右子树存在时加逗号__serialize(root->rchild);  // 递归序列化右子树}len += snprintf(buff + len, 100, ")");  // 右括号return ;
}// 反序列化：将字符串转为二叉树
Node *deserialize(char *buff, int n) {Node **s = (Node **)malloc(sizeof(Node *) * MAX_NODE);  // 栈存储节点int top = -1, flag = 0, scode = 0;  // flag标记左右子树，scode状态机Node *p = NULL, *root = NULL;for (int i = 0; buff[i]; i++) {switch (scode) {case 0:  // 初始状态，判断下一个字符类型if (buff[i] >= '0' && buff[i] <= '9') scode = 1;  // 数字→解析节点值else if (buff[i] == '(') scode = 2;  // 左括号→入栈else if (buff[i] == ',') scode = 3;  // 逗号→切换到右子树else scode = 4;  // 右括号→出栈i -= 1;  // 回退索引，重新处理当前字符break;case 1:  // 解析节点值int key = 0;while (buff[i] <= '9' && buff[i] >= '0') {key = key * 10 + (buff[i] - '0');i += 1;}p = getNewNode(key);  // 创建新节点// 关联到父节点的左/右子树if (top >= 0 && flag == 0) s[top]->lchild = p;if (top >= 0 && flag == 1) s[top]->rchild = p;i -= 1;  // 回退索引scode = 0;break;case 2:  // 左括号：当前节点入栈，准备处理左子树s[++top] = p;flag = 0;scode = 0;break;case 3:  // 逗号：切换到右子树flag = 1;scode = 0;break;case 4:  // 右括号：栈顶节点出栈root = s[top];top -= 1;scode = 0;break;}}return root;
}

解读：
该代码实现二叉树的序列化（转为字符串）和反序列化（字符串重构为树）。序列化采用 "节点值 (左子树，右子树)" 格式，反序列化通过状态机和栈解析字符串，重建树结构。适用于二叉树的存储与传输场景。

5. 第 5 章：堆与优先队列

文件：5. 第 5 章：堆与优先队列 / 第五章代码 / 7.Leetcode-23.cpp

cpp

运行

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {typedef pair<int, int> PII;  // 存储(节点值, 链表索引)int n = lists.size();set<PII> s;  // 有序集合模拟优先队列（最小堆）// 初始化：将每个链表的头节点入队for (int i = 0; i < n; i++) {if (lists[i] == nullptr) continue;s.insert(PII(lists[i]->val, i));}ListNode new_head, *p = &new_head, *q;  // 哨兵节点简化操作new_head.next = nullptr;while (s.size()) {PII a = *s.begin();  // 取最小值节点s.erase(s.begin());q = lists[a.second];  // 获取对应节点lists[a.second] = lists[a.second]->next;  // 移动链表指针p->next = q;  // 接入结果链表q->next = nullptr;p = q;// 若链表未空，将下一个节点入队if (lists[a.second]) {s.insert(PII(lists[a.second]->val, a.second));}}return new_head.next;  // 返回结果链表头}
};

解读：
该代码实现k个有序链表的合并，利用set（有序集合）模拟最小堆，每次取出最小值节点接入结果链表，再将该链表的下一个节点入堆。时间复杂度O(n log k)（n为总节点数，k为链表数），空间复杂度O(k)。

6. 第 6 章：排序算法

文件：6. 第 6 章：排序算法 / 第六章代码 / 12.Leetcode-88.cpp

cpp

运行

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {// p1指向nums1有效末尾，p2指向nums2末尾，k指向合并后末尾int p1 = m - 1, p2 = n - 1, k = m + n - 1;while (p1 != -1 || p2 != -1) {// 取较大元素放入nums1末尾if (p2 == -1 || (p1 != -1 && nums1[p1] >= nums2[p2])) {nums1[k--] = nums1[p1--];} else {nums1[k--] = nums2[p2--];}}return ;}
};

解读：
该代码实现两个有序数组的合并（nums1有足够空间容纳nums2），采用 "从后往前" 合并策略，避免覆盖未处理的元素。时间复杂度O(m+n)，空间复杂度O(1)，高效利用已有空间。

文件：6. 第 6 章：排序算法 / 第六章代码 / 11.Leetcode-148-2.cpp（归并排序链表）

cpp

运行

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:// 获取链表长度int getLength(ListNode *head) {int n = 0;while (head) n += 1, head = head->next;return n;}// 归并排序：对长度为n的链表排序ListNode *merge_sort(ListNode *head, int n) {if (n <= 1) return head;  // 单个节点无需排序int l = n / 2, r = n - l;  // 分割为左右两部分ListNode *p = head, *p1, *p2, ret;// 找到左半部分的尾节点for (int i = 1; i < l; i++) p = p->next;p1 = head; p2 = p->next;  // p1左半部分，p2右半部分p->next = NULL;  // 切断链表p1 = merge_sort(p1, l);  // 递归排序左半部分p2 = merge_sort(p2, r);  // 递归排序右半部分// 合并两个有序链表p = &ret; ret.next = NULL;while (p1 || p2) {if (p2 == NULL || (p1 && p1->val <= p2->val)) {p->next = p1;p = p1;p1 = p1->next;} else {p->next = p2;p = p2;p2 = p2->next;}}return ret.next;}ListNode* sortList(ListNode* head) {int n = getLength(head);return merge_sort(head, n);}
};

解读：
该代码实现链表的归并排序，时间复杂度O(n log n)，空间复杂度O(log n)（递归栈）。步骤为：计算长度→分割链表→递归排序左右两部分→合并有序链表，适合链表的高效排序（避免数组排序的随机访问需求）。

7. 第 7 章：查找算法

文件：7. 第 7 章：查找算法 / 第七章代码 / 6.Leetcode-35.cpp

cpp

运行

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int head = 0, tail = nums.size(), mid;  // 左闭右开区间while (head < tail) {mid = (head + tail) / 2;  // 计算中间位置if (nums[mid] < target) head = mid + 1;  // 目标在右半部分else tail = mid;  // 目标在左半部分（含当前位置）}return head;  // 最终位置为插入点}
};

解读：
该代码通过二分查找在有序数组中寻找目标值的插入位置，时间复杂度O(log n)。采用左闭右开区间[head, tail)，循环结束时head == tail，即为目标位置（存在时为索引，不存在时为插入点）。

文件：7. 第 7 章：查找算法 / 4.Leetcode-01-1.cpp

cpp

运行

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> h;  // 哈希表存储{值:索引}vector<int> ret(2);for (int i = 0, I = nums.size(); i < I; i++) {// 查找目标差值是否存在if (h.find(target - nums[i]) != h.end()) {ret[0] = h[target - nums[i]];  // 之前的索引ret[1] = i;  // 当前索引break;}h[nums[i]] = i;  // 存储当前值和索引}return ret;}
};

解读：
该代码通过哈希表实现两数之和问题，时间复杂度O(n)，空间复杂度O(n)。核心是边遍历边存储，对于每个元素nums[i]，检查target - nums[i]是否已在哈希表中，若存在则返回两个索引。

二、其他重要代码解析

1. 哈夫曼编码相关（第 4、5 章）

文件：4. 第 4 章：树与二叉树 / 第四章代码 / 4.haffman.cpp 与 5. 第 5 章：堆与优先队列 / 第五章代码 / 3.haffman.cpp（相同实现）

cpp

运行

void extractHaffmanCode(Node *root, char buff[], int k) {buff[k] = 0;  // 字符串结束符// 叶子节点：记录编码if (root->lchild == NULL && root->rchild == NULL) {char_code[root->ch] = strdup(buff);  // 复制编码到全局数组return ;}buff[k] = '0';  // 左子树路径为'0'extractHaffmanCode(root->lchild, buff, k + 1);buff[k] = '1';  // 右子树路径为'1'extractHaffmanCode(root->rchild, buff, k + 1);return ;
}

解读：
该代码递归提取哈夫曼树的编码，左子树路径记为'0'，右子树路径记为'1'，到达叶子节点时将编码存入char_code数组。通过buff临时存储路径，strdup复制编码字符串，时间复杂度O(n)（n为树节点数）。

2. 跨语言 OJ 参考代码

文件：Y. 各语言 OJ 提交参考代码 /【java8】路飞吃桃：HZOJ-184.java

java

运行

public class Main{// 递归计算第n天的桃子数int Peach(int n){if(n==1){  // 递归终止条件：第1天剩1个return 1;}// 第n天的桃子数 = 2*(第n-1天桃子数 + 1)return 2*(Peach(n-1)+1);}public static void main(String[] args){Main main = new Main();Scanner sc=new Scanner(System.in);int n = sc.nextInt();  // 读取天数System.out.println(main.Peach(n)+"");  // 输出结果}
}

文件：Y. 各语言 OJ 提交参考代码 /【C++11】路飞吃桃：HZOJ-184.cpp

cpp

运行

int main()
{int i, n, r = 1;  // r初始为第1天的桃子数cin >> n;// 循环从第2天计算到第n天for (i = 1; i < n; i++){r = (r + 1) * 2;  // 递推公式}cout << r << endl;return 0;
}

解读：
两个代码分别用 Java（递归）和 C++（迭代）解决 "路飞吃桃" 问题，核心公式为：第n天桃子数 = 2×(第n-1天桃子数 + 1)。递归实现简洁但可能有栈溢出风险，迭代实现效率更高，时间复杂度均为O(n)。

三、仓库代码整体特点

按算法章节组织：代码按算法类型（递归、链表、树、排序、查找等）分章节存放，结构清晰，便于学习。
聚焦经典问题：覆盖 LeetCode 高频题（如两数之和、合并链表、二叉树重建）和算法基础实现（哈夫曼编码、归并排序、BFS 遍历）。
多语言参考：提供 C++ 和 Java 实现，适配不同 OJ 环境，方便学习者对比参考。
注重效率：多数代码采用最优时间复杂度实现（如哈希表O(n)、二分查找O(log n)、归并排序O(n log n)）。
递归与迭代结合：同一问题提供递归（如路飞吃桃）和迭代（如栈模拟）实现，展示不同解题思路。

通过这些代码，可系统学习数据结构（链表、树、栈、堆）和算法（排序、查找、递归、动态规划）的核心实现与应用。

我要的是该仓库中所有CPP代码文件的提取、注释及解读，内容不需要避免与原代码注释重复

以下是对该仓库中部分 CPP 代码文件的提取、注释及解读：

1. Leetcode-03.cpp（最长无重复字符子串）

cpp

运行

class Solution {
public:// 检查是否存在长度为l的无重复字符子串bool check(string &s, int l) {int cnt[256] = {0}, k = 0; // cnt记录字符出现次数，k记录不同字符数量for (int i = 0; s[i]; i++) {cnt[s[i]] += 1;if (cnt[s[i]] == 1) k += 1; // 新出现的字符，k加1if (i >= l) { // 窗口大小超过l，移除左边界字符cnt[s[i - l]] -= 1;if (cnt[s[i - l]] == 0) k -= 1; // 字符完全移除，k减1}if (l == k) return true; // 存在长度为l的无重复子串}return false;}int lengthOfLongestSubstring(string s) {int head = 0, tail = s.size(), mid; // 二分查找范围// 二分查找最大长度（满足条件的右边界）while (head < tail) {mid = (head + tail + 1) / 2; // 向上取整避免死循环if (check(s, mid)) head = mid; // 存在则尝试更大长度else tail = mid - 1; // 不存在则尝试更小长度}return head;}
};

解读：采用二分查找结合滑动窗口的思路。二分查找可能的最长长度，check函数通过滑动窗口判断是否存在该长度的无重复子串，时间复杂度为 O (n log n)，n 为字符串长度。

2. Leetcode-04.cpp（寻找两个正序数组的中位数）

cpp

运行

class Solution {
public:// 查找两个数组中第k小的元素int findK(vector<int> &n1, int ind1, vector<int> &n2, int ind2, int k) {int n = n1.size(), m = n2.size();if (k == 1) { // 第1小元素，取两者当前起始位置的最小值int a = (n1.size() == ind1 ? INT32_MAX : n1[ind1]);int b = (n2.size() == ind2 ? INT32_MAX : n2[ind2]);return min(a, b);}if (n == ind1) return n2[k - 1]; // n1已空，直接返回n2第k小if (m == ind2) return n1[k - 1]; // n2已空，直接返回n1第k小// 计算每次比较的元素数量int cnt1 = min(k / 2, n - ind1);int cnt2 = min(k - cnt1, m - ind2);cnt1 = k - cnt2;// 比较对应位置元素，排除较小部分if (n1[ind1 + cnt1 - 1] <= n2[ind2 + cnt2 - 1]) {return findK(n1, ind1 + cnt1, n2, ind2, k - cnt1);}return findK(n1, ind1, n2, ind2 + cnt2, k - cnt2);}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size(), m = nums2.size();if ((n + m) % 2 == 1) return findK(nums1, 0, nums2, 0, (n + m) / 2 + 1); // 奇数取中间// 偶数取中间两个的平均值double a = findK(nums1, 0, nums2, 0, (n + m) / 2);double b = findK(nums1, 0, nums2, 0, (n + m) / 2 + 1);return (a + b) / 2.0;}
};

解读：通过递归寻找两个有序数组的第 k 小元素，每次排除掉不可能包含第 k 小元素的部分，时间复杂度为 O (log (m + n))，避免了合并数组的 O (m + n) 复杂度。

3. Leetcode-35.cpp（搜索插入位置）

cpp

运行

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int head = 0, tail = nums.size(), mid; // 左闭右开区间while (head < tail) {mid = (head + tail) / 2;if (nums[mid] < target) head = mid + 1; // 目标在右侧else tail = mid; // 目标在左侧或当前位置}return head; // 最终位置为插入位置}
};

解读：标准的二分查找应用，寻找目标值在有序数组中的插入位置，时间复杂度 O (log n)。

4. Leetcode-349.cpp（两个数组的交集）

cpp

运行

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> h; // 存储nums1中的元素vector<int> ret; // 结果集for (auto x : nums1) h.insert(x); // 去重存储nums1for (auto x : nums2) {if (h.find(x) == h.end()) continue; // 不在nums1中则跳过ret.push_back(x); // 加入结果h.erase(h.find(x)); // 避免重复加入}return ret;}
};

解读：利用哈希集合去重和快速查找的特性，先存储第一个数组的元素，再遍历第二个数组寻找交集元素，时间复杂度 O (m + n)。

5. Leetcode-01-1.cpp（两数之和）

cpp

运行

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> h; // 存储数值到索引的映射vector<int> ret(2);for (int i = 0, I = nums.size(); i < I; i++) {// 查找是否存在目标补数if (h.find(target - nums[i]) != h.end()) {ret[0] = h[target - nums[i]];ret[1] = i;break;}h[nums[i]] = i; // 存储当前元素和索引}return ret;}
};

解读：通过哈希表记录已遍历元素，单次遍历即可找到满足条件的两个数，时间复杂度 O (n)，空间复杂度 O (n)。

6. Leetcode-23.cpp（合并 K 个升序链表）

cpp

运行

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {typedef pair<int, int> PII; // 存储节点值和对应链表索引int n = lists.size();set<PII> s; // 有序集合，自动按值排序// 初始化，将每个链表的头节点加入集合for (int i = 0; i < n; i++) {if (lists[i] == nullptr) continue;s.insert(PII(lists[i]->val, i));}ListNode new_head, *p = &new_head, *q; // 虚拟头节点new_head.next = nullptr;while (s.size()) {PII a = *s.begin(); // 取最小值节点s.erase(s.begin());q = lists[a.second]; // 获取对应节点lists[a.second] = lists[a.second]->next; // 链表指针后移p->next = q; // 加入结果链表q->next = nullptr;p = q;// 若该链表还有节点，继续加入集合if (lists[a.second]) {s.insert(PII(lists[a.second]->val, a.second));}}return new_head.next;}
};

解读：利用有序集合（类似优先队列）维护各链表当前最小节点，每次取出最小值并将后续节点加入集合，时间复杂度 O (N log k)，N 为总节点数，k 为链表数量。

7. Leetcode-21.cpp（合并两个有序链表）

cpp

运行

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode ret, *p = &ret; // 虚拟头节点while (list1 || list2) {// 选择较小的节点加入结果if (list2 == NULL || (list1 && list1->val <= list2->val)) {p->next = list1;list1 = list1->next;} else {p->next = list2;list2 = list2->next;}p = p->next;}return ret.next;}
};

解读：双指针法合并两个有序链表，通过虚拟头节点简化边界处理，时间复杂度 O (m + n)。

8. Leetcode-88.cpp（合并两个有序数组）

cpp

运行

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int p1 = m - 1, p2 = n - 1, k = m + n - 1; // 从后往前合并while (p1 != -1 || p2 != -1) {// 选择较大的元素放在后面if (p2 == -1 || (p1 != -1 && nums1[p1] >= nums2[p2])) {nums1[k--] = nums1[p1--];} else {nums1[k--] = nums2[p2--];}}return ;}
};

解读：利用 nums1 的额外空间，从后往前合并两个有序数组，避免覆盖未处理元素，时间复杂度 O (m + n)。

9. Leetcode-217.cpp（存在重复元素）

cpp

运行

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> h; // 哈希集合存储已出现元素for (auto x : nums) {if (h.find(x) != h.end()) return true; // 找到重复元素h.insert(x);}return false;}
};

解读：通过哈希集合判断元素是否重复出现，时间复杂度 O (n)，空间复杂度 O (n)。

10. 堆与优先队列相关：Leetcode-703.cpp（数据流中的第 K 大元素）

cpp

运行

class KthLargest {
public:typedef pair<int, int> PII;int tot, k;set<PII> s; // 有序集合维护前k大元素（按值升序）KthLargest(int k, vector<int>& nums) {this->k = k;for (auto x : nums) {add(x); // 初始化添加元素}return ;}int add(int val) {if (s.size() < k) { // 元素不足k个，直接加入s.insert(PII(val, tot++));} else {if (s.begin()->first < val) { // 新元素更大，替换最小元素s.insert(PII(val, tot++));}}if (s.size() > k) s.erase(s.begin()); // 保持集合大小为kreturn s.begin()->first; // 第k大元素为集合最小值}
};

解读：用有序集合维护数据流中最大的 k 个元素，每次添加元素后保持集合大小为 k，集合最小值即为第 k 大元素，add 操作时间复杂度 O (log k)。

以上代码涵盖了查找、排序、哈希表、链表、堆等常见数据结构与算法的应用，注释和解读已尽量详细，可结合具体问题场景理解其设计思路。

我要的是该仓库中所有CPP代码文件的提取、注释及解读，内容不需要避免与原代码注释重复，请你牢记我的要求

以下是该仓库中更多 CPP 代码文件的提取、注释及解读（补充之前未涵盖的内容）：

1. HZOJ-237.cpp（全排列问题）

cpp

运行

/*************************************************************************> File Name: 5.HZOJ-237.cpp> Author: huguang> Mail: hug@haizeix.com> Created Time: ************************************************************************/#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;int arr[10], vis[10] = {0}; // arr存储当前排列，vis标记数字是否使用// 打印当前排列结果
void print_one_result(int n) {for (int i = 0; i < n; i++) {if (i) cout << " "; // 非首个元素前加空格cout << arr[i];}cout << endl;return ;
}// 递归生成全排列：i为当前填充位置，n为排列长度
void f(int i, int n) {if (i == n) { // 填充完所有位置，打印结果print_one_result(n);return ;}// 尝试放置1到n的每个数字for (int k = 1; k <= n; k++) {if (vis[k]) continue; // 数字已使用，跳过arr[i] = k; // 放置数字kvis[k] = 1; // 标记为已使用f(i + 1, n); // 递归填充下一个位置vis[k] = 0; // 回溯：恢复未使用状态}return ;
}int main() {int n;cin >> n; // 输入排列长度f(0, n); // 从第0个位置开始生成排列return 0;
}

解读：通过递归 + 回溯实现全排列生成。vis数组标记数字是否已使用，f(i, n)函数负责填充第i个位置，当i == n时输出完整排列。回溯过程通过恢复vis数组状态实现，时间复杂度 O (n!)。

2. Leetcode-148-2.cpp（链表排序：归并排序）

cpp

运行

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:// 获取链表长度int getLength(ListNode *head) {int n = 0;while (head) n += 1, head = head->next;return n;}// 归并排序链表：head为头节点，n为链表长度ListNode *merge_sort(ListNode *head, int n) {if (n <= 1) return head; // 长度为1或0时直接返回（递归终止）int l = n / 2, r = n - l; // 分为左右两部分，长度分别为l和rListNode *p = head, *p1, *p2, ret; // p1为左半部分头，p2为右半部分头// 找到左半部分的尾节点，分割链表for (int i = 1; i < l; i++) p = p->next;p1 = head; p2 = p->next;p->next = NULL; // 断开左半部分与右半部分的连接// 递归排序左右两部分p1 = merge_sort(p1, l);p2 = merge_sort(p2, r);// 合并两个有序链表p = &ret; ret.next = NULL; // 虚拟头节点简化合并while (p1 || p2) {if (p2 == NULL || (p1 && p1->val <= p2->val)) {p->next = p1;p = p1;p1 = p1->next;} else {p->next = p2;p = p2;p2 = p2->next;}}return ret.next;}// 主函数：对链表排序ListNode* sortList(ListNode* head) {int n = getLength(head); // 计算长度return merge_sort(head, n); // 调用归并排序}
};

解读：采用归并排序对链表进行排序，时间复杂度 O (n log n)。步骤包括：计算链表长度→分割为左右两部分→递归排序→合并有序链表。通过虚拟头节点简化合并操作，避免处理空指针的复杂逻辑。

3. Leetcode-219.cpp（存在重复元素 II）

cpp

运行

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {int n = nums.size();vector<int> ind(n); // 存储原数组索引// 初始化索引数组for (int i = 0; i < n; i++) ind[i] = i;// 按数值排序，数值相同则按索引排序sort(ind.begin(), ind.end(), [&](int i, int j) -> bool {if (nums[i] != nums[j]) return nums[i] < nums[j];return i < j;});// 检查相邻相同元素的索引差是否≤kfor (int i = 0, I = n - 1; i < I; i++) {if (nums[ind[i]] - nums[ind[i + 1]]) continue; // 数值不同，跳过if (ind[i + 1] - ind[i] <= k) return true; // 找到符合条件的重复元素}return false;}
};

解读：通过排序索引数组实现。先按数值对索引排序，相同数值的索引会相邻，再检查相邻索引的差值是否≤k。时间复杂度 O (n log n)（排序耗时），空间复杂度 O (n)。

4. Leetcode-844.cpp（比较含退格的字符串）

cpp

运行

class Solution {
public:// 将字符串处理后压入栈：遇到'#'弹出栈顶，否则压入字符void pushStack(string &s, stack<char> &s1) {for (int i = 0; s[i]; i++) {if (s[i] == '#') { if (!s1.empty()) s1.pop(); // 栈非空时弹出} else s1.push(s[i]); // 压入普通字符}return ;}// 比较两个处理后的字符串是否相等bool backspaceCompare(string s, string t) {stack<char> s1, s2;pushStack(s, s1); // 处理spushStack(t, s2); // 处理tif (s1.size() != s2.size()) return false; // 长度不同直接不等// 逐个比较栈顶元素while (!s1.empty()) {if (s1.top() != s2.top()) return false;s1.pop(), s2.pop();}return true;}
};

解读：利用栈处理退格逻辑。对两个字符串分别处理（'#' 表示删除前一个字符），最后比较处理后的栈是否完全相同。时间复杂度 O (n + m)，空间复杂度 O (n + m)（n 和 m 为两字符串长度）。

5. Leetcode-01.cpp（两数之和：排序 + 双指针）

cpp

运行

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();vector<int> ind(n); // 存储原数组索引// 初始化索引数组for (int i = 0; i < n; i++) ind[i] = i;// 按数值排序索引sort(ind.begin(), ind.end(), [&](int i, int j) -> bool {return nums[i] < nums[j];});// 双指针查找目标和int p1 = 0, p2 = n - 1;while (nums[ind[p1]] + nums[ind[p2]] != target) {if (nums[ind[p1]] + nums[ind[p2]] < target) p1 += 1; // 和偏小，左指针右移else p2 -= 1; // 和偏大，右指针左移}// 整理结果（确保索引顺序）vector<int> ret(2);ret[0] = ind[p1], ret[1] = ind[p2];if (ret[0] > ret[1]) swap(ret[0], ret[1]);return ret;}
};

解读：通过排序 + 双指针实现两数之和。先对索引按数值排序，再用双指针从两端向中间查找和为target的元素。时间复杂度 O (n log n)（排序耗时），空间复杂度 O (n)。

6. Leetcode-148-1.cpp（链表排序：快速排序）

cpp

运行

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if (head == NULL) return head; // 空链表直接返回// 确定分区基准（取当前链表最大值和最小值的中间值）int l = head->val, r = head->val, z;ListNode *p = head, *h1 = NULL, *h2 = NULL, *q;while (p) {l = min(p->val, l); // 更新最小值r = max(p->val, r); // 更新最大值p = p->next;}z = (l + r) >> 1; // 基准值（中间值）if (l == r) return head; // 所有元素相同，直接返回// 分区：小于等于z的放h1，大于z的放h2p = head;while (p) {q = p->next; // 暂存下一个节点if (p->val <= z) {p->next = h1; // 插入h1头部h1 = p;} else {p->next = h2; // 插入h2头部h2 = p;}p = q;}// 递归排序左右两部分h1 = sortList(h1);h2 = sortList(h2);// 合并排序后的链表p = h1;while (p->next) p = p->next; // 找到h1的尾节点p->next = h2; // 连接h1和h2return h1;}
};

解读：采用快速排序思想对链表排序。步骤为：确定基准值→分区（小于等于基准的放左链表，大于的放右链表）→递归排序→合并。时间复杂度平均 O (n log n)，最坏 O (n²)，空间复杂度 O (log n)（递归栈）。

7. HZOJ-186.cpp（跳跃游戏步数）

cpp

运行

/*************************************************************************> File Name: 2.HZOJ-186.cpp> Author: huguang> Mail: hug@haizeix.com> Created Time: ************************************************************************/#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;// 递归计算从位置i跳到终点的最少步数
int f(int i, vector<int> &arr, int n) {if (i >= n) return 0; // 已到达或超过终点，步数为0// 从i跳arr[i]步到i+arr[i]，步数+1return f(i + arr[i], arr, n) + 1;
}int main() {int n;vector<int> arr;cin >> n;for (int i = 0, a; i < n; i++) {cin >> a;arr.push_back(a); // 存储每步可跳的距离}cout << f(0, arr, n) << endl; // 从位置0开始跳return 0;
}

解读：递归求解跳跃游戏的最少步数。每次从当前位置i跳arr[i]步，直到超过终点，累加步数。时间复杂度 O (n)（每个位置只访问一次），空间复杂度 O (n)（递归栈深度）。

8. Leetcode-01-2.cpp（两数之和：排序 + 二分查找）

cpp

运行

class Solution {
public:// 二分查找：在ind[b..n-1]中找数值为x的索引int binary_search(vector<int> &nums, vector<int> &ind, int b, int x) {int head = b, tail = nums.size() - 1, mid;while (head <= tail) {mid = (head + tail) / 2;if (nums[ind[mid]] == x) return mid; // 找到目标if (nums[ind[mid]] < x) head = mid + 1; // 目标在右侧else tail = mid - 1; // 目标在左侧}return -1; // 未找到}vector<int> twoSum(vector<int>& nums, int target) {int n = nums.size();vector<int> ind(n, 0); // 存储原索引// 按数值排序索引for (int i = 0; i < n; i++) ind[i] = i;sort(ind.begin(), ind.end(), [&](int i, int j) -> bool {return nums[i] < nums[j];});vector<int> ret(2);// 遍历每个元素，二分查找互补元素for (int i = 0; i < n; i++) {int j = binary_search(nums, ind, i + 1, target - nums[ind[i]]);if (j == -1) continue; // 未找到互补元素ret[0] = ind[j];ret[1] = ind[i];}// 确保索引顺序if (ret[0] > ret[1]) swap(ret[0], ret[1]);return ret;}
};

解读：结合排序和二分查找实现两数之和。先对索引排序，再遍历每个元素，通过二分查找其互补元素（target - 当前值）。时间复杂度 O (n log n)（排序 + 二分查找），空间复杂度 O (n)。

9. HZOJ-287.cpp（哈夫曼编码最小代价）

cpp

运行

/*************************************************************************> File Name: 15.HZOJ-287.cpp> Author: huguang> Mail: hug@haizeix.com> Created Time: ************************************************************************/#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
using namespace std;typedef pair<int, int> PII; // 存储数值和索引（避免重复元素冲突）int main() {int n;set<PII> s; // 有序集合模拟最小堆（自动按first升序）cin >> n;for (int i = 0, a; i < n; i++) {cin >> a;s.insert(PII(a, i)); // 插入初始元素}int ans = 0; // 总代价// 合并n-1次（n个元素最终合并为1个）for (int i = 1; i < n; i++) {int a = s.begin()->first; // 取最小元素s.erase(s.begin());int b = s.begin()->first; // 取次小元素s.erase(s.begin());ans += a + b; // 累加合并代价s.insert(PII(a + b, n + i)); // 插入合并后的新元素}cout << ans << endl; // 输出总代价return 0;
}

解读：模拟哈夫曼编码的构建过程，计算最小合并代价。通过有序集合（set）维护最小元素，每次取出两个最小元素合并，累加代价并插入新元素，重复 n-1 次。时间复杂度 O (n log n)（每次插入 / 删除操作 O (log n)）。

10. HZOJ-239.cpp（分形图案坐标计算）

cpp

运行

/*************************************************************************> File Name: 6.HZOJ-239.cpp> Author: huguang> Mail: hug@haizeix.com> Created Time: ************************************************************************/#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <cmath>
using namespace std;#define S(a) ((a) * (a)) // 平方宏定义// 递归计算第s个点在n阶分形中的坐标(x,y)
void f(long long n, long long s, long long &x, long long &y) {if (n == 1) { // 1阶分形（2x2网格）if (s == 1) x = 0, y = 0;else if (s == 2) x = 0, y = 1;else if (s == 3) x = 1, y = 1;else x = 1, y = 0;return ;}long long L = 1LL << (n - 1); // 当前阶的半边长（2^(n-1)）long long block = L * L; // 每个子块的点数long long xx, yy;if (s <= block) { // 第1个子块：坐标变换(x,y)→(y,x)f(n - 1, s, xx, yy);x = yy, y = xx;} else if (s <= 2 * block) { // 第2个子块：坐标变换(x,y)→(x, y+L)f(n - 1, s - block, xx, yy);x = xx, y = yy + L;} else if (s <= 3 * block) { // 第3个子块：坐标变换(x,y)→(x+L, y+L)f(n - 1, s - 2 * block, xx, yy);x = xx + L, y = yy + L;} else { // 第4个子块：坐标变换(x,y)→(2L - y -1, L - x -1)f(n - 1, s - 3 * block, xx, yy);x = 2 * L - yy - 1, y = L - xx - 1;}return ;
}int main() {long long t, n, s, d;scanf("%lld", &t);while (t--) {scanf("%lld%lld%lld", &n, &s, &d);long long sx, sy, dx, dy;f(n, s, sx, sy); // 计算s点坐标f(n, d, dx, dy); // 计算d点坐标// 计算两点距离（放大10倍输出）printf("%.0lf\n", 10 * sqrt(S(sx - dx) + S(sy - dy)));}return 0;
}

解读：递归计算分形图案中两点的坐标并求距离。n 阶分形由 4 个 n-1 阶分形组成，通过坐标变换规则递归求解每个点的位置，最终计算欧氏距离。时间复杂度 O (n)（递归深度为 n）。

这些代码覆盖了递归、排序、查找、链表操作、堆 / 集合应用等多种算法场景，注释和解读已结合具体逻辑和复杂度分析，便于理解实现思路。

查看全文

http://www.xdnf.cn/news/19533.html