大结局——算法常见面试笔试题，不在陷入题海抓住重点

算法题目成百上千，但是每个人的经历是有限的，尤其作为非计算机专业转到想找软件工作的同学，所以我们应该能够抓住面试笔试考查的重点内容，考试嘛就需要突击一点。
基础数据结构
数组、字符串
链表
特点：数据元素个数不确定，经常需要删除或者插入元素而不是经常访问某个元素。
应用：
快慢指针（有时候三个指针）：链表翻转、寻找链表倒数第k个元素、寻找链表中间位置元素、判断链表是否有环。
构建一个虚假的链表头，优点是不需要判断链表是否为空，删除和插入简单了，返回时返回链表头的下一个元素：两个排序链表进行整合；将链表的分离，前半部分是奇数，后半部分是偶数。
栈
特点：后进先出。
基本思想：只关心最后一次的操作，处理完上一次的操作，能在o（1）的时间内查找到更新前的一次操作。
LeetCode：20有效的括号；
LeetCode：739每日温度。
队列
特点：先进先出
应用：广度优先遍历
双端队列
队列的头尾两端能在o（1）的时间内进行数据的查看、添加和删除。常用场景：实现一个长度动态变化的窗口或连续区间
LeetCode：239 滑动窗口的最大值
树
树的问题考查递归算法的熟练程度。
常考的树：普通的二叉树；平衡二叉树；完全二叉树；二叉搜索树；四叉树
遍历：前序遍历（树的创建）、中序遍历（如果是二叉搜索树，遍历结果是排序好的，LeetCode 230
题）、后序遍历（LeetCode 250题）
高级数据结构
优先队列
与普通队列的区别：保证每次取出的元素是队列中优先级最高的，优先级自定义。
最常用的场景：从杂乱无章的数据中按照一定的顺序筛选数据。例如：一个数组的前K大的数据。
本质：本质是一个二叉堆，利用一个数组结构来实现完全二叉树。
LeetCode：347 前K个高频元素
图
最基本知识点：度、有向图、无向图、连通图。
图的算法：图的遍历——深度优先与广度优先；环的检测；拓扑排序；最短路径算法（Dijkstra、Floyd）；连通性相关——求解孤岛数量、旅行商问题、图的着色。
必须掌握的算法：
1.图的存储和表达方式：邻接矩阵、邻接链表
2.图的遍历：深度优先和广度优先 （重要）
基于图的遍历的算法：二分图的检测、环的检测
3.最短路径
4.并查集
LeetCode ：785 判断二分图
前缀树
前缀树叶称字典树，例如：给定一系列构成字典的字符串，需要在字典中找出所有以“ABC”开头的字符
串。使用前缀树。
LeetCode：212 单词搜索2

我已经为大家整理成pdf，方便大家查阅。

公众号“跟小新一起玩编程”获取