（三）数据结构与算法——经典算法

🗂️ 一、 哈希表：O(1) 神话的缔造者与冲突解决

1. 哈希表的原理是什么？

哈希表（Hash Table）是一种通过哈希函数把键（key）映射到数组下标，从而在平均 O(1) 时间内完成查找、插入、删除的数据结构。
核心原理四步走：

2. 哈希冲突怎么解决？

不同的 key 经过哈希函数后可能映射到同一个下标，这就是哈希冲突，无法完全避免。主要有两大解决方案：

• 链地址法（拉链法）：每个桶里挂一个链表（或红黑树），冲突的元素都挂在对应桶的链表上。Java HashMap 和 Redis 的 dict 都用这种方式。注意点：JDK 1.8 之后，当某个桶的链表长度 ≥ 8 且数组长度 ≥ 64 时，链表会转成红黑树，进一步优化最坏情况下的查找。

• 开放寻址法：冲突时按一定规则在数组里寻找下一个空位。常见探测方式有线性探测（i, i+1, i+2…）、二次探测（i, i+1², i+2²…）、双重哈希。Java 的 ThreadLocalMap 就是用线性探测。

3. 负载因子（Load Factor）

• 公式：元素数量 / 桶数量。

• 负载因子越大冲突越多。Java HashMap 默认 0.75，超过就触发扩容（rehash），以维持平均 O(1) 的查找性能。

🧩 二、 归并排序：分治思想的完美体现

1. 原理与实现

归并排序是一种典型的分治算法，思想非常清晰，就是“分、治、合”三步：

2. 复杂度与特性

• 时间复杂度：最好、最坏、平均都是 O(n log n)（共 log n 层递归，每层合并总共处理 n 个元素）。

• 空间复杂度：O(n)（需要额外的临时数组存放合并结果）。

• 稳定性：稳定排序，合并时相同元素按原始顺序放入。

3. 对比快排与应用场景

• 相比快排的优势：稳定、最坏情况也是 O(n log n)（快排最坏是 O(n²)）。

• 相比快排的劣势：需要 O(n) 额外空间，不是原地排序。

• 典型应用场景：

  • 外部排序（内存放不下的海量数据）。

  • 链表排序（对链表非常友好，空间可以做到 O(1)）。

  • 需要稳定性的业务场景。

#include <iostream>
#include <vector>

// 合并两个有序子数组
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> temp(right – left + 1);
int i = left, j = mid + 1, k = 0;

while (i <= mid && j <= right) {
// 注意：这里用 <= 保证稳定性
if (arr[i] <= arr[j]) {
temp[k++] = arr[i++];
} else {
temp[k++] = arr[j++];
}
}
while (i <= mid) temp[k++] = arr[i++];
while (j <= right) temp[k++] = arr[j++];

// 将临时数组拷贝回原数组
for (int p = 0; p < k; ++p) {
arr[left + p] = temp[p];
}
}

void mergeSort(vector<int>& arr, int left, int right) {
if (left >= right) return;
int mid = left + (right – left) / 2;
mergeSort(arr, left, mid); // 递归排序左半
mergeSort(arr, mid + 1, right); // 递归排序右半
merge(arr, left, mid, right); // 合并
}

 三、 二分查找：思路很简单，细节是魔鬼

1. 核心思想与标准实现

二分查找是对有序数组进行查找的经典算法，时间复杂度 O(log n)。核心思想是每次比较中间元素，根据大小关系把查找范围缩小一半。

2. 容易踩的坑

#include <vector>

int binarySearch(const vector<int>& arr, int target) {
int left = 0, right = arr.size() – 1;

// 闭区间 [left, right]
while (left <= right) {
// 防溢出写法，面试必考！
int mid = left + (right – left) / 2;

if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1; // 更新左边界
} else {
right = mid – 1; // 更新右边界
}
}
return -1; // 未找到
}

四、 DFS 与 BFS：图/树遍历的双子星

1. 区别与实现

• DFS（深度优先）：一条路走到黑，走不通再回溯。通常用递归或栈实现。

• BFS（广度优先）：一层一层向外扩展。通常用队列实现。

2. 对比表格

3. 经典题举例

• 二叉树前/中/后序遍历 → DFS

• 二叉树层序遍历 → BFS

• LeetCode 200 岛屿数量 → DFS/BFS 都行

• LeetCode 994 腐烂的橘子（求最短感染时间） → BFS

• 回溯类题目（全排列、N 皇后、子集、组合） → DFS

💡 一句话区别：要找最短路径、最少步数用 BFS；要穷举所有方案或深挖某条路径用 DFS。

五、 链表手撕：反转链表与环形链表

1. 如何反转一个链表？

这是链表手撕题里最经典的一道，要会两种解法。

• 解法一：迭代（推荐，O(1) 空间）
  用三个指针 prev、curr、next 依次调转每个节点的指向。
  时间复杂度 O(n)，空间复杂度 O(1)。

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* nextTemp = curr->next; // 暂存下一个节点
curr->next = prev; // 反转当前节点指针
prev = curr; // prev 前进
curr = nextTemp; // curr 前进
}
return prev; // 最后 prev 就是新的头节点
}

• 解法二：递归
  递归到最后一个节点作为新头节点，然后在回溯的过程中改变指针指向。
  时间复杂度 O(n)，但递归栈占用 O(n) 空间。
  ⚠️一定要考虑空链表（head == null）和只有一个节点的边界情况，上面两种写法都已经处理了。

