算法总结
一句话总结
数据结构的本质是数组和链表的变换；算法的本质是穷举，关键是"无遗漏、无冗余"。
核心思想
一、数据结构的本质
所有数据结构皆为数组（顺序存储）和链表（链式存储）的变换。
1.1 存储方式只有两种
| 数据结构 | 底层实现 | 特点 |
|---|---|---|
| 队列、栈 | 数组或链表 | 数组实现需处理扩容缩容；链表实现无需扩容但多内存开销 |
| 图 | 邻接表（链表）或邻接矩阵（二维数组） | 邻接矩阵判断连通性快但耗费空间；邻接表节省空间 |
| 哈希表 | 大数组 + 散列函数 | 拉链法需链表特性；线性探查法需数组特性 |
| 树 | 数组（堆）或链表（二叉搜索树等） | 完全二叉树适合数组；普通树适合链表 |
1.2 基本操作只有两种
所有数据结构的基本操作 = 遍历 + 访问（增删查改）
遍历方式只有两种：
- 线性：for/while 迭代
- 非线性：递归
1.3 数组 vs 链表
| 特性 | 数组 | 链表 |
|---|---|---|
| 存储方式 | 连续存储 | 不连续，靠指针连接 |
| 随机访问 | O(1) | 不支持 |
| 扩容 | 需重新分配 + 复制 O(N) | 无此问题 |
| 插入/删除中间 | O(N) 需搬移 | O(1) 已知前后驱时 |
| 存储空间 | 较节省 | 需额外指针空间 |
二、算法的本质
算法的本质 = 穷举
2.1 穷举的两个关键
| 关键 | 问题 | 原因 |
|---|---|---|
| 无遗漏 | 遗漏导致答案错误 | 对算法框架掌握不到位 |
| 无冗余 | 重复计算拖慢速度 | 没有充分利用信息 |
2.2 如何穷举？
难点在"如何穷举"的算法：回溯算法、动态规划
- 回溯算法："遍历"的思维，抽象成树结构，用代码遍历树的所有节点
- 动态规划："分解问题"的思维，把问题分解为子问题，利用数学归纳法找状态转移方程
2.3 如何聪明地穷举？
难点在"如何聪明地穷举"的算法：二分搜索、滑动窗口、并查集、贪心算法
- 二分搜索：有序数组中用 O(logN) 时间搜索，而非 O(N) 暴力遍历
- 滑动窗口：用快慢双指针在 O(N) 时间内找到子数组答案，而非 O(N²)
- 并查集：用数组模拟树结构，将连通性操作优化到 O(1)
- 贪心算法：利用贪心选择性质，不用完整穷举所有解
代码框架模板
一、数据结构遍历框架
1.1 数组遍历（线性迭代）
void traverse(int[] arr) {
for (int i = 0; i < arr.length; i++) {
// 迭代访问 arr[i]
}
}
1.2 链表遍历（迭代 + 递归）
// 基本的单链表节点
class ListNode {
int val;
ListNode next;
}
// 迭代遍历
void traverse(ListNode head) {
for (ListNode p = head; p != null; p = p.next) {
// 迭代访问 p.val
}
}
// 递归遍历
void traverse(ListNode head) {
if (head == null) return;
// 递归访问 head.val
traverse(head.next);
}
1.3 二叉树遍历（递归框架）
// 基本的二叉树节点
class TreeNode {
int val;
TreeNode left, right;
}
// 二叉树递归遍历框架
void traverse(TreeNode root) {
if (root == null) return;
// 前序位置
traverse(root.left);
// 中序位置
traverse(root.right);
// 后序位置
}
1.4 N 叉树遍历
// 基本的 N 叉树节点
class TreeNode {
int val;
TreeNode[] children;
}
void traverse(TreeNode root) {
if (root == null) return;
for (TreeNode child : root.children) {
traverse(child);
}
}
1.5 图遍历（DFS/BFS）
// DFS 遍历（递归）
boolean[] visited;
void dfs(int node, List<Integer>[] graph) {
if (visited[node]) return;
visited[node] = true;
for (int neighbor : graph[node]) {
dfs(neighbor, graph);
}
}
// BFS 遍历（队列）
void bfs(int start, List<Integer>[] graph) {
boolean[] visited = new boolean[graph.length];
Queue<Integer> q = new LinkedList<>();
q.offer(start);
visited[start] = true;
while (!q.isEmpty()) {
int cur = q.poll();
for (int neighbor : graph[cur]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.offer(neighbor);
}
}
}
}
二、算法框架
2.1 回溯算法框架（遍历思维）
class Solution {
List<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> track = new LinkedList<>();
boolean[] used;
List<List<Integer>> permute(int[] nums) {
used = new boolean[nums.length];
backtrack(nums);
return res;
}
void backtrack(int[] nums) {
// 到达叶子节点，收集结果
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
// 做选择
track.add(nums[i]);
used[i] = true;
// 进入下一层递归
backtrack(nums);
// 撤销选择
track.removeLast();
used[i] = false;
}
}
}
核心：回溯 = 多叉树遍历，把问题抽象成树结构，遍历所有叶子节点。
2.2 动态规划框架（分解问题思维）
// 定义：dp(coins, amount) 表示凑出 amount 所需的最少硬币数
int dp(int[] coins, int amount) {
// base case
if (amount == 0) return 0;
if (amount < 0) return -1;
int res = Integer.MAX_VALUE;
for (int coin : coins) {
int subProblem = dp(coins, amount - coin);
if (subProblem == -1) continue;
res = Math.min(res, subProblem + 1);
}
return res == Integer.MAX_VALUE ? -1 : res;
}
// 加备忘录优化（自顶向下）
int dp(int[] coins, int amount, Map<Integer, Integer> memo) {
if (amount == 0) return 0;
if (amount < 0) return -1;
if (memo.containsKey(amount)) return memo.get(amount);
int res = Integer.MAX_VALUE;
for (int coin : coins) {
int subProblem = dp(coins, amount - coin, memo);
if (subProblem == -1) continue;
res = Math.min(res, subProblem + 1);
}
res = res == Integer.MAX_VALUE ? -1 : res;
memo.put(amount, res);
return res;
}
核心：动态规划 = 分解问题，明确函数定义，用数学归纳法找状态转移方程。
2.3 BFS 算法框架（层序遍历）
// 层序遍历二叉树（也是 BFS 基础框架）
void levelTraverse(TreeNode root) {
if (root == null) return;
Queue<TreeNode> q = new LinkedList<>();
q.offer(root);
int depth = 0;
while (!q.isEmpty()) {
int sz = q.size(); // 关键：必须在循环前保存队列长度
for (int i = 0; i < sz; i++) {
TreeNode cur = q.poll();
// 访问 cur 节点
if (cur.left != null) q.offer(cur.left);
if (cur.right != null) q.offer(cur.right);
}
depth++;
}
}
核心：BFS = 层序遍历，用队列按层级扩散，适合求最短路径。
2.4 滑动窗口框架
void slidingWindow(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 增大窗口：更新窗口数据
window.put(c, window.getOrDefault(c, 0) + 1);
while (windowNeedsShrink()) { // 窗口需要收缩的条件
char d = s.charAt(left);
left++;
// 缩小窗口：更新窗口数据
window.put(d, window.get(d) - 1);
}
}
}
2.5 二分搜索框架
int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
}
}
return -1;
}
总结
- 数据结构：数组 + 链表 → 所有数据结构都是它们的变换
- 算法：穷举 → 如何无遗漏？如何无冗余？
- 框架思维：所有算法都有固定框架，套用框架 + 填充细节
- 两种思维模式：
- 遍历思维（回溯算法）：遍历树的所有节点
- 分解问题思维（动态规划）：把问题分解为子问题