面试算法学习大纲

以下只包含我了解到出现频率较高的题，仅供参考，以后还会补充的，因为完全刷完leetcode挺难的。

有些题目是我自己面试以及从同学那里了解到的面试原题，面试官也是从题库里抽。

一、基础

1.时间复杂度和空间复杂度

时间复杂度空间复杂度、选择排序、冒泡排序插入排序的时间复杂度二分法的复杂度递归的复杂度

2.O（N*logN）的排序

归并排序

堆和堆排序

快速排序

3.进阶排序算法

桶排序外部排序工程中的排序

4.链表

数据结构以及特点链表的遍历链表的创建、头插法、尾插法链表的反转 剑指Offer24（58同城一面原题）链表相交点 leetcode160两数相加 leetcode2 （快手二面原题）链表中倒数第K个节点 剑指Offer22

5.二叉树

二叉树的三种遍历：递归与非递归二叉树层次遍历以及按层次打印 剑指Offer32（猿辅导面试原题）二叉树的镜像反转 leetcode226二叉树的最近公共祖先 剑指Offer68将二叉树展开为链表 leetcode114填充二叉树右侧指针 leetcode116最大二叉树 leecode654二叉树的重新构建 leetcode105&&106（华为面试原题）二叉树的序列化与反序列化 剑指Offer37

6.图**

图的数据存储结构图的深度优先遍历和广度优先遍历拓扑排序最小生成树单元最短路径

总体来看图好像挺少见的，但是代表不考，除非和图计算相关的工作。

提升

1.哈希表

哈希表的数据结构及用途位图与布隆过滤器并查集（笔试常见题目）LRU实现（滴滴二面原题）高频考点！！必须会！！

2.栈与队列的使用

两个队列实现一个栈（58同城二面原题）两个栈实现一个队列树的层次遍历带有最小值的栈的实现（好未来一面原题）括号匹配相关问题中缀表达式与后缀表达式的转换

3.二分查找

二分查找基础版寻找排序数组中某个数字的左右边界旋转数组中的最小数字 剑指Offer11（美团一面原题）旋转数组中查找某个数字 leetcode33（小米二面原题）在排序数组中查找数字 剑指Offer53（快手一面原题）上面的基础上，如果排序数组中有重复的数字呢？（快手一面原题）0~n-1中缺失的数字 剑指Offer53

4.动态规划（重中之重）

斐波那契数列非递归凑零钱问题小青蛙跳台阶迷路机器人路径 leetcode面试题08.0201背包问题最长递增子序列 leetcode673（华为一面原题）最长回文子串 leetcode5(金山云二面原题)连续子数组最大和 剑指Offer42股票系列问题 剑指Offer63（美团二面原题）

5.分治

快排归并排序

以下几类问题目前来看比较少见，动态规划考的贼多,我认为根本原因是回溯算法普遍都很难，不适合面试的时候写，只适合笔试。但是不排除AT这种T0级别的公司会考。

6.回溯算法**

正则表达式 leetcode10全排列问题 leetcode46&&47

7.贪心算法**

背包问题

8.分支限界法**

总结

​ 以上总结的不一定全面，只是暂时遇到的。算法总体来看内容比较多，也很难，需要花很长时间研究才能掌握，但是为了找工作，必须掌握才行！

​ 算法基础开始，就要认真研究，熟练掌握数据结构，以及常见的几种算法是找工作的基本要求之一，除了上面从算法分类角度分析，也可以从解题方法来分，还包括比如双指针法、滑动窗口、BFS、递归、动态规划等等。希望对大家有一点帮助。也方便日后自己复习。