编码模式增强了我们“将新问题映射到已知问题的能力”。
通过专注于编码模式,可以更轻松地准备编码面试。每个软件工程师都应该学习诸如滑动窗口、两个指针、两个堆等编码模式。通过这样做,软件工程师将能够培养“将新问题映射到现有问题”的技能。在这篇文章中,我们将了解哪些编码模式对软件工程师的投资回报率最高。
Grokking the Coding Interview根据解决问题所需技术的相似性,列出了 18 种编码问题模式。该课程的想法是教授著名的编码模式,这样一旦有人熟悉了一种模式,他们就能够用它解决几十个问题。
LeetCode 问题分布
LeetCode (LC) 是最大的编码问题库,包含超过 2k 多个问题。LC 上的每个问题都可以标记一个或多个主题。这些主题要么是Array、HashTable、Tree等数据结构,要么是Greedy、Divide and Conquer、Sorting等算法技术,或者是Sliding Window、Depth First Search、Topological Sort等编码模式。这里是LC 问题的主题分布:

最上面的主题是 Array 有 1142 个问题,其次是 String 有 549 个问题,依此类推。让我们仔细看看每个主题类别,即数据结构、算法和编码模式。
具有最佳投资回报率的顶级数据结构
以下是投资回报率最高的顶级数据结构:
- 数组(1142 题)
- 字符串 (549)
- 哈希表 (392)
- 树 (191)
- 矩阵 (171)
- 堆栈 (128)
- 堆或优先队列 (107)
- 图表 (102)
- 链表 (69)
- 特里 (44)
具有最佳投资回报率的顶级算法技术
以下是投资回报率最高的顶级算法技术:
- 动态规划 (383)
- 分拣 (253)
- 贪心 (248)
- 二进制搜索 (186)
- 回溯 (91)
- 递归 (44)
- 分而治之 (38)
具有最佳投资回报率的顶级编码模式
以下是投资回报率最高的顶级编码模式:
- 深度优先搜索 (250)
- 广度优先搜索(198)
- 二进制搜索 (186)
- 两个指针 (147)
- 滑动窗 (72)
- 单调堆栈 (44)
- 联合查找 (63)
- 记忆 (32)
- 拓扑排序 (28)
- 段树 (27)
具有最高投资回报率的最佳编码模式
结合上述数据中的所有类别,以下是具有最高 ROI 的最佳编码模式/技术列表:
1.两个指针(数组、字符串、快慢指针)
这种模式涵盖了大量与数组和字符串相关的问题,它们是标记最高的数据结构。快慢指针可以很容易地理解为两个指针模式的变体。
2.滑动窗口(数组、字符串、哈希表)
滑动窗口涵盖了与顶级数据结构(如数组、字符串和哈希表)相关的大部分问题。
3.树和图深度优先搜索(矩阵遍历)
大多数树和图问题都可以使用深度优先搜索 (DFS) 来解决。矩阵遍历,也是基于 DFS 的模式,涵盖了大多数与矩阵相关的问题。
4.树和图广度优先搜索(队列、子集、矩阵遍历、拓扑排序)
广度优先搜索 (BFS) 是一种非常方便的模式。BFS 的模式(例如子集、矩阵遍历和拓扑排序)涵盖了很多问题。
5.二分查找(数组)
二进制搜索及其变体用于解决大量的编码问题。
6.区间合并
虽然与Interval Merge相关的问题并不多,但这些问题在编码面试中却经常出现。
7.递归/回溯
回溯和递归用于解决范围广泛的问题。强烈建议掌握这些技术。
结论
大多数编程面试都包括 LeetCode 类型的问题。软件工程师在面试前练习这样的编码问题。通过巧妙地准备并专注于问题模式,可以获得最高的投资回报。您可以在Grokking the Coding Interview和Grokking Dynamic Programming for Coding Interviews中了解有关这些模式和相关问题的更多信息。