Leetcode HOT面试总结

面试题目类型

双指针

二叉树

链表

滑动窗口

堆&栈

回溯

所有回溯问题，都可以抽象成在一个“决策树”上进行深度优先搜索（DFS）的过程。这个过程包含三个关键部分：

  1. 路径（Path）：已经做出的选择。在全排列问题中，就是当前已经选了哪几个数字，构成了一个不完整的排列。我们通常用一个 List 或 Stack 来记录。
  2. 选择列表（Choices）：当前可以做的选择。在全排列问题中，就是那些还没有被选过的数字。
  3. 结束条件（End Condition）：当“选择列表”为空，或者说“路径”的长度达到了要求（比如等于原数组长度），就意味着我们走到了决策树的叶子节点，找到了一个完整的解。此时需要把“路径”存入最终结果集。

比如说一个全排列的问题，抽象出来就是

我们需要先从选择列表中将其加入到路径之中，然后标记为已选

继续递归

下一层递归返回后，为了能去尝试其他的，就将这次的撤销，就是我们说的回溯，然后移除，标记为没有启用