Grokking LeetCode：准备编程面试的更智能方法

要不要参加 LeetCode？如果你不想在下一次编程面试前练习数百道编程题，该怎么办？

我内心深处其实不太喜欢编程面试，主要是因为它需要我花很多时间准备编程问题。此外，在面试过程中，我必须向评估我的人提供一个合理（即使不是最优）的解决方案，而作为一名软件工程师，我日常生活中根本不需要处理这些事情。

话虽如此，我确实热爱算法和解决编程问题。这对我来说是一项有趣的活动，它能让我很好地锻炼脑力，而且我喜欢花时间去做这件事。在这篇文章中，我想分享一些我多年来积累的经验和技巧，这些经验和技巧让准备编程面试变得既刺激又有趣。

关于我自己：我的软件工程师生涯大约有 20 年，期间我换过五次工作。我参加过大约 30 轮面试，总共超过 120 场。我也有一些面试经验。我参加过 300 多次编程面试和 200 多次系统设计面试。

背景

如果你正在考虑换工作并准备编程面试，你一定会知道 LeetCode。它可能是最大的在线编程面试题库，并且拥有一个活跃的社区，可以与其他工程师讨论算法。每当我有空的时候，我喜欢花时间在 LeetCode 上，尝试解决新的编程问题，或者学习其他人开发的巧妙解决方案。

LeetCode 的问题

LeetCode 最大的挑战之一是缺乏条理性；它有大量的编程题目，让人不知从何入手，也不知该专注于什么。在准备编程面试之前，应该回答多少道题比较合适？我希望看到一个精简的流程，能够指导我并教会我足够的算法技巧，让我在面试中充满自信。我自己是个懒人，不太喜欢回答 500 多道题。

解决方案

人们经常遵循的一种技巧是解决与相同数据结构相关的问题；例如，关注与数组相关的问题，然后是 LinkedList、HashMap、Heap、Tree 或 Trie 等。虽然这确实提供了一些组织，但仍然缺乏连贯性。例如，许多问题可以使用 HashMap 解决，但仍然需要不同的算法技术。我希望看到不仅遵循相同数据结构而且遵循类似算法技术的问题集。我遇到的最好的事情是解决问题的模式，如滑动窗口、快速和慢速指针或拓扑排序等。遵循这些模式帮助我培养了将新问题映射到已知问题的能力。这不仅使整个编码面试准备过程变得有趣，而且更加有条理。

我收集了大约 25 个这样的编程问题模式，我相信它们可以帮助任何人学习这些精妙的算法技巧，并在编程面试中真正发挥作用。这些模式背后的理念是，一旦你熟悉了某个模式，就能用它来解决很多问题。有关这些模式及其相关问题和解决方案的详细讨论，请参阅《深入理解编程面试》。

因此，事不宜迟，让我列出所有这些模式：

1. 滑动窗口
2. 两个指针
3. 快指针和慢指针
4. 合并间隔
5. 循环排序
6. LinkedList 的就地反转
7. 树广度优先搜索
8. 树深度优先搜索
9. 两堆
10. 子集
11. 改进的二分查找法
12. 按位异或
13. 前“K”元素
14. K路合并
15. 0/1 背包
16. 无界背包
17. 斐波那契数列
18. 回文子序列
19. 最长公共子串
20. 拓扑排序
21. Trie 遍历
22. 岛屿数量
23. 反复试验
24. 联合查找
25. 唯一路径

以下是每个模式的简要介绍以及示例问题：

1.滑动窗口

用途：当我们需要处理特定窗口大小的输入数据时，使用此算法 ic 技术。

示例问题：

1. 具有 K 个不同字符的最长子字符串
2. 水果入篮
3. 字符串中的排列

2. 两个指针

用法：在此技术中，我们使用两个指针来迭代输入数据。通常，两个指针以恒定的间隔向相反的方向移动。

示例问题：

1. 对排序数组求平方
2. 荷兰国旗问题
3. 最小窗口排序

3. 快速指针和慢速指针

用法：也称为“龟兔赛跑”算法。在此技术中，我们使用两个指针以不同的速度遍历输入数据。

示例问题：

1. LinkedList 的中间
2. 快乐数字
3. 循环阵列

4. 合并间隔

用法：此技术用于处理重叠区间。给定两个区间（“a”和“b”），这两个区间之间有六种不同的关联方式：

示例问题：

