面试题速查表

本文档整理了《程序员面试金典》中常见题型的解题模板和技巧，方便快速查阅。

数据结构速查

数组与字符串

技巧	适用场景	时间复杂度
双指针	有序数组、回文判断、滑动窗口	O(n)
快慢指针	环检测、中点查找	O(n)
前缀和	子数组和、区间求和	O(n) 预处理
位图	字符去重、状态压缩	O(n)
哈希表	两数之和、字符统计	O(n)

常用操作模板：

// 双指针：有序数组两数之和
int left = 0, right = arr.length - 1;
while (left < right) {
    int sum = arr[left] + arr[right];
    if (sum == target) return new int[]{left, right};
    else if (sum < target) left++;
    else right--;
}

// 滑动窗口：最长无重复子串
int[] count = new int[128];
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
    count[s.charAt(right)]++;
    while (count[s.charAt(right)] > 1) {
        count[s.charAt(left++)]--;
    }
    maxLen = Math.max(maxLen, right - left + 1);
}

链表

技巧	适用场景	注意事项
快慢指针	环检测、中点、倒数第k个	快指针先走k步或每次走两步
虚拟头节点	涉及头节点删除	简化边界处理
反转链表	回文判断、链表重排	注意保存next指针
双链表合并	排序链表、交错合并	使用虚拟头节点

常用操作模板：

// 反转链表
ListNode prev = null, curr = head;
while (curr != null) {
    ListNode next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
}
return prev;

// 快慢指针找中点
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow 是中点

// 检测环
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;

栈与队列

数据结构	特点	典型应用
栈	LIFO	括号匹配、表达式求值、单调栈
队列	FIFO	BFS、层序遍历
双端队列	两端操作	滑动窗口最大值
优先队列	自动排序	Top K、合并有序链表

常用操作模板：

// 单调栈：下一个更大元素
int[] result = new int[nums.length];
Arrays.fill(result, -1);
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < nums.length; i++) {
    while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
        result[stack.pop()] = nums[i];
    }
    stack.push(i);
}

// 用栈实现队列
Stack<Integer> inStack = new Stack<>();
Stack<Integer> outStack = new Stack<>();

void push(int x) { inStack.push(x); }

int pop() {
    if (outStack.isEmpty()) {
        while (!inStack.isEmpty()) outStack.push(inStack.pop());
    }
    return outStack.pop();
}

树与图

遍历方式	特点	应用场景
前序遍历	根-左-右	复制树、序列化
中序遍历	左-根-右	BST有序遍历
后序遍历	左-右-根	计算高度、删除树
层序遍历	BFS	最短路径、层级信息

常用操作模板：

// DFS 遍历二叉树
void dfs(TreeNode root) {
    if (root == null) return;
    // 前序：处理 root
    dfs(root.left);
    // 中序：处理 root
    dfs(root.right);
    // 后序：处理 root
}

// BFS 层序遍历
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        TreeNode node = queue.poll();
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

// BST 验证
boolean isValidBST(TreeNode root, Integer min, Integer max) {
    if (root == null) return true;
    if ((min != null && root.val <= min) || (max != null && root.val >= max)) {
        return false;
    }
    return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
}

// LCA 最近公共祖先
TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;
    TreeNode left = lca(root.left, p, q);
    TreeNode right = lca(root.right, p, q);
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

算法技巧速查

位运算

操作	代码	说明
判断奇偶	`(n & 1) == 1`	最低位为1则是奇数
交换两数	`a ^= b; b ^= a; a ^= b;`	不用临时变量
取低位k位	`n & ((1 << k) - 1)`	获取二进制低k位
判断2的幂	`(n & (n - 1)) == 0`	只有一个1
统计1的个数	`while (n != 0) { n &= n - 1; count++; }`	Brian Kernighan算法

常用操作模板：

// 不用+号实现加法
int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;  // 进位
        a = a ^ b;                  // 无进位加法
        b = carry;
    }
    return a;
}

// 统计位1的个数
int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;  // 清除最低位的1
        count++;
    }
    return count;
}

二分查找

