准软件工程师：LeetCode练习重点技术方向及解题方法咨询

1. 数组与字符串 #

这是最基础也是面试最频繁的题型，练熟了能快速培养解题手感和逻辑思维。

• 核心主题：双指针、滑动窗口、前缀和/后缀和、字符串匹配、字符统计
• 常见问题与挑战：
  • 滑动窗口的边界收缩时机容易搞混，导致多算或漏算
  • 字符串处理时的索引越界问题，尤其是子串截取场景
  • 前缀和的应用场景判断模糊，比如不知道什么时候用它来优化区间和计算
• 解题思路与方法：
  • 双指针：针对有序数组的两数之和、反转字符串这类问题，用左右指针相向移动，时间复杂度直接降到O(n)
  • 滑动窗口：处理子串/子数组的最长/最短满足条件问题时，先移动右指针扩大窗口，不满足条件时再移动左指针收缩，用变量记录窗口内的状态（比如字符计数、区间和）
  • 前缀和：提前计算前缀和数组，区间[i,j]的和直接用prefix[j+1] - prefix[i]，避免重复遍历计算

2. 链表 #

链表考察指针操作的熟练度，也是很多复杂数据结构的基础载体。

• 核心主题：单链表反转、快慢指针、链表合并、环的检测与入口定位
• 常见问题与挑战：
  • 反转链表时容易断链，递归写法的终止条件和返回值经常出错
  • 快慢指针找中间节点时，奇数/偶数长度链表的边界处理容易遗漏
  • 链表环的入口推导逻辑绕，数学关系理不清
• 解题思路与方法：
  • 迭代反转链表：用prev、curr、next三个指针逐个节点反转，注意提前保存next节点，防止断链
  • 快慢指针：快指针走两步、慢指针走一步，既能找中间节点，也能检测环（相遇则存在环）；找环入口时，相遇后将慢指针移到表头，快慢同速走，再次相遇点就是入口
  • 合并有序链表：用虚拟头节点简化边界判断，逐个比较两个链表节点，把较小的接到结果链表上

3. 哈希表 #

哈希表是「空间换时间」思想的典型应用，是高效查找的核心工具。

• 核心主题：哈希映射（键值对存储）、哈希集合（去重/存在性判断）、前缀哈希
• 常见问题与挑战：
  • 不知道怎么设计合适的键（比如字符异位词的键选择）
  • 空间复杂度权衡不清，比如字符范围有限时用数组比哈希表更高效，但容易想不到
  • 哈希冲突的原理理解模糊，虽然LeetCode不用自己实现，但会影响解题思路
• 解题思路与方法：
  • 存在性判断：直接用哈希集合存储已遍历元素，比如判断数组是否有重复元素
  • 键值对映射：用哈希表记录元素的索引、计数等关联信息，比如两数之和中存目标值-当前数: 当前索引，遍历到当前数时查哈希表是否有对应键
  • 字符计数：针对小写字母类问题，用大小为26的数组代替哈希表，空间更高效，比如判断异位词、有效的字母异位词

4. 树与二叉搜索树（BST） #

树是考察递归和分治思想的典型场景，BST的特有性质能大幅简化问题。

• 核心主题：二叉树遍历（前/中/后序、层序）、BST性质应用、子树问题、路径求和
• 常见问题与挑战：
  • 递归写法的终止条件容易漏写，比如空节点的处理
  • 迭代遍历二叉树的栈/队列操作容易出错，尤其是后序遍历
  • 验证BST时容易忽略「左子树所有节点小于根、右子树所有节点大于根」的严格条件
• 解题思路与方法：
  • 递归遍历：先处理空节点，再按顺序处理左、右子树；BST的中序遍历是有序的，这是很多问题的突破口
  • 迭代遍历：用栈模拟递归过程，前序遍历先压右节点再压左节点；中序遍历先压所有左节点，弹出时处理再压右节点；层序用队列，逐个弹出节点并加入左右子节点
  • BST问题：验证BST时记录前一个节点的值，确保当前节点大于前一个；找第k大元素可以反向中序遍历（右→根→左），计数到k时直接返回

5. 动态规划（DP） #

DP是面试难点，核心考察问题拆解和状态转移的推导能力。