1. （区间交叉）[ https://designgurus.org/path-player?courseid=grokking-the-coding-interview&unit=grokking-the-coding-interview_1628743634893_23Unit ]
2. 冲突的任命
3. 最少会议室数量

5.循环排序

用途：使用此技术解决输入数据位于固定范围内的数组问题。

示例问题：

1. 查找所有缺失的数字
2. 查找所有重复的数字
3. 找出前 K 个缺失的正数

6. LinkedList 的就地反转

用途：此技术描述了一种高效的方法来反转 LinkedList 中一组节点之间的链接。通常情况下，限制在于我们需要在原地执行此操作，即使用现有的节点对象，并且不占用额外的内存。

示例问题：

1. 反转每个 K 元素子列表
2. 旋转 LinkedList

7.树广度优先搜索

用途：顾名思义，该技术用于解决以广度优先搜索的方式遍历树的问题。

示例问题：

1. 二叉树层次遍历
2. 二叉树的最小深度
3. 连接级别顺序兄弟

8. 树深度优先搜索

用途：顾名思义，该技术用于解决以深度优先搜索方式遍历树的问题。

示例问题：

1. 给定序列的路径
2. 计算路径总数

9. 两堆

用途：在许多问题中，我们会遇到给定一组元素，可以将它们分成两部分的情况。我们想知道一部分中的最小元素和另一部分中的最大元素。顾名思义，此技术使用最小堆 (Min-Heap) 查找最小元素，使用最大堆 (Max-Heap) 查找最大元素。

示例问题：
1.求数流的中位数

1. 下一个间隔

10.子集

用法：当问题要求处理一组元素的排列或组合时，使用此技术。

示例问题：

1. 通过改变大小写来排列字符串
2. 独特的通用缩写

11. 改进的二分查找

用法：使用此技术可以有效地搜索已排序的元素集。

示例问题：

1. 数字的上限
2. 双调数组最大值

12. 按位异或

用法：该技术使用 XOR 运算符来操作位来解决问题。

示例问题：

1. 两个单数
2. 翻转和反转图像

1. 前“K”个元素用法：此技术用于查找集合中前/最小/最常出现的“K”个元素。

示例问题：

1. 离原点最近的“K”个点
2. 最大不同元素

14. K路合并

用途：此技术帮助我们解决涉及排序数组列表的问题。

示例问题：

1. M 个排序列表中的第 K 个最小数
2. 排序矩阵中第 K 个最小的数

15. 0/1 背包

用途：此技术用于解决优化问题。使用此技术从给定集合中选择出能够带来最大利润的元素，该集合具有容量限制，并且每个元素只能被选取一次。

示例问题：

1. 相等子集和划分
2. 最小子集和差

16. 无界背包

用途：使用此技术从给定集合中选择可带来最大利润的元素，且容量有限制，并且每个元素可以被挑选多次。

示例问题：

1. 棒材切割
2. 找零

17.斐波那契数列

用途：使用此技术解决遵循斐波那契数列的问题，即每个后续数字都是根据最后几个数字计算出来的。

示例问题：

1. 楼梯
2. 窃贼

18. 回文子序列

用途：该技术用于解决与回文序列或字符串相关的优化问题。

示例问题：

1. 最长回文子序列
2. 字符串中最少删除几行使其成为回文

19. 最长公共子串

用法：使用此技术来查找字符串/序列或字符串/序列集的最佳部分。

示例问题：

1. 最大和递增子序列
2. 编辑距离

20. 拓扑排序

用法：使用此技术来找到相互依赖的元素的线性排序。

示例问题：

1. 任务调度
2. 外星人词典

21. Trie 遍历

用法：使用涉及创建或遍历 Trie 数据结构的技术。

示例问题：

1. 字典中最长的单词
2. 回文对

22. 岛屿数量

用法：使用此技术遍历二维数组并找到一组连通的元素。

示例问题：

1. 不同岛屿的数量
2. 岛屿最大面积

23. 反复试验

用法：使用此技巧遍历数组以找到所需的最佳元素。遍历过程以反复试验的方式进行。

示例问题：

1. 找到第 K 个最小对距离
2. 最小化到加油站的最大距离

24. 联合查找

用途：使用此技术解决需要将给定的一组元素划分为多个不重叠的子集的问题。

示例问题：

1. 省份数量
2. 二分图

25. 独特路径

用法：使用此技术来找到遍历多维数组的不同/最佳方法。

示例问题：

1. 查找唯一路径
2. 地下城游戏

结论

不管你喜不喜欢，LeetCode 这类题目几乎是所有编程面试的必考题，所以每个软件开发者都应该在面试前练习一下。他们唯一的选择就是充分准备，并通过专注于底层问题模式来学习解决问题。在《深入理解编程面试》和《深入理解动态规划编程面试》中，了解更多关于这些模式和样题的信息。

查看设计大师关于编码和系统设计面试的一些有趣的课程。

阅读有关系统设计编码面试的更多信息：

1. 掌握系统设计面试：完整指南
2. 2023 年系统设计面试必读的 7 篇论文
3. 系统设计面试生存指南（2023）：准备策略和实用技巧
4. Grokking LeetCode：准备编程面试的更智能方法
5. 14 个最受欢迎的亚马逊编程面试问题