面试刷题总结

发表于 更新于 Disqus：

题目类型

字符串/数组

字符串是数组的一个特例，常用处理方案是一致的。思路包括：

  1. 双指针（首尾）
  2. 回溯
  3. 贪心/dp
  4. Trie树
  5. 二分搜索（各种变种）

特殊题型

  1. 旋转数组：多次反转
  2. 判断是否存在，超大规模使用布隆过滤器（能精准判断不存在，但是不能精准判断存在）
  3. 矩阵相关：注意遍历的起始位置，根据矩阵的特点从右上角、左下角开始能迅速计算出目标

堆

在Java中通过PriorityQueue实现最大/最小堆（默认是最小）
python中通过heapq这个库来实现数组堆化，当然也可以用queue.PriorityQueue
堆可以用来解决topK问题

栈

栈通常用来解决优先级问题，一系列的操作中，有些优先级高，有些优先级低。可以将优先级低的先压栈，取出优先级高的进行处理。

队列

队列可以用来解决二叉树层次遍历问题。

链表

  1. 双指针（快慢）
    1. 快慢指针能相遇则链表有环
    2. 相遇点和链表头各设一个指针，同时前进，交点即环的入口
    3. 两个链表的问题，可以根据长度差X设置两个指针，长链表指针先走X步

二叉树

概念：
1. 满二叉树：除了叶子节点，所有节点都有两个子节点的二叉树；层数为K，节点数为2^K - 1个
2. 完全二叉树：最后一层节点从左到右连续，其他层节点达到最大值。满二叉树是完全二叉树的特殊情况
3. 二叉搜索树(BST)：左子树的节点均小于根结点，右子树的节点均大于根结点，子节点也是二叉搜索树
1. 中序遍历BST得到排序后的数组；
2. 反向转换：取mid作为根，左边递归是左子树，右边递归是右子树
3. 二叉搜索树的所有操作复杂度为O(h)，h为树的高度，当树高度不平衡时，退化为O(n)，即链表操作
4. 平衡二叉树：左右子树高度差不超过1，且子节点都是平衡二叉树
5. AVL：自平衡二叉搜索树
6. 红黑树：也是自平衡二叉搜索树，理论性能优于AVL树 => 由于十分难写，很多实现采用skiplist代替
7. 区间树/线段树：二叉搜索树的元素不再是元素，而是某个区间
8. B树：自平衡多叉树，高度较低，适用于磁盘存储
9. R树：一般用于存储空间位置信息

解法：
1. 递归。由于二叉树本身就是递归结构，所以几乎所有的解法都需要递归
2. 遍历：前序、中序、后序都是深度优先搜索（DFS），使用递归即可；层次遍历是广度优先搜索（BFS），使用队列辅助完成；
3. 序列化：用层次遍历即可，先把root放进去然后分别放入其子节点

排序和搜索

概念：
1. 经典排序算法：插入、选择、冒泡，复杂度都是O(n^2)，实际上一般并不单独使用
2. 普通排序算法的最佳复杂度就是O(nlgn)，一般我们使用快排，但是它的最差复杂度是O(n^2)，相比之下归并排序具有更稳定的复杂度但是却需要占用更多的空间
3. 如果需要稳定排序，一般还是用归并排序
4. 特殊情况下，可以达到线性事件排序，如桶排序、基数排序等
5. 求Kth最大/小的值，一般采用类似快速排序的切割算法，期望复杂度是O(n)，C++中可以用STL中的nth实现
6. 二分搜索的前提是数组已经排好序

动态规划

dp问题没有固定的解法，一般用于最优化问题（统筹规划），需要根据观察列出dp方程，并找到剪枝方式，从而简化求解过程。
dp方程的个数取决于状态的个数，自变量的个数则需要分析题意。

使用动态规划将问题划分为若干个子问题，这些子问题之间相互重叠，通过记忆化查表的方式简化这些计算，动态规划一般分为自底向上和自顶向下两种设计方式。
贪心算法则是对子问题直接作出贪心选择，从而简化计算，贪心算法一般都是自顶向下的。

图论

掌握dfs，bfs和并查集
并查集主要是join和search两个操作
最短路径算法
最小生成树