面试算法题全军覆没后 程序员总结的Java算法学习路径 从零到offer的资源清单
说实话，第一次去面大厂的时候，我连快排手写都卡壳了。面试官轻轻一句话”说说快排的思路”，我脑子里一片空白，手心全是汗。那天出来之后，我在地铁上坐过了三站，心想：完了，这条路是不是走不通了？
但后来想想，算法这东西，真不是智商问题，就是缺一套系统的方法。今天我想把这条路上踩过的坑、摸到的门道，还有那些真正有用的资源，全部掏出来给你看。
一、为什么大多数人算法学不好
先别急着翻书，我想让你先停下来想一想自己卡在哪一步。
很多人的问题出在学习顺序错了。
一上来就刷LeetCode硬刚，遇到不会的就看题解，看完觉得自己懂了，第二天再遇到还是不会。这个循环重复了无数次，最后就是”刷了500题，面试还是不会”。
还有一个常见问题：数据结构基础不牢。栈、队列、链表、树这些基本概念都没搞清楚，就去学动态规划，那不是舍本逐末吗？
我见过太多人了，包括曾经的自己，学算法是”碎片化”的，今天看一个排序，明天看一个二叉树，后天又来一个哈希表，脑子里没有一张清晰的地图。你问”算法到底要学什么”，别人也说不清楚。
所以第一件事，是建立知识体系。
二、算法学习的核心地图
我先给你一张全景图，让你知道我们往哪个方向走。
算法学习路径总览
┌─────────────────────────────────────────────────────────┐
│ 阶段一：基础夯实 │
│ · 时间复杂度分析 │
│ · Java基础语法回顾 │
│ · 基本数据结构（数组、链表、栈、队列） │
└─────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────┐
│ 阶段二：核心算法 │
│ · 排序算法（冒泡、选择、插入、快排、归并、堆排序） │
│ · 二分查找 │
│ · 双指针 │
│ · 哈希表应用 │
└─────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────┐
│ 阶段三：数据结构深化 │
│ · 树与二叉树 │
│ · 二叉搜索树 │
│ · 堆（优先队列） │
│ · 图的基础 │
└─────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────┐
│ 阶段四：高级算法 │
│ · 动态规划 │
│ · 贪心算法 │
│ · 回溯算法 │
│ · 分治算法 │
└─────────────────────────────────────────────────────────┘
↓
┌─────────────────────────────────────────────────────────┐
│ 阶段五：面试实战 │
│ · 高频题专项训练 │
│ · 模拟面试 │
│ · 手写代码速度训练 │
└─────────────────────────────────────────────────────────┘
这个路线图不复杂，但每一阶段都对应着不同的能力要求。很多人跳着学，效果就很差。
三、阶段一：把基础打牢，别跳过这一步
时间复杂度分析
时间复杂度是算法的”体检报告”。你写了一个排序，是O(n²)还是O(n log n)，决定了你的代码能不能通过面试官的考验。
先搞清楚几个基本概念：
- O(1)：常数时间，不管数据量多大，执行时间不变
- O(n)：线性时间，执行时间与数据量成正比
- O(n²)：平方时间，嵌套循环的典型
- O(log n)：对数时间，二分查找的典型
- O(n log n)：线性对数时间，归并排序、快排的典型
- O(2ⁿ)：指数时间，暴力递归的典型，能避开就避开
来看一个具体例子，帮你理解为什么这个很重要：
// 例子1：O(n²) 的暴力解法
public int countPairs(int[] nums, int target) {
int count = 0;
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
count++;
}
}
}
return count;
}
// 例子2：O(n) 的优化解法（使用哈希表）
public int countPairsOptimized(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
int count = 0;
for (int num : nums) {
int complement = target - num;
if (map.containsKey(complement)) {
count += map.get(complement);
}
map.put(num, map.getOrDefault(num, 0) + 1);
}
return count;
}
同一个”两数之和”的变体问题，暴力解法在数据量大时会超时，而哈希表解法就能轻松通过。面试官问”你能优化吗”，这就是展示理解力的好机会。
Java基础回顾
算法题在Java里实现，有些东西必须熟练：
数组操作
// 常用数组操作
int[] arr = {3, 1, 4, 1, 5, 9, 2, 6};
// 排序
Arrays.sort(arr);
// 二分查找（需要已排序）
int index = Arrays.binarySearch(arr, 5);
// 数组拷贝
int[] copy = Arrays.copyOf(arr, arr.length);
// 填充
Arrays.fill(arr, 0);
集合框架
// List
List<Integer> list = new ArrayList<>();
list.add(1);
list.get(0); // O(1)
list.remove(0); // O(n)，因为要移动元素
// Set - 去重、快速查找
Set<Integer> set = new HashSet<>();
set.add(1);
set.contains(1); // O(1) 平均
// Map - 最重要的数据结构之一
Map<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.get("apple"); // O(1)
map.containsKey("apple"); // O(1)
// 按值排序的Map（ TreeMap ）
Map<Integer, String> treeMap = new TreeMap<>();
字符串操作
String s = "hello world";
s.length(); // 11
s.charAt(0); // 'h'
s.substring(0, 5); // "hello"
s.toCharArray(); // 转成char数组
s.split(" "); // ["hello", "world"]
// 字符串拼接，大量拼接用StringBuilder
StringBuilder sb = new StringBuilder();
sb.append("hello");
sb.append(" world");
String result = sb.toString();
栈和队列
// 栈 - Deque是实现栈的首选
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); // 入栈
stack.pop(); // 出栈
stack.peek(); // 查看栈顶
// 队列 - 双向队列是最通用的选择
Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); // 入队
queue.poll(); // 出队
queue.peek(); // 查看队首
queue.offerFirst(0); // 从头部入队（双端队列特性）
queue.pollLast(); // 从尾部出队（双端队列特性）
四、阶段二：排序算法，必须手写
排序是面试出现频率最高的算法之一。不是让你调Arrays.sort()，是让你手写。
快速排序
快排的核心思想是分治：选一个基准，把比它小的放左边，比它大的放右边，然后对左右两部分递归排序。
public class QuickSort {
public void sort(int[] arr, int left, int right) {
if (left >= right) return;
// 分区操作，返回基准元素的最终位置
int pivotIndex = partition(arr, left, right);
// 递归排序左右两部分
sort(arr, left, pivotIndex - 1);
sort(arr, pivotIndex + 1, right);
}
private int partition(int[] arr, int left, int right) {
// 选择最后一个元素作为基准
int pivot = arr[right];
int i = left - 1; // i指向小于基准的区域的末尾
for (int j = left; j < right; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr, i, j);
}
}
// 把基准放到正确位置
swap(arr, i + 1, right);
return i + 1;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 测试
public static void main(String[] args) {
int[] arr = {3, 6, 8, 10, 1, 2, 1};
QuickSort qs = new QuickSort();
qs.sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
// 输出: [1, 1, 2, 3, 6, 8, 10]
}
}
面试官常问的坑：
快排的最坏情况是什么？
- 当数组已经有序时，每次分区都只减少一个元素，时间复杂度退化为O(n²)
- 解决方案：随机选择基准，或者三数取中法
快排是稳定排序吗？
- 不是。相等元素的相对位置可能改变
快排的空间复杂度是多少？
- O(log n)，递归栈的深度
归并排序
归并排序的思路很清晰：先分，再合。把数组从中间切开，分别排序，然后合并两个有序数组。
public class MergeSort {
public void sort(int[] arr) {
if (arr == null || arr.length <= 1) return;
int[] temp = new int[arr.length];
mergeSort(arr, temp, 0, arr.length - 1);
}
private void mergeSort(int[] arr, int[] temp, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2; // 防止溢出
mergeSort(arr, temp, left, mid); // 排序左半部分
mergeSort(arr, temp, mid + 1, right); // 排序右半部分
merge(arr, temp, left, mid, right); // 合并
}
private void merge(int[] arr, int[] temp, int left, int mid, int right) {
// 复制到临时数组
for (int i = left; i <= right; i++) {
temp[i] = arr[i];
}
int i = left; // 左半部分指针
int j = mid + 1; // 右半部分指针
int k = left; // 合并后的指针
while (i <= mid && j <= right) {
if (temp[i] <= temp[j]) {
arr[k++] = temp[i++];
} else {
arr[k++] = temp[j++];
}
}
// 复制左半部分剩余元素（右半部分剩余的不需要复制，因为已经在正确位置）
while (i <= mid) {
arr[k++] = temp[i++];
}
}
public static void main(String[] args) {
int[] arr = {38, 27, 43, 3, 9, 82, 10};
MergeSort ms = new MergeSort();
ms.sort(arr);
System.out.println(Arrays.toString(arr));
// 输出: [3, 9, 10, 27, 38, 43, 82]
}
}
归并排序的特点：
- 时间复杂度稳定：O(n log n)
- 空间复杂度：O(n)
- 是稳定排序
- 适合链表排序（不需要额外空间）
堆排序
堆排序可能不是面试最常考的，但理解堆对于后面的”Top K问题”至关重要。
public class HeapSort {
public void sort(int[] arr) {
int n = arr.length;
// 1. 构建最大堆（从最后一个非叶子节点开始）
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 2. 逐个提取元素
for (int i = n - 1; i > 0; i--) {
// 把最大元素移到末尾
swap(arr, 0, i);
// 重新调整堆
heapify(arr, i, 0);
}
}
private void heapify(int[] arr, int n, int i) {
int largest = i; // 假设根节点最大
int left = 2 * i + 1; // 左子节点
int right = 2 * i + 2; // 右子节点
// 如果左子节点更大
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点更大
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是根节点，交换并继续调整
if (largest != i) {
swap(arr, i, largest);
heapify(arr, n, largest);
}
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
HeapSort hs = new HeapSort();
hs.sort(arr);
System.out.println(Arrays.toString(arr));
// 输出: [5, 6, 7, 11, 12, 13]
}
}
五、阶段三：二分查找，简洁但容易出错
二分查找是面试高频题，看似简单，但边界条件非常容易写错。
public class BinarySearch {
/**
* 标准二分查找：查找目标值是否存在
*/
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出，不要用 (left+right)/2
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // 目标在右半部分
} else {
right = mid - 1; // 目标在左半部分
}
}
return -1; // 未找到
}
/**
* 查找第一个大于等于target的位置（lower bound）
* 这是非常实用的变体，很多题都用得到
*/
public int lowerBound(int[] nums, int target) {
int left = 0;
int right = nums.length; // 注意：right是nums.length，不是length-1
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid; // 注意：可能mid就是答案，不能跳过
}
}
return left;
}
/**
* 查找第一个大于target的位置（upper bound）
*/
public int upperBound(int[] nums, int target) {
int left = 0;
int right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] <= target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
public static void main(String[] args) {
BinarySearch bs = new BinarySearch();
int[] nums = {1, 2, 3, 3, 3, 4, 5};
System.out.println(bs.search(nums, 3)); // 输出: 2（第一个找到的位置）
System.out.println(bs.lowerBound(nums, 3)); // 输出: 2（第一个>=3的位置）
System.out.println(bs.upperBound(nums, 3)); // 输出: 5（第一个>3的位置）
}
}
二分查找的常见变体：
| 变体类型 | 应用场景 |
|---|---|
| 标准查找 | 判断元素是否存在 |
| lower bound | 找第一个>=target的位置 |
| upper bound | 找第一个>target的位置 |
| 旋转数组查找 | 搜索旋转排序数组 |
| 峰值查找 | 找局部峰值 |
| 平方根计算 | 求整数的平方根 |
六、阶段四：双指针，优雅的解题技巧
双指针适用于数组、字符串相关问题，能大幅降低时间复杂度。
经典例子：两数之和 II（有序数组）
public class TwoSumII {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum == target) {
return new int[]{left + 1, right + 1}; // 1-based索引
} else if (sum < target) {
left++; // 和太小，左指针右移
} else {
right--; // 和太大，右指针左移
}
}
return new int[]{-1, -1};
}
}
滑动窗口
滑动窗口是双指针的一种特殊形式，适用于”连续子数组/子串”相关问题。
public class SlidingWindow {
/**
* 无重复字符的最长子串
* 经典滑动窗口问题
*/
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> window = new HashMap<>();
int left = 0;
int maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
window.put(c, window.getOrDefault(c, 0) + 1);
// 当窗口内有重复字符时，收缩左边界
while (window.get(c) > 1) {
char leftChar = s.charAt(left);
window.put(leftChar, window.get(leftChar) - 1);
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
/**
* 最小覆盖子串
* harder版本，需要仔细处理边界
*/
public String minWindow(String s, String t) {
Map<Character, Integer> need = new HashMap<>();
Map<Character, Integer> window = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0; // 满足need条件的字符种类数
int start = 0, minLen = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
right++;
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 当所有字符都满足时，尝试收缩左边界
while (valid == need.size()) {
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.get(d) - 1);
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
}
七、阶段五：树，面试的重头戏
树结构在面试中占据半壁江山。二叉树的遍历、搜索、最近公共祖先、序列化……这些都是必考内容。
二叉树的三种遍历
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class TreeTraversal {
// 递归实现
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
inorder(root, result);
return result;
}
private void inorder(TreeNode node, List<Integer> result) {
if (node == null) return;
inorder(node.left, result); // 左
result.add(node.val); // 中
inorder(node.right, result); // 右
}
// 迭代实现（使用栈）
public List<Integer> inorderIterative(TreeNode root) {
List<Integer> result = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
// 一直走到最左边
while (current != null) {
stack.push(current);
current = current.left;
}
// 弹出并访问
current = stack.pop();
result.add(current.val);
// 转向右子树
current = current.right;
}
return result;
}
// 层序遍历（BFS）
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
}
return result;
}
}
二叉搜索树（BST）
public class BST {
/**
* 二叉搜索树中的插入操作
*/
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
/**
* 二叉搜索树中的搜索
*/
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) return root;
if (val < root.val) {
return searchBST(root.left, val);
} else {
return searchBST(root.right, val);
}
}
/**
* 删除节点（较难，面试高频）
*/
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (key < root.val) {
root.left = deleteNode(root.left, key);
} else if (key > root.val) {
root.right = deleteNode(root.right, key);
} else {
// 找到要删除的节点
// 情况1：没有左子树，返回右子树
if (root.left == null) return root.right;
// 情况2：没有右子树，返回左子树
if (root.right == null) return root.left;
// 情况3：有两个子节点
// 找到右子树的最小节点（中序后继）
TreeNode minNode = findMin(root.right);
root.val = minNode.val;
root.right = deleteNode(root.right, minNode.val);
}
return root;
}
private TreeNode findMin(TreeNode node) {
while (node.left != null) {
node = node.left;
}
return node;
}
}
最近公共祖先（LCA）
public class LowestCommonAncestor {
/**
* 二叉树的最近公共祖先
* 思路：如果p和q分别在左右子树，则当前节点就是LCA
*/
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
// p和q分别在左右子树
if (left != null && right != null) return root;
// 都在左子树或都在右子树
return left != null ? left : right;
}
/**
* 二叉搜索树的最近公共祖先（利用BST性质优化）
*/
public TreeNode lowestCommonAncestorBST(TreeNode root, TreeNode p, TreeNode q) {
if (root == null) return null;
// 如果p和q都在左子树
if (p.val < root.val && q.val < root.val) {
return lowestCommonAncestorBST(root.left, p, q);
}
// 如果p和q都在右子树
if (p.val > root.val && q.val > root.val) {
return lowestCommonAncestorBST(root.right, p, q);
}
// 分居两侧，当前节点就是LCA
return root;
}
}
八、阶段六：动态规划，算法学习的分水岭
动态规划是很多人的噩梦，但只要你掌握了方法，它其实是有规律可循的。
动态规划的核心思想
动态规划的本质是记忆化搜索——把子问题的解存起来，避免重复计算。
解题步骤：
- 定义dp数组的含义
- 找出状态转移方程
- 确定边界条件
- 确定遍历顺序
经典例子1：斐波那契数列
public class Fibonacci {
// 方法1：递归（效率极低，O(2^n)）
public int fibRecursive(int n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// 方法2：记忆化递归（自顶向下，O(n)）
public int fibMemo(int n) {
if (n <= 1) return n;
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
return fibMemoHelper(n, memo);
}
private int fibMemoHelper(int n, int[] memo) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n];
memo[n] = fibMemoHelper(n - 1, memo) + fibMemoHelper(n - 2, memo);
return memo[n];
}
// 方法3：动态规划（自底向上，O(n)空间）
public int fibDP(int n) {
if (n <= 1) return n;
int[] dp = new int[n + 1];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// 方法4：空间优化（O(1)空间）
public int fibOptimized(int n) {
if (n <= 1) return n;
int prev2 = 0;
int prev1 = 1;
int current = 0;
for (int i = 2; i <= n; i++) {
current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return current;
}
}
从方法1到方法4，我们看到了动态规划的典型优化路径：暴力递归 → 记忆化 → 表格DP → 空间优化。
经典例子2：0-1背包问题
这是动态规划最经典的问题之一。
public class Knapsack01 {
/**
* 0-1背包问题
* 有n个物品，每个物品有重量weight[i]和价值value[i]
* 背包容量为W，求能装下的最大价值
*
* 状态定义：dp[i][j]表示前i个物品，背包容量为j时的最大价值
* 状态转移：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])
*/
public int knapsack(int[] weights, int[] values, int capacity) {
int n = weights.length;
// dp[i][j]表示前i个物品，容量为j时的最大价值
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= capacity; j++) {
// 不选第i个物品
dp[i][j] = dp[i - 1][j];
// 选第i个物品（如果装得下）
if (j >= weights[i - 1]) {
dp[i][j] = Math.max(dp[i][j],
dp[i - 1][j - weights[i - 1]] + values[i - 1]);
}
}
}
return dp[n][capacity];
}
/**
* 空间优化版（滚动数组）
* 从二维dp压缩到一维dp
*/
public int knapsackOptimized(int[] weights, int[] values, int capacity) {
int n = weights.length;
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
// 从后向前遍历，避免覆盖需要使用到的旧值
for (int j = capacity; j >= weights[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
}
}
return dp[capacity];
}
}
经典例子3：最长公共子序列
public class LongestCommonSubsequence {
/**
* 最长公共子序列（LCS）
* 状态定义：dp[i][j]表示text1前i个字符和text2前j个字符的LCS长度
* 状态转移：
* 如果text1[i-1] == text2[j-1]，dp[i][j] = dp[i-1][j-1] + 1
* 否则，dp[i][j] = max(dp[i-1][j], dp[i][j-1])
*/
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
/**
* 编辑距离（Levenshtein Distance）
* 同样是LCS的变体，非常经典的DP题
*/
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// 初始化边界
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = Math.min(dp[i - 1][j], // 删除
Math.min(dp[i][j - 1], // 插入
dp[i - 1][j - 1])) + 1; // 替换
}
}
}
return dp[m][n];
}
}
动态规划入门推荐题目
| 题目 | 难度 | 核心思想 |
|---|---|---|
| 爬楼梯 | Easy | 基础DP |
| 不同路径 | Easy | 二维DP |
| 最长递增子序列 | Medium | 经典DP |
| 零钱兑换 | Medium | 完全背包 |
| 背包问题 | Medium | 0-1背包 |
| 最长公共子序列 | Medium | 二维DP |
| 编辑距离 | Medium | 二维DP |
| 最长回文子串 | Medium | 区间DP |
九、阶段七：回溯算法，暴力但有技巧
回溯算法本质是DFS + 剪枝，用于解决排列、组合、子集等问题。
public class Backtracking {
/**
* 全排列问题
* 给定一个不含重复数字的数组，返回所有可能的全排列
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, used, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> path,
List<List<Integer>> result) {
// 终止条件：路径长度等于数组长度
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // 剪枝：已使用过
used[i] = true;
path.add(nums[i]);
backtrack(nums, used, path, result);
// 回溯：撤销选择
path.remove(path.size() - 1);
used[i] = false;
}
}
/**
* 子集问题
* 给定一个整数数组，返回其所有子集
*/
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrackSubsets(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrackSubsets(int[] nums, int start, List<Integer> path,
List<List<Integer>> result) {
result.add(new ArrayList<>(path)); // 每次递归都加入当前路径
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrackSubsets(nums, i + 1, path, result); // 注意：从i+1开始，避免重复
path.remove(path.size() - 1);
}
}
/**
* N皇后问题（经典回溯）
*/
public List<List<String>> solveNQueens(int n) {
List<List<String>> result = new ArrayList<>();
char[][] board = new char[n][n];
for (char[] row : board) {
Arrays.fill(row, '.');
}
backtrackQueens(board, 0, result);
return result;
}
private void backtrackQueens(char[][] board, int row,
List<List<String>> result) {
if (row == board.length) {
List<String> solution = new ArrayList<>();
for (char[] r : board) {
solution.add(new String(r));
}
result.add(solution);
return;
}
for (int col = 0; col < board.length; col++) {
if (isValid(board, row, col)) {
board[row][col] = 'Q';
backtrackQueens(board, row + 1, result);
board[row][col] = '.'; // 回溯
}
}
}
private boolean isValid(char[][] board, int row, int col) {
// 检查同一列
for (int i = 0; i < row; i++) {
if (board[i][col] == 'Q') return false;
}
// 检查左上对角线
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') return false;
}
// 检查右上对角线
for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
if (board[i][j] == 'Q') return false;
}
return true;
}
}
回溯模板（三要素）：
- 路径：已经做的选择
- 选择列表：当前可以做的选择
- 结束条件：到达决策树底层，触发结束
十、阶段八：图论基础，DFS和BFS
图的遍历是理解更复杂算法的基础。
public class GraphTraversal {
// 邻接表表示的图
private List<List<Integer>> adj;
private boolean[] visited;
public GraphTraversal(int vertices) {
adj = new ArrayList<>();
for (int i = 0; i < vertices; i++) {
adj.add(new ArrayList<>());
}
visited = new boolean[vertices];
}
public void addEdge(int u, int v) {
adj.get(u).add(v);
adj.get(v).add(u); // 无向图
}
/**
* DFS递归实现
*/
public void dfsRecursive(int start) {
Arrays.fill(visited, false);
dfsHelper(start);
}
private void dfsHelper(int v) {
visited[v] = true;
System.out.print(v + " ");
for (int neighbor : adj.get(v)) {
if (!visited[neighbor]) {
dfsHelper(neighbor);
}
}
}
/**
* DFS迭代实现（使用栈）
*/
public void dfsIterative(int start) {
Arrays.fill(visited, false);
Stack<Integer> stack = new Stack<>();
stack.push(start);
visited[start] = true;
while (!stack.isEmpty()) {
int v = stack.pop();
System.out.print(v + " ");
// 逆序压栈，保证遍历顺序与递归一致
for (int i = adj.get(v).size() - 1; i >= 0; i--) {
int neighbor = adj.get(v).get(i);
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
}
}
}
/**
* BFS（层序遍历）
*/
public void bfs(int start) {
Arrays.fill(visited, false);
Queue<Integer> queue = new LinkedList<>();
queue.offer(start);
visited[start] = true;
while (!queue.isEmpty()) {
int v = queue.poll();
System.out.print(v + " ");
for (int neighbor : adj.get(v)) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.offer(neighbor);
}
}
}
}
/**
* 检测图中是否有环（无向图）
*/
public boolean hasCycle() {
Arrays.fill(visited, false);
for (int i = 0; i < adj.size(); i++) {
if (!visited[i]) {
if (hasCycleHelper(i, -1)) return true;
}
}
return false;
}
private boolean hasCycleHelper(int v, int parent) {
visited[v] = true;
for (int neighbor : adj.get(v)) {
if (!visited[neighbor]) {
if (hasCycleHelper(neighbor, v)) return true;
} else if (neighbor != parent) {
return true; // 发现回边，存在环
}
}
return false;
}
}
十一、刷题策略：不要盲目刷
很多人刷题的问题是：** quantity > quality **。刷了500题，但面试还是不会。
我的建议：
第一步：按专题刷，不要按难度刷
把LeetCode按知识点分类，逐个击破：
- 数组：前100题
- 字符串：前50题
- 链表：前50题
- 树：前100题
- 动态规划：前50题
- …
第二步：一题多解，一解多题
同一个题目，尝试用不同方法解。解完一道题，想想类似的题目有哪些。
比如”两数之和”和”四数之和”思路类似，”二叉树遍历”和”二叉树层序遍历”可以一起记忆。
第三步：总结模板，形成肌肉记忆
// 二分查找模板（记住这一种就够了）
public 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 right = mid - 1;
}
return -1;
}
// 快排模板
public void quickSort(int[] arr, int left, int right) {
if (left >= right) return;
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
// 二叉树遍历模板（递归）
public void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
process(root);
inorder(root.right);
}
// DFS模板
public void dfs(Node node, boolean[] visited) {
if (visited[node.val]) return;
visited[node.val] = true;
process(node);
for (Node neighbor : node.neighbors) {
dfs(neighbor, visited);
}
}
// BFS模板
public void bfs(Node start) {
Queue<Node> queue = new LinkedList<>();
Set<Integer> visited = new HashSet<>();
queue.offer(start);
visited.add(start.val);
while (!queue.isEmpty()) {
Node current = queue.poll();
process(current);
for (Node neighbor : current.neighbors) {
if (!visited.contains(neighbor.val)) {
visited.add(neighbor.val);
queue.offer(neighbor);
}
}
}
}
把这几个模板背下来，面试时手到擒来。
十二、推荐资源清单
书籍
| 书名 | 作者 | 适合阶段 | 评价 |
|---|---|---|---|
| 《算法4》 | Robert Sedgewick | 入门-进阶 | 经典中的经典，配图清晰 |
| 《剑指Offer》 | 何海涛 | 面试准备 | 国内面试必备，题目经典 |
| 《程序员面试金典》 | Google工程师 | 面试准备 | 题目覆盖全面 |
| 《算法导论》 | CLRS | 进阶-深入 | 学术性强，不适合速成 |
| 《算法》 | Sedgewick | 进阶 | 更简洁的版本 |
在线平台
- LeetCode：刷题首选，题量大，社区活跃
- 牛客网：国内面试准备，有真题库
- HackerRank：难度适中，界面友好
- Codeforces：竞赛级难度，适合提升
- LintCode：题目质量不错，有中文支持
视频课程
- MIT 6.006 算法导论：入门首选，讲解清晰
- 魏秀明 数据结构与算法：B站免费，讲得细致
- labuladong的算法小抄：套路清晰，适合快速上手
十三、我的建议：给正在准备的你
回想我当初算法全军覆没的时候，心情确实很低落。但后来我明白了一件事：算法不是天赋，是练习。
我的经验总结成三句话：
第一句：基础不牢，地动山摇。
不要一上来就啃动态规划。先把数组、链表、栈、队列这些基础数据结构搞明白，排序和二分这些基础算法手写熟练。
第二句：不要追求数量，要追求质量。
刷100道高质量题目，比刷500道水题有用得多。每道题都要理解思路、能独立写出来、能讲清楚。
第三句：模拟面试，开口说。
很多面试官不只考你会不会，还考你能不能讲清楚。平时练习时，试着把解题思路讲给别人听。如果不能清晰地表达，说明你还没有真正理解。
十四、面试前最后的准备
面试前一周，做这几件事：
- 复习高频题：把LeetCode热题100再过一遍，确保能独立写出来
- 准备自我介绍：用3分钟讲清楚你的项目经历和技术亮点
- 复习基础概念：HashMap原理、JVM基础、多线程等，算法之外也很重要
- 保持手感：每天做1-2道题，不要停，保持手感
最后想说，算法这条路，确实挺难的。我第一次被拒的时候，也怀疑过自己是不是不适合写代码。但后来我用对了方法，坚持了三个月，拿到了offer。
你需要的不是天赋，是一套正确的方法，加上足够的练习。
这篇文章里的每一个代码例子，都是我自己理解之后重写过的。如果你看完觉得有帮助，那就去动手敲一敲。代码这东西，看一百遍不如写一遍。
祝你早日拿到心仪的offer。