变体	条件	说明
标准二分	`arr[mid] == target`	精确查找
找第一个等于	`arr[mid] >= target`	左边界
找最后一个等于	`arr[mid] > target`	右边界-1
旋转数组	比较arr[mid]与arr[left]	判断有序区间

通用模板：

// 查找左边界
int leftBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] >= target) right = mid;
        else left = mid + 1;
    }
    return left;  // 第一个 >= target 的位置
}

// 查找右边界
int rightBound(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] > target) right = mid;
        else left = mid + 1;
    }
    return left - 1;  // 最后一个 <= target 的位置
}

动态规划

问题类型	状态定义	转移方程
最长子序列	`dp[i]` 以i结尾的最长	依赖前面的状态
背包问题	`dp[i][j]` 前i个容量j	选或不选
区间DP	`dp[i][j]` 区间[i,j]	枚举分割点
编辑距离	`dp[i][j]` 前i变前j	插删改三种操作

常用模板：

// 01背包
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
    for (int j = capacity; j >= weight[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 完全背包（每种物品无限）
int[] dp = new int[capacity + 1];
for (int i = 0; i < n; i++) {
    for (int j = weight[i]; j <= capacity; j++) {
        dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 最长递增子序列（O(n log n)）
int[] dp = new int[n];
int len = 0;
for (int num : nums) {
    int i = Arrays.binarySearch(dp, 0, len, num);
    if (i < 0) i = -(i + 1);
    dp[i] = num;
    if (i == len) len++;
}

// 最长子串/子数组
int[] dp = new int[n];  // dp[i] 以i结尾的最长
dp[0] = 1;
for (int i = 1; i < n; i++) {
    if (满足条件) dp[i] = dp[i - 1] + 1;
    else dp[i] = 1;
}

回溯算法

问题类型	特点	剪枝策略
子集	每个元素选或不选	无需剪枝
排列	有序，用过不能再用	used数组
组合	无序，需要去重	排序+跳过重复
棋盘问题	约束条件多	提前判断合法性

通用模板：

// 子集问题
void backtrack(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]);
        backtrack(nums, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

// 排列问题（有重复元素）
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] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

// N皇后
void backtrack(char[][] board, int row, List<List<String>> result) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }
    for (int col = 0; col < board.length; col++) {
        if (isValid(board, row, col)) {
            board[row][col] = 'Q';
            backtrack(board, row + 1, result);
            board[row][col] = '.';
        }
    }
}

排序算法

算法	时间复杂度	空间复杂度	稳定性	适用场景
快速排序	O(n log n) 平均	O(log n)	不稳定	通用排序
归并排序	O(n log n)	O(n)	稳定	需要稳定性
堆排序	O(n log n)	O(1)	不稳定	空间受限
计数排序	O(n + k)	O(k)	稳定	范围小的整数

快速排序模板：

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);
}

int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left;
    for (int j = left; j < right; j++) {
        if (arr[j] < pivot) {
            swap(arr, i++, j);
        }
    }
    swap(arr, i, right);
    return i;
}

特殊问题技巧

滑动窗口

适用：连续子数组、子串问题

// 滑动窗口框架
int left = 0, right = 0;
while (right < n) {
    // 扩大窗口
    window.add(arr[right]);
    right++;
    
    // 收缩窗口
    while (需要收缩) {
        window.remove(arr[left]);
        left++;
    }
    
    // 更新结果
}

前缀和与差分

适用：区间求和、区间修改

// 一维前缀和
int[] prefix = new int[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + arr[i];
}
// 区间[l, r]的和 = prefix[r + 1] - prefix[l]

// 差分数组（区间修改）
int[] diff = new int[n + 1];
void add(int l, int r, int val) {
    diff[l] += val;
    diff[r + 1] -= val;
}
void apply() {
    for (int i = 0; i < n; i++) {
        diff[i + 1] += diff[i];
    }
}

单调栈与单调队列

适用：下一个更大元素、滑动窗口最大值

// 单调栈：找下一个更大元素
int[] nextGreater(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Stack<Integer> stack = new Stack<>();
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

// 单调队列：滑动窗口最大值
int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> deque = new LinkedList<>();
    int[] result = new int[nums.length - k + 1];
    for (int i = 0; i < nums.length; i++) {
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        deque.offerLast(i);
        if (i >= k - 1) result[i - k + 1] = nums[deque.peekFirst()];
    }
    return result;
}

