1 介绍
1.1 考试与面试概述
01.考试类型
a.笔试
a.选择题
考察基础知识和概念理解。
b.填空题
考察对算法细节的掌握。
c.编程题
考察算法实现能力。
b.机试
在线编程考试，如牛客网、赛码网。
c.面试
a.算法面试
现场手写代码或在线编程。
b.系统设计
设计大规模系统架构。
02.考试准备
a.基础知识
数据结构、算法、时间空间复杂度。
b.编程能力
熟练掌握Java或Go等编程语言。
c.刷题训练
LeetCode、牛客网、AcWing等平台。
d.模拟考试
定期进行模拟考试，提升应试能力。
03.面试技巧
a.沟通能力
清晰表达思路，与面试官互动。
b.问题分析
先分析问题，再动手编码。
c.代码规范
注意代码风格和命名规范。
d.测试用例
考虑边界条件和特殊情况。
04.常见考点
a.数据结构
数组、链表、栈队列、树、图、哈希表。
b.算法
排序、查找、双指针、动态规划、贪心、搜索。
c.系统设计
缓存、负载均衡、分布式系统。
1.2 时间复杂度分析
01.常见时间复杂度
a.O(1)
数组访问、哈希表查找、数学运算。
b.O(log n)
二分查找、堆操作、平衡树操作。
c.O(n)
遍历数组、遍历链表、线性查找。
d.O(n log n)
快速排序、归并排序、堆排序。
e.O(n²)
双重循环、冒泡排序、选择排序。
f.O(2ⁿ)
递归求解所有子集、暴力搜索。
02.复杂度估算
a.根据数据规模选择算法
a.n ≤ 10
O(n!)全排列。
b.n ≤ 20
O(2ⁿ)状态压缩DP。
c.n ≤ 100
O(n³)Floyd算法。
d.n ≤ 1000
O(n²)冒泡排序。
e.n ≤ 10⁵
O(n log n)快速排序。
f.n ≤ 10⁶
O(n)线性扫描。
g.n ≤ 10⁹
O(log n)二分查找。
03.空间复杂度分析
a.原地算法
O(1)空间，如快速排序。
b.递归栈
O(log n)或O(n)，取决于递归深度。
c.辅助数组
O(n)空间，如归并排序。
04.优化方向
a.时间换空间
使用哈希表、前缀和等。
b.空间换时间
使用记忆化搜索、DP。
1.3 算法题型分类
01.数据结构题
a.线性结构
数组、链表、栈、队列。
b.树形结构
二叉树、二叉搜索树、平衡树、堆。
c.图结构
邻接矩阵、邻接表、图的遍历。
d.哈希表
哈希函数、冲突处理。
02.算法设计题
a.递归与分治
归并排序、快速排序、二分查找。
b.动态规划
背包问题、最长子序列、路径问题。
c.贪心算法
区间调度、哈夫曼编码。
d.回溯搜索
全排列、N皇后、子集问题。
03.应用题
a.字符串处理
KMP、字符串匹配、编辑距离。
b.图论算法
最短路、最小生成树、拓扑排序。
c.数学问题
质数、GCD、快速幂、组合数。
04.综合题
a.系统设计
LRU缓存、LFU缓存、数据库设计。
b.实际应用
任务调度、资源分配、路径规划。
1.4 解题思路框架
01.理解题目
a.读题
仔细阅读题目，理解输入输出格式。
b.样例分析
通过样例理解题意，找出规律。
c.边界条件
考虑特殊情况和边界条件。
02.分析问题
a.数据规模
根据数据范围选择合适的算法。
b.时间限制
估算算法复杂度是否满足要求。
c.空间限制
考虑内存使用是否超限。
03.设计算法
a.暴力法
先想出暴力解法，再优化。
b.分类讨论
将问题分解为多个子问题。
c.模式识别
识别题目类型，套用模板。
04.编码实现
a.代码结构
清晰的函数划分，便于调试。
b.变量命名
使用有意义的变量名。
c.注释
关键逻辑添加注释。
1.5 备考策略
01.时间规划
a.长期规划
制定3-6个月的学习计划。
b.短期目标
每周完成一定数量的题目。
c.复习周期
定期复习已学内容，巩固记忆。
02.学习方法
a.理论学习
系统学习数据结构和算法理论。
b.实践练习
在LeetCode、牛客网等平台刷题。
c.总结归纳
整理笔记和代码模板。
03.心态调整
a.保持耐心
算法学习需要时间积累。
b.克服困难
遇到难题不要放弃，多思考多查资料。
c.适度休息
避免过度疲劳，保持学习效率。
04.资源推荐
a.在线平台
LeetCode、牛客网、AcWing、洛谷。
b.书籍
算法导论、剑指Offer、程序员代码面试指南。
c.视频课程
慕课网、极客时间、B站算法课程。
2 数据结构实战
2.1 线性表综合题
01.数组操作
a.旋转数组
---
public void rotate(int[] nums, int k) {
k %= nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, nums.length - 1);
}
private void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
---
b.原地删除重复项
双指针法，时间O(n)，空间O(1)。
02.链表操作
a.反转链表
---
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
---
b.合并K个有序链表
使用优先队列，时间O(n log k)。
03.栈的应用
a.有效的括号
使用栈匹配括号。
b.最小栈
使用辅助栈存储最小值。
04.队列的应用
a.滑动窗口最大值
使用单调队列。
b.设计循环队列
使用数组实现。
2.2 栈与队列应用题
01.有效的括号
a.问题
判断括号字符串是否有效。
b.栈解法
遇到左括号入栈，右括号出栈匹配。
02.最小栈
a.问题
设计支持O(1)时间获取最小值的栈。
b.辅助栈
使用额外栈存储最小值。
03.滑动窗口最大值
a.问题
求每个窗口的最大值。
b.单调队列
维护递减的单调队列。
2.3 树结构综合题
01.二叉树遍历
a.前序中序后序
递归和迭代两种实现。
b.层序遍历
使用队列BFS。
02.二叉树构造
a.从前序和中序构造
递归分治。
b.从后序和中序构造
递归分治。
03.二叉搜索树
a.验证BST
中序遍历递增。
b.BST的第K大
中序遍历或Morris遍历。
2.4 图结构综合题
01.图的遍历
a.DFS
递归或栈实现。
b.BFS
队列实现。
02.最短路
a.Dijkstra
单源最短路，边权非负。
b.Floyd
多源最短路。
03.拓扑排序
a.Kahn算法
入度为0的节点入队。
b.DFS
后序遍历逆序。
2.5 二叉排序树与平衡树
01.二叉排序树BST
a.插入
递归或迭代。
b.删除
三种情况：叶子、单子、双子。
c.查找
递归或迭代。
02.平衡树
a.AVL树
通过旋转维持平衡。
b.红黑树
Java TreeMap的实现。
03.应用
a.动态维护有序集合
支持插入删除查询。
b.区间查询
结合线段树。
2.6 Huffman树应用
01.Huffman编码
a.构造Huffman树
每次选择两个最小权值节点合并。
b.编码
左0右1，从根到叶的路径。
02.Java实现
a.优先队列
---
public long huffman(int[] weights) {
PriorityQueue<Long> pq = new PriorityQueue<>();
for (int w : weights) pq.offer((long)w);
long cost = 0;
while (pq.size() > 1) {
long a = pq.poll();
long b = pq.poll();
cost += a + b;
pq.offer(a + b);
}
return cost;
}
---
03.应用场景
a.数据压缩
最优前缀编码。
b.文件压缩
ZIP、GZIP等。
2.7 数据结构选择题
01.选择原则
a.根据操作频率
频繁查找用哈希表，频繁插入删除用链表。
b.根据数据特点
有序数据用BST，需要范围查询用线段树。
c.根据空间限制
空间紧张用数组，空间充足用哈希表。
02.常见场景
a.LRU缓存
HashMap + 双向链表。
b.Top K
最小堆或快速选择。
c.中位数
两个堆：最大堆和最小堆。
03.时间复杂度对比
a.数组
查找O(n)，插入删除O(n)。
b.链表
查找O(n)，插入删除O(1)。
c.哈希表
查找插入删除O(1)。
d.BST
查找插入删除O(log n)。
3 查找与排序
3.1 查找算法综合
01.二分查找
a.标准二分
在有序数组中查找目标值。
b.左边界
查找第一个大于等于target的位置。
c.右边界
查找最后一个小于等于target的位置。
02.哈希查找
a.HashMap
O(1)时间查找。
b.HashSet
判断元素是否存在。
03.树查找
a.BST查找
二叉搜索树的查找。
b.平衡树
AVL树、红黑树的查找。
3.2 B树与B+树
01.B树
a.定义
多路平衡查找树，每个节点可以有多个子节点。
b.特点
所有叶子节点在同一层。
c.应用
数据库索引、文件系统。
02.B+树
a.定义
B树的变种，所有数据都在叶子节点。
b.特点
叶子节点形成链表，便于范围查询。
c.应用
MySQL的InnoDB索引。
03.对比
a.B树
节点存储数据，适合点查询。
b.B+树
只有叶子存数据，适合范围查询。
3.3 散列表应用
01.哈希函数
a.除留余数法
h(key) = key % m
b.乘法哈希
h(key) = (key * A) % m
c.字符串哈希
多项式哈希。
02.冲突处理
a.链地址法
每个桶是一个链表。
b.开放寻址法
线性探测、二次探测、双重哈希。
03.应用题
a.两数之和
哈希表存储已遍历的数。
b.字母异位词分组
排序后的字符串作为key。
3.4 字符串匹配KMP
01.KMP算法
a.next数组
记录最长相等前后缀长度。
b.时间复杂度
O(m+n)，m是模式串长度，n是文本串长度。
02.Java实现
a.构建next数组
---
int[] getNext(String pattern) {
int m = pattern.length();
int[] next = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
j = next[j-1];
}
if (pattern.charAt(i) == pattern.charAt(j)) j++;
next[i] = j;
}
return next;
}
---
03.应用
a.字符串匹配
在文本中查找模式串。
b.重复子串
找最长重复子串。
3.5 排序算法综合
01.快速排序
a.标准实现
---
public void quickSort(int[] arr, int l, int r) {
if (l >= r) return;
int i = l - 1, j = r + 1, x = arr[l + r >> 1];
while (i < j) {
do i++; while (arr[i] < x);
do j--; while (arr[j] > x);
if (i < j) swap(arr, i, j);
}
quickSort(arr, l, j);
quickSort(arr, j + 1, r);
}
---
b.三路快排
处理重复元素更高效。
02.归并排序
a.标准实现
---
public void mergeSort(int[] arr, int l, int r) {
if (l >= r) return;
int mid = l + r >> 1;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
---
b.逆序对统计
在归并过程中统计逆序对。
03.堆排序
a.建堆
从最后一个非叶子节点开始下沉。
b.排序
依次取出堆顶元素。
04.排序算法选择
a.快速排序
平均O(n log n)，不稳定，原地排序。
b.归并排序
O(n log n)，稳定，需要额外空间。
c.堆排序
O(n log n)，不稳定，原地排序。
3.6 外部排序
01.外部排序概述
a.定义
数据量太大无法全部装入内存，需要使用外存。
b.基本思想
分治法，先内部排序，再归并。
02.多路归并
a.步骤
a.分块
将大文件分成多个小块。
b.内部排序
对每个小块进行内部排序。
c.多路归并
使用优先队列归并多个有序块。
03.败者树
a.定义
用于优化多路归并的数据结构。
b.优势
减少比较次数。
3.7 排序查找真题
01.排序真题
a.数组中的第K大元素
快速选择O(n)。
b.合并K个有序链表
优先队列O(n log k)。
02.查找真题
a.搜索旋转排序数组
二分查找变形。
b.寻找两个正序数组的中位数
二分查找O(log(m+n))。
03.综合题
a.前K个高频元素
哈希表+堆。
b.数据流的中位数
两个堆维护。
4 算法设计题
4.1 递归与分治
01.递归基础
a.递归三要素
递归终止条件、递归公式、边界条件。
b.递归优化
尾递归、记忆化。
02.分治算法
a.归并排序
分解、递归、合并。
b.快速排序
选择pivot、分区、递归。
03.经典题目
a.汉诺塔
递归移动盘子。
b.全排列
回溯生成所有排列。
4.2 动态规划题型
01.线性DP
a.最长上升子序列
---
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);
int maxLen = 1;
for (int i = 1; i < nums.length; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
maxLen = Math.max(maxLen, dp[i]);
}
return maxLen;
}
---
b.最长公共子序列
二维DP，dp[i][j]表示s1前i个和s2前j个的LCS。
02.背包DP
a.01背包
---
public int knapsack01(int[] w, int[] v, int V) {
int[] dp = new int[V + 1];
for (int i = 0; i < w.length; i++) {
for (int j = V; j >= w[i]; j--) {
dp[j] = Math.max(dp[j], dp[j-w[i]] + v[i]);
}
}
return dp[V];
}
---
b.完全背包
内层循环正序遍历。
03.区间DP
a.石子合并
dp[i][j]表示合并区间[i,j]的最小代价。
b.最长回文子序列
dp[i][j]表示s[i..j]的最长回文子序列长度。
04.状态压缩DP
a.旅行商问题
dp[state][i]表示访问state集合且当前在i的最短路径。
b.集合DP
使用二进制表示状态。
4.3 贪心算法题型
01.区间问题
a.区间选点
按右端点排序。
b.最大不相交区间
贪心选择。
02.贪心策略
a.局部最优
每步选择当前最优。
b.证明
交换论证法、反证法。
03.经典题目
a.跳跃游戏
贪心维护最远位置。
b.分发饼干
排序后贪心分配。
4.4 回溯与搜索
01.回溯框架
a.选择列表
当前可以做的选择。
b.路径
已经做过的选择。
c.结束条件
到达决策树底层。
02.剪枝优化
a.可行性剪枝
提前判断不可行。
b.最优性剪枝
不可能更优则剪枝。
03.经典题目
a.N皇后
回溯放置皇后。
b.数独
回溯填数字。
4.5 图论算法题
01.图的遍历
a.DFS应用
连通性、环检测、拓扑排序。
b.BFS应用
最短路、层序遍历。
02.最短路
a.Dijkstra
单源最短路，边权非负。
b.Bellman-Ford
可处理负权边。
c.Floyd
多源最短路。
03.最小生成树
a.Kruskal
边排序+并查集。
b.Prim
贪心选择最小边。
4.6 字符串处理题
01.字符串匹配
a.暴力匹配
O(mn)时间复杂度。
b.KMP
O(m+n)时间复杂度。
02.字符串操作
a.反转
双指针。
b.去重
快慢指针。
03.经典题目
a.最长回文子串
中心扩展或DP。
b.字符串相加
模拟大数加法。
4.7 综合设计题
01.系统设计
a.LRU缓存
HashMap + 双向链表。
b.LFU缓存
HashMap + 频率链表。
02.数据结构设计
a.最小栈
辅助栈存最小值。
b.全O(1)数据结构
支持O(1)的inc、dec、getMax、getMin。
03.算法设计
a.任务调度器
贪心或优先队列。
b.设计推特
哈希表+堆。
5 笔试真题
5.1 2021年真题解析
01.选择题
a.数据结构
时间空间复杂度分析。
b.算法
排序、查找算法特点。
02.填空题
a.代码填空
补充关键代码。
b.结果填空
计算程序输出。
03.编程题
a.动态规划
背包问题、最长子序列。
b.图论
最短路、拓扑排序。
5.2 模拟题精选
01.基础题
a.数组操作
旋转、去重、合并。
b.链表操作
反转、合并、环检测。
02.进阶题
a.树的遍历
前中后序、层序。
b.图的遍历
DFS、BFS。
03.综合题
a.动态规划
背包、LIS、LCS。
b.贪心算法
区间调度、跳跃游戏。
5.3 递推与枚举
01.递推
a.斐波那契数列
F(n) = F(n-1) + F(n-2)
b.爬楼梯
dp[i] = dp[i-1] + dp[i-2]
02.枚举
a.全排列
递归生成所有排列。
b.子集
位运算或回溯。
03.组合枚举
a.组合数
C(n,m) = C(n-1,m-1) + C(n-1,m)
b.组合生成
递归或迭代。
5.4 高精度计算
01.高精度加法
a.实现
模拟竖式加法，处理进位。
b.Java
使用StringBuilder逆序处理。
02.高精度减法
a.实现
模拟竖式减法，处理借位。
b.注意
确保被减数大于减数。
03.高精度乘法
a.大数乘小数
逐位相乘累加。
b.大数乘大数
模拟竖式乘法。
04.高精度除法
a.大数除小数
模拟长除法。
5.5 位运算技巧
01.基本操作
a.判断奇偶
x & 1
b.交换变量
a ^= b; b ^= a; a ^= b;
c.去掉最低位1
x & (x-1)
02.常用技巧
a.统计1的个数
Brian Kernighan算法。
b.判断2的幂
x > 0 && (x & (x-1)) == 0
03.应用题
a.只出现一次的数字
异或运算。
b.位1的个数
循环统计或查表。
5.6 计算几何基础
01.点和向量
a.点的表示
(x, y)坐标。
b.向量运算
加减、数乘、点积、叉积。
02.直线和线段
a.点到直线距离
公式法。
b.线段相交
跨立实验。
03.多边形
a.面积计算
叉积法。
b.点在多边形内
射线法。
5.7 真题综合训练
01.历年真题
a.2020年
动态规划、图论。
b.2021年
贪心、搜索。
c.2022年
字符串、数学。
02.模拟考试
a.时间控制
3小时完成5-7题。
b.难度分布
简单2题、中等3题、困难2题。
03.评分标准
a.代码正确性
通过所有测试用例。
b.代码质量
清晰、简洁、高效。
6 面试高频题
6.1 数组与字符串
01.两数之和
a.题目
LeetCode 1 - 给定数组和目标值，找出和为目标值的两个数的索引。
b.哈希表解法
---
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{};
}
---
02.最长无重复子串
a.题目
LeetCode 3 - 找出字符串中最长的无重复字符子串。
b.滑动窗口解法
---
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int maxLen = 0, left = 0;
for (int right = 0; right < s.length(); right++) {
while (set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
---
03.三数之和
a.题目
LeetCode 15 - 找出数组中所有和为0的三元组。
b.排序+双指针
---
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue;
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left+1]) left++;
while (left < right && nums[right] == nums[right-1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
---
04.接雨水
a.题目
LeetCode 42 - 计算能接多少雨水。
b.双指针解法
---
public int trap(int[] height) {
int left = 0, right = height.length - 1;
int leftMax = 0, rightMax = 0;
int water = 0;
while (left < right) {
if (height[left] < height[right]) {
if (height[left] >= leftMax) {
leftMax = height[left];
} else {
water += leftMax - height[left];
}
left++;
} else {
if (height[right] >= rightMax) {
rightMax = height[right];
} else {
water += rightMax - height[right];
}
right--;
}
}
return water;
}
---
6.2 链表问题
01.反转链表
a.迭代法
---
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
---
b.递归法
---
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) return head;
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
---
02.环形链表
a.判断是否有环
---
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true;
}
return false;
}
---
b.找环的入口
快慢指针相遇后，一个指针回到头部，两指针同速前进，相遇点即为入口。
03.合并链表
a.合并两个有序链表
---
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode curr = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
curr.next = l1;
l1 = l1.next;
} else {
curr.next = l2;
l2 = l2.next;
}
curr = curr.next;
}
curr.next = l1 != null ? l1 : l2;
return dummy.next;
}
---
b.合并K个有序链表
使用优先队列。
04.链表排序
a.归并排序
找中点、分割、合并。
b.快速排序
选择pivot、分割、递归。
6.3 树与图问题
01.二叉树遍历
a.前序遍历
根-左-右，递归或栈实现。
b.中序遍历
左-根-右，BST的中序遍历是有序的。
c.后序遍历
左-右-根。
d.层序遍历
使用队列BFS。
02.二叉树构造
a.从前序和中序构造
---
public TreeNode buildTree(int[] preorder, int[] inorder) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
return build(preorder, 0, preorder.length - 1,
inorder, 0, inorder.length - 1, map);
}
private TreeNode build(int[] pre, int ps, int pe,
int[] in, int is, int ie, Map<Integer, Integer> map) {
if (ps > pe) return null;
TreeNode root = new TreeNode(pre[ps]);
int idx = map.get(pre[ps]);
int leftSize = idx - is;
root.left = build(pre, ps + 1, ps + leftSize, in, is, idx - 1, map);
root.right = build(pre, ps + leftSize + 1, pe, in, idx + 1, ie, map);
return root;
}
---
03.二叉搜索树
a.验证BST
中序遍历应该是递增的。
b.BST的插入和删除
递归实现。
04.图的遍历
a.DFS
使用递归或栈。
b.BFS
使用队列。
c.拓扑排序
Kahn算法或DFS。
6.4 动态规划经典题
01.打家劫舍系列
a.打家劫舍I
---
public int rob(int[] nums) {
if (nums.length == 0) return 0;
int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, prev2 + num);
prev2 = prev1;
prev1 = curr;
}
return prev1;
}
---
b.打家劫舍II
环形数组，分两种情况。
c.打家劫舍III
树形DP。
02.股票买卖系列
a.买卖股票的最佳时机
---
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int maxProfit = 0;
for (int price : prices) {
minPrice = Math.min(minPrice, price);
maxProfit = Math.max(maxProfit, price - minPrice);
}
return maxProfit;
}
---
b.买卖股票的最佳时机II
可以多次交易。
c.买卖股票的最佳时机III
最多两次交易。
03.子序列问题
a.最长上升子序列
O(n²)DP或O(n log n)二分。
b.最长公共子序列
二维DP。
c.编辑距离
三种操作：插入、删除、替换。
04.路径问题
a.不同路径
dp[i][j] = dp[i-1][j] + dp[i][j-1]
b.最小路径和
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
6.5 双指针技巧
01.对撞指针
a.两数之和
有序数组中找两数和。
b.三数之和
固定一个数，双指针找另外两个。
02.快慢指针
a.环检测
快指针走两步，慢指针走一步。
b.链表中点
快指针到末尾时慢指针在中点。
03.滑动窗口
a.最长无重复子串
右指针扩展，左指针收缩。
b.最小覆盖子串
哈希表+双指针。
6.6 哈希表应用
01.计数问题
a.两数之和
HashMap存储已遍历的数。
b.字母异位词
HashMap统计字符频率。
02.去重问题
a.数组去重
HashSet判断重复。
b.链表去重
HashSet记录已出现的值。
03.映射问题
a.同构字符串
HashMap建立映射关系。
b.单词模式
HashMap双向映射。
6.7 并查集与红黑树
01.并查集
a.路径压缩
find时压缩路径。
b.按秩合并
合并时将小树接到大树。
c.应用
连通性判断、最小生成树。
02.红黑树
a.性质
每个节点是红色或黑色，根节点是黑色。
b.Java TreeMap
基于红黑树实现的有序Map。
c.应用
动态维护有序集合。
03.对比
a.并查集
处理集合合并和查询。
b.红黑树
维护有序数据。
7 综合提升
7.1 代码规范与调试
01.代码规范
a.命名规范
变量名、函数名使用驼峰命名，见名知意。
b.缩进与格式
统一使用4空格缩进，保持代码整洁。
c.注释
关键逻辑添加注释，说明算法思路。
02.调试技巧
a.打印调试
在关键位置打印变量值。
b.断点调试
使用IDE的断点功能。
c.单元测试
编写测试用例验证代码正确性。
03.常见错误
a.数组越界
检查索引范围。
b.空指针
判断null值。
c.整数溢出
使用long类型或取模。
04.优化建议
a.时间优化
选择合适的数据结构和算法。
b.空间优化
复用变量，避免不必要的空间开销。
c.代码简洁
避免重复代码，提取公共逻辑。
7.2 边界条件处理
01.常见边界
a.空输入
数组为空、字符串为空。
b.单元素
只有一个元素的特殊情况。
c.极值
最大值、最小值、溢出。
02.数组边界
a.越界检查
访问前检查索引范围。
b.空数组
length == 0的情况。
03.整数边界
a.溢出
使用long或取模。
b.负数
考虑负数的特殊处理。
7.3 性能优化技巧
01.时间优化
a.选择合适算法
根据数据规模选择O(n)、O(n log n)或O(n²)。
b.避免重复计算
使用记忆化、DP。
c.提前终止
剪枝、break。
02.空间优化
a.滚动数组
DP时复用数组。
b.原地算法
不使用额外空间。
03.代码优化
a.减少函数调用
内联小函数。
b.使用位运算
替代乘除法。
7.4 常见陷阱与错误
01.逻辑错误
a.边界条件
忘记处理空数组、单元素。
b.循环条件
< 和 <= 的区别。
02.运行时错误
a.数组越界
访问不存在的索引。
b.空指针
未判断null。
c.栈溢出
递归太深。
03.精度问题
a.整数除法
注意整数除法会截断。
b.浮点数比较
使用epsilon比较。
7.5 模拟考试训练
01.考试准备
a.时间管理
分配好每题时间。
b.题目顺序
先易后难。
c.检查
预留时间检查代码。
02.答题技巧
a.读题
仔细理解题意和样例。
b.分析
确定算法和数据结构。
c.编码
先写框架再填细节。
03.调试技巧
a.样例测试
用样例验证代码。
b.边界测试
测试边界条件。
c.打印调试
输出中间结果。
7.6 面试沟通技巧
01.表达能力
a.清晰描述思路
先说整体思路再说细节。
b.主动沟通
遇到问题及时询问。
02.问题分析
a.理解题意
确认输入输出格式。
b.讨论方案
与面试官讨论优化方向。
03.代码讲解
a.边写边说
解释代码逻辑。
b.复杂度分析
说明时间空间复杂度。
04.应对技巧
a.不会的题
说出部分思路，寻求提示。
b.卡壳时
换个角度思考，尝试暴力解。
7.7 职业发展建议
01.技术提升
a.持续学习
关注新技术、新框架，保持学习热情。
b.深入源码
阅读优秀开源项目的源码，学习设计思想。
c.参与开源
为开源项目贡献代码，提升影响力。
02.面试准备
a.算法刷题
LeetCode、牛客网、AcWing等平台。
b.系统设计
学习分布式系统、微服务架构。
c.项目经验
总结项目中的技术难点和解决方案。
03.职业规划
a.技术路线
深耕技术，成为技术专家。
b.管理路线
转向技术管理，带领团队。
c.创业路线
积累经验后创业。
04.软技能
a.沟通能力
清晰表达技术方案，与团队协作。
b.时间管理
合理安排工作和学习时间。
c.抗压能力
面对困难保持冷静，积极解决问题。
05.学习资源
a.在线课程
Coursera、极客时间、慕课网。
b.技术书籍
算法导论、设计模式、深入理解计算机系统。
c.技术社区
GitHub、Stack Overflow、掘金、CSDN。