练习是准备算法面试的最好方式。下面这个清单提炼几十个有代表性的问题,我把它们分成5周的时间表。
当你练习的时候,建议你把它当作一次真正的算法面试,并且在提交之前彻底检查一遍。甚至可以考虑手动提出一些测试用例并运行它们来验证其正确性!
在第一周,我们将从简单的开始,混合使用关于数组和字符串的简单和中等问题。数组和字符串是在面试中最常见的问题类型; 熟悉它们将有助于建立强有力的基础,更好地处理更难的问题。
第二周的重点是关于链表、字符串和基于矩阵的问题。我们的目标是学习处理链表、遍历矩阵和序列分析(数组/字符串)的常用例程,比如滑动窗口。
- 反向链表
- 检测链表中的循环
- 盛载最多水份的容器
- 在旋转排序数组中查找最小值
- 最长重复字符替换
- 无重复字符的最长子字符串
- 最小窗口子字符串
- 离岛数目
- 从列表结束处删除第 n 个节点
- 回文子字符串
- 太平洋大西洋水流
第三周的重点是树、图和堆等非线性数据结构。您应该熟悉各种树遍历算法(按顺序、前顺序、后顺序)和图遍历算法,如广度优先搜索和深度优先搜索。根据我的经验,使用更高级的图算法(Dijkstra 和 Floyd-Warshall)是相当罕见的,通常也是不必要的。
第四周积累了前几周的知识,但问题的难度增加了。需要在更高级的数据结构上获得更多的实践,例如(但不仅限于)堆和树。
- 添加和搜索 Word
- 实现 Trie (前缀树)
- 另一棵树的子树
- 一个 BST 中最小的元素
- 英国夏令时最近公共祖先
- 合并 k 排序列表
- 从数据流中找出中位数
- 插入间隔
- 最长的连续序列
- Word 搜索 II
第5周主要讨论动态编程(DP)问题。DP并不真正适用于实际场景,一般面试测评会遇到类似的问题。DP 问题可能很难掌握,最好的方法就是-练习!
从问题模式的角度而不是从数据结构的角度来进行练习,解决一类问题,而非套用数据结构。