并查集

适用：连通性、等价类问题

class UnionFind {
    int[] parent, rank;
    
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
    
    void union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else { parent[py] = px; rank[px]++; }
    }
}

题目分类索引

数组与字符串

题目	核心技巧
判定字符是否唯一	位图 / Set
判定是否互为字符重排	计数 / 排序
URL化	从后向前填充
回文排列	位运算统计奇偶
一次编辑	双指针
字符串压缩	遍历统计
旋转矩阵	两次翻转 / 四角交换
零矩阵	标记数组 / 首行首列标记
字符串轮转	子串判断

链表

题目	核心技巧
移除重复节点	Set / 双重循环
返回倒数第k个节点	快慢指针
删除中间节点	复制下一个节点
分割链表	双链表拼接
链表求和	模拟加法
回文链表	快慢指针 + 反转
链表相交	双指针交换
环路检测	快慢指针

树与图

题目	核心技巧
节点间通路	BFS / DFS
最小高度树	二分递归
特定深度节点链表	BFS 层序遍历
检查平衡性	递归计算高度
合法二叉搜索树	中序遍历 / 递归验证
后继者	BST 性质
首个共同祖先	递归查找
求和路径	前缀和

动态规划

题目	核心技巧
三步问题	简单DP
幂集	回溯 / 位运算
括号生成	回溯
八皇后	回溯 + 剪枝
堆箱子	LIS 变形
布尔运算	区间DP

复杂度速查

时间复杂度

复杂度	规模	示例算法
O(1)	无限	哈希表查找
O(log n)	10^18	二分查找
O(√n)	10^12	质因数分解
O(n)	10^7	遍历、哈希
O(n log n)	10^6	排序
O(n²)	10^4	双重循环
O(n³)	500	三重循环
O(2^n)	25	子集枚举
O(n!)	12	全排列

空间复杂度选择原则

优先使用 O(1) 额外空间
递归注意栈空间 O(n)
大数组优先考虑滚动数组
DP 优先一维优化

常见错误避免

边界条件

空数组、空字符串、空链表
单元素、两元素情况
负数、零的处理
整数溢出（用 long）

细节问题

循环变量边界：< vs <=
数组下标从0还是1开始
深拷贝 vs 浅拷贝
字符串比较用 equals()

时间空间权衡

哈希表：空间换时间
预处理：前期投入换取查询优化
记忆化：递归+缓存
滚动数组：压缩空间

面试技巧

解题步骤

理解题意：确认输入输出、边界条件
分析思路：暴力→优化→最优
编写代码：先写框架，再填细节
测试验证：手动跑几个用例
复杂度分析：时间、空间

沟通技巧

边想边说，展示思考过程
不确定时主动询问
提出多种解法并比较
承认不知道，但要展示学习能力

代码规范

变量命名有意义
适当添加注释
保持代码整洁
注意边界处理

数据结构速查​

数组与字符串​

链表​

栈与队列​

树与图​

算法技巧速查​

位运算​

二分查找​

动态规划​

回溯算法​

排序算法​

特殊问题技巧​

滑动窗口​

前缀和与差分​

单调栈与单调队列​

并查集​

题目分类索引​

数组与字符串​

链表​

树与图​

动态规划​

复杂度速查​

时间复杂度​

空间复杂度选择原则​

常见错误避免​

边界条件​

细节问题​

时间空间权衡​

面试技巧​

解题步骤​

沟通技巧​

代码规范​

数据结构速查

数组与字符串

链表

栈与队列

树与图

算法技巧速查

位运算

二分查找

动态规划

回溯算法

排序算法

特殊问题技巧

滑动窗口

前缀和与差分

单调栈与单调队列

并查集

题目分类索引

数组与字符串

链表

树与图

动态规划

复杂度速查

时间复杂度

空间复杂度选择原则

常见错误避免

边界条件

细节问题

时间空间权衡

面试技巧

解题步骤

沟通技巧

代码规范