ListNode* reverseListRecursive(ListNode* head) {
// 边界情况：空链表或只有一个节点
if (head == nullptr || head->next == nullptr) return head;

ListNode* newHead = reverseListRecursive(head->next);
head->next->next = head; // 让下一个节点的 next 指向当前节点
head->next = nullptr; // 当前节点的 next 设为 null，避免成环
return newHead;
}

2. 如何判断一个链表是否有环？如何找到环的入口节点？

这是快慢指针（Floyd 判圈算法）的经典应用题，两问都有标准答案。

• 第一问：判断有没有环
  用两个指针 slow 和 fast，slow 每次走 1 步，fast 每次走 2 步。
  如果 fast 走到了 null，说明没有环；如果 fast 追上了 slow（相遇），说明有环。

• 第二问：找环的入口节点
  关键结论（Floyd 算法的数学推导）：在 slow 和 fast 相遇后，让其中一个指针回到链表头，两个指针都每次走一步，再次相遇的地方就是环的入口。
  数学原理：设头到入口距离为 a，入口到相遇点为 b，相遇点到入口（沿环走）为 c。相遇时 slow = a + b，fast = a + b + k(b + c)（多跑了 k 圈）。由 fast = 2 * slow 推出 a = (k – 1)(b + c) + c，含义就是：从头走 a 步，等价于从相遇点走 c 步再走若干整圈，两者一定会同时到达入口。

ListNode* detectCycle(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;

while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;

if (slow == fast) { // 相遇，开始找入口
ListNode* p = head;
while (p != slow) {
p = p->next;
slow = slow->next;
}
return p; // 再次相遇的地方就是环的入口
}
}
return nullptr; // 无环
}

 六、 二叉树遍历：四种方式一网打尽

二叉树遍历分两大类：DFS 三种 和 BFS 一种，一共四种，都是超高频考点。

1. DFS 三种（根据根节点被访问的顺序区分）

• 前序遍历：根 → 左 → 右

• 中序遍历：左 → 根 → 右（二叉搜索树的中序遍历结果是升序的）

• 后序遍历：左 → 右 → 根

递归实现（以中序为例）：代码非常简洁，牢记“左、根、右”的顺序递归调用即可。迭代实现需要显式用栈。

#include <stack>

vector<int> inorderTraversal(TreeNode* root) {
vector<int> result;
stack<TreeNode*> stk;
TreeNode* curr = root;

while (curr != nullptr || !stk.empty()) {
// 一路向左，把左节点全部压栈
while (curr != nullptr) {
stk.push(curr);
curr = curr->left;
}
// 弹出栈顶（最左节点）并访问
curr = stk.top();
stk.pop();
result.push_back(curr->val);
// 转向右子树
curr = curr->right;
}
return result;
}

2. BFS 一种：层序遍历（Level Order）

用队列实现，一层一层访问。
核心技巧是在每一层开始前，记录当前队列的大小 size，然后用一个循环把当前层的节点全部处理完，并将其子节点加入队列。这样就能完美分层输出。

#include <queue>

vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) return result;

queue<TreeNode*> q;
q.push(root);

while (!q.empty()) {
int size = q.size(); // 记录当前层的节点数
vector<int> level;

for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
level.push_back(node->val);

if (node->left) q.push(node->left);
if (node->right) q.push(node->right);
}
result.push_back(level);
}
return result;
}

 七、什么是动态规划（DP）？

动态规划（Dynamic Programming）是一种把大问题拆解为重叠子问题、通过记录子问题的解来避免重复计算的算法思想。它本质上是“聪明的暴力枚举”。

一个问题是能否用DP，通常看两个特征：

💡 掌握DP的解题套路（核心四步曲）：

• 定义状态：dp[i] 或 dp[i][j] 到底表示什么？

• 状态转移方程：dp[i] 如何从之前的状态推导出来？

• 初始化：边界状态如何赋值？

• 遍历顺序：是从前往后、从后往前，还是按某种维度？

🔥 进阶技巧（必备）：
先想暴力递归 -> 发现重叠子问题 -> 用数组/哈希表做记忆化搜索 -> 改写成自底向上的迭代DP -> 最后用滚动数组优化空间。掌握这套流程，80%的DP题都能套！

💻 实战：斐波那契（滚动数组空间优化）

以最基础的爬楼梯为例，状态转移方程 dp[i] = dp[i-1] + dp[i-2]。为了节省空间，我们不用存整个数组，只用两个变量。

int climbStairs(int n) {
if (n <= 2) return n;
int prev2 = 1; // dp[1]
int prev1 = 2; // dp[2]
int current = 0;
for (int i = 3; i <= n; ++i) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}

典型题目图谱： 0-1背包、完全背包（零钱兑换）、最长公共子序列（LCS）、最长递增子序列（LIS）、最长回文子串、编辑距离、打家劫舍

贪心算法和动态规划有什么区别？

两者都用于求最优解问题，但核心区别在于做决策时是否回头看。

典型贪心题：

• 找零钱（面值 1/5/10/25）：每次尽量用大面额。

• 区间调度（活动选择）：按结束时间排序，依次选能加入的活动。

• 霍夫曼编码：每次合并频率最小的两个节点。

• 跳跃游戏：每一步都跳到“能到达的最远位置”。

贪心是“每一步都走当前看起来最好的”，DP是“把所有可能性都算过再选最好的”。贪心更快但不一定正确，DP一定正确但更慢。