
学习数据结构,需要先熟练掌握插入、删除和查找等基本操作,
这些基本操作往往是解决很多面试题的关键。例如,如果我们熟练掌
握了前缀树的插入和查找操作,那么很多与字符串前缀相关的问题都
很容易解决。
同样,对于基础算法我们也需要深刻理解它们的原理及其实现代
码。例如,二分查找通常只需要10行左右的代码就能实现,我们要理
解它的循环条件的比较运算符什么时候用“<”,以及什么时候用
“<=”,确定下一步查找前半部分或后半部分的标准是什么。在理
解了这些原理之后,不管面试题如何变化,最终解决问题的代码都大
同小异。
学习数据结构,还要深刻理解每种数据结构的特点及其适用场
景,这样才能在面试过程中合理选择数据结构解决问题。例如,哈希
表是时间效率非常高的数据结构,它的插入、删除和查找操作的时间
复杂度都是
O
(1)。虽然哈希表的时间效率非常高,但并不是所有的
问题都能用哈希表来解决。如果存储的元素是字符串,并且需要根据
字符串的前缀进行查找,那么前缀树是更好的选择。如果存储的元素
是数值,并且解决问题需要知道数据集合中的最大值或最小值,那么
堆可能是更好的选择。如果需要对动态数据集合排序,并且需要根据
数值的大小进行查找,那么平衡的二叉搜索树(Java中的TreeSet或
TreeMap)可能是更好的选择。
同样,学习算法也要理解每种算法的特点及其适用场景。例如,
回溯法和动态规划适合解决的问题看起来很类似。如果解决一个问题
需要多个步骤,并且每个步骤都面临多个选择,那么我们可以考虑使
用回溯法或动态规划来解决问题。如果要求列举出问题所有的解,那
么我们应该采用回溯法来解决问题。如果只是要求计算某个最优解
(通常是最大值或最小值)或计算解的数目,那么我们应该采用动态
规划来解决问题。
本书的关注点是算法面试,因此,和常规的算法类书籍相比,本
书更加注重面试准备的实用性。本书注重总结常用的解题思路。例
如,如果面试题提到与二叉树相关的概念,那么我们可以尝试用广度