• 核心主题：一维DP、二维DP、背包问题、子序列/子数组问题、状态压缩
• 常见问题与挑战：
  • 状态定义不准确，不知道dp[i]到底代表什么
  • 状态转移方程推导困难，尤其是涉及多状态的场景
  • 边界条件处理不当，比如dp数组的初始化错误
• 解题思路与方法：
  • 三步法：先明确状态定义（比如dp[i]表示前i个元素的最大子数组和），再推导状态转移方程（比如dp[i] = max(dp[i-1] + nums[i], nums[i])），最后确定边界条件（比如dp[0] = nums[0]）
  • 子序列问题：最长递增子序列（LIS）用dp[i]表示以第i个元素结尾的最长递增子序列长度，转移时遍历i之前的所有元素；也可以用贪心+二分优化到O(nlogn)
  • 背包问题：0-1背包用二维dp[i][j]表示前i个物品、容量j时的最大价值，转移方程为dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]] + value[i])，可压缩为一维数组（逆序遍历容量）

6. 回溯算法 #

回溯是暴力搜索的优化，主要考察枚举能力，常见于排列、组合、子集类问题。

• 核心主题：排列、组合、子集、棋盘问题（N皇后、数独）
• 常见问题与挑战：
  • 去重处理不到位，比如组合问题中出现重复解
  • 递归的状态回溯容易遗漏，比如选完元素后没撤销选择
  • 不会设计剪枝条件，导致超时
• 解题思路与方法：
  • 模板框架：定义递归函数，参数包含当前路径、选择起始位置、结果集合；遍历可选元素，做出选择，递归进入下一层，然后回溯（撤销选择）
  • 去重：数组有重复元素时先排序，遍历跳过和前一个相同的元素（同时要确保前一个元素已被处理，避免漏解）
  • 剪枝：比如组合总和问题中，若当前元素大于剩余目标值，直接break，不用继续遍历后面的元素

7. 排序与查找 #

排序是基础算法，查找则考察对有序数据的高效利用能力。

• 核心主题：快速排序、归并排序、二分查找、二分查找变种（找第一个/最后一个满足条件的元素）
• 常见问题与挑战：
  • 二分查找的边界条件（左闭右开/左闭右闭）容易搞混，导致死循环或漏解
  • 快速排序的pivot选择和分区操作容易出错，尤其是处理重复元素时
  • 旋转有序数组的查找逻辑复杂，容易绕晕
• 解题思路与方法：
  • 二分查找：确定区间定义，比如左闭右闭区间[left, right]，终止条件为left > right，mid用left + (right - left) // 2避免溢出；找第一个满足条件的元素时，找到后继续向左收缩右边界
  • 快速排序：选pivot（比如中间元素），分区将小于pivot的放左边、大于的放右边，递归处理左右子数组；重复元素用三路分区（小于、等于、大于pivot的三个区域）
  • 旋转有序数组查找：先判断mid在左半有序区还是右半有序区，再根据target和mid、left的大小关系调整边界

8. 图论基础 #

图论问题频率稍低，但也是大厂面试的常客，核心考察遍历和最短路径。

• 核心主题：图的遍历（DFS、BFS）、最短路径（Dijkstra、BFS）、拓扑排序、并查集
• 常见问题与挑战：
  • 图的表示（邻接表vs邻接矩阵）选择不当，稀疏图用邻接表更高效但容易写错
  • 遍历过程中的环检测逻辑不清，比如拓扑排序判断是否有环
  • Dijkstra算法的堆实现容易出错，尤其是节点距离的更新
• 解题思路与方法：
  • DFS/BFS遍历：用visited数组记录已访问节点，避免重复访问；DFS用递归或栈，BFS用队列；比如岛屿数量问题，遍历每个未访问的陆地，用DFS/BFS标记所有相连陆地
  • 最短路径：无权图用BFS，有权非负图用Dijkstra算法，用小顶堆存储节点和当前距离，每次取出距离最小的节点更新邻接节点的距离
  • 并查集：处理连通性问题（比如朋友圈、岛屿数量），初始化每个节点父节点为自己，find函数做路径压缩，union函数按秩合并集合

内容的提问来源于stack exchange，提问作者Anh Tuan