非算法工程师面试必问的算法面试理论 顶
【推荐】2019 Java 开发者跳槽指南.pdf(吐血整理) >>>
非算法方向的你
面了多少次试？
最后，因为不懂算法，
死在了半路上？
这些痛，
作为技术创新型公司的小编——个推君
怎么会不懂？
为此，个推君特请了我司经验丰富的面试官
为你奉上一份热乎的面试宝典。
宝典可不是面试题哦
仅送给想认真钻研的童鞋
帮大家梳理知识点
让大家举一反三，
offer拿到手软！
注：此处建议大家使用 C 语言来学习数据结构与算法。
一、数据结构
数据结构是算法的基础。大家需要对数据结构有个清晰的概念，因为大部分的算法题均需要带入数据结构的概念来处理。科班出身的程序员或多或少学习过数据结构。我们推荐大家可以重温下这本书，温故而知新。
时间复杂度与空间复杂度
在说算法之前和大家科普两个重要的理论知识：算法的时间复杂度与空间复杂度。
时间复杂度
算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n))。它表示随着 输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述，并且会忽略常量部分。
举个例子
int aFunc(void) { printf("Hello, World!\n"); // 需要执行 1 次 return 0; // 需要执行 1 次}调用此方法，printf("Hello, World!\n"); 执行了一次，那么我们记作 T(n) = O(1)
int aFunc(int n) {
for(int i = 0; i<n; i++) {
// 需要执行 (n + 1) 次
printf("Hello, World!\n");
// 需要执行 n 次
}
return 0;// 需要执行 1 次}此处输出语句被执行了 n 次，那么我们记作 T(n) = O(n)
再看一个
int aFunc(int n) {
for(int i = 0; i<3*n; i++) {
for(int j = 0; j<2*n; i++) {// 需要执行 (n） 次
printf("Hello, World!\n"); // 需要执行 n 次
}
return 0;
}此处输出语句被执行了 (3n)(2*n) 次,f（n）=6n^2,由于我们是忽略常量的，所以 T(n)=O(n^2)
空间复杂度
是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。
int i = 1;
int j = 2;
++i;
j++;
int m = i + j代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。
int[] m = new int[n];
for(i=1; i<=n; ++i){
j = i;
j++;
}这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，这段代码的2-6行，虽然有循环，但没有再分配新的空间。因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)。
字符串
字符串或串(String)是由数字、字母、下划线组成的一串字符。一般记为 s=“a1a2···an”(n>=0)。它是编程语言中表示文本的数据类型。在程序设计中，字符串（string）为符号或数值的一个连续序列，如符号串（一串字符）或二进制数字串（一串二进制数字）。
这个不多说了，敲代码的都懂：一切皆可字符串。
数组
所谓数组，是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素，有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。
在 C 语言中，数组可分为一维数组、二维数组、多维数组等。而涉及到怎么创建数组这边就不细讲了，因为各个语言的的申明方法以及使用方法都不太相同。
二维数组结构图
举例
1、int a[10]; 说明整型数组a，有10个元素。若要表示第10个元素，则使用a[9]。第一个则是a[0]。
2、float b[10],c[20]; 说明实型数组b，有10个元素，实型数组c，有20个元素。
3、char ch[20]; 说明字符数组ch，有20个元素。
链表（Node）
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表是我们比较常用的数据结构，如果在编程的过程中，需要进行频繁 增&删 操作的，优先使用链式存储结构。链表分为我们常见的单链表，还有双链表以及循环链表。
单链表结构体
typedef struct LNode{
int data; //data中存放结点数据域（默认是int型）
struct LNode *next; //指向后继结点的指针}LNode;单链表结构图
栈（Stack）
栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。
栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。栈是一种先进后出的的数据结构，有入栈和入栈两种常见操作。
结构体
typedef struct Stack{ // 栈
PNODE pTop;
PNODE pBottom;
}STACK,*PSTACK;结构图
队列（Queue）
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列是一种先进先出的的数据结构，有入队和出队两种常见操作，一般有顺序队列，双向队列，循环队列。
结构体
typedef struct{
ELemType data[MaxSize];
int front, rear;
}SqQueue;结构图
树
它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
树是一个大类，树下面又分 二叉树，平衡二叉树，AVL 树，字典树，哈夫曼树，红黑树，b 树等，考到最多的是二叉树与红黑树。
结构体
下图是二叉树的结构体定义。
typedef struct TNode{
TElemType data;
struct TNode *lchild,*rchild;
}TNode,*Tree;二叉树结构图
图（Graph）
图是由顶点的有穷非空集合和顶点之间边的集合组成， 通常表示为: G（V，E）， 其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。顶点有时也称为节点或者交点，边有时也称为链接。
结构图
二、算法和数据操作
粗略地讲了下数据结构的理论，终于要进入正餐了。算法题大致分为以下几大类。还有一些小类，比如位运算、回溯算法等就不一一举例了。
查找
查找也可以叫做搜索，这是算法分类里面最最最普通的一个模块，查找分为 线性查找、数表查找、哈希查找。
掌握程度：查找类型的题目较为丰富，每一种数据结构都有自己的查找类型的经典算法，比如 数组对应的最小值/最大值查找、字符串对应的关键字查找、链表对应的回环判断等、树对应的深度/广度优先，二叉树对应的 前/中/后 遍历，最 小/大 堆查找 。这些本质是都是和查找算法相关的。
排序
说到排序，大家应该都非常熟悉了。排序分为内排序和外排序，因为外排序的出现频率较低，这边只进行内排序的分析。我们常见的选择、冒泡、快排均属于内排序。
具体的算法可以搜索百度。掌握程度：除了基数排序和希尔排序，其他几个排序算法均需要可以默写算法的程度，接着要进行实战操作，刷完下面的这些题目，对排序算法会有个清晰的理解。
推荐范例：
https://leetcode.com/tag/sort/
递归
讲到递归的时候，我们在使用的过程中，特别要对递归终止的条件有个清晰的把握，不然很容易陷入死循环当中
掌握程度：链接里面的就 14 道题目，我们建议全部刷一遍。值得注意的是，递归的题目一般来说会有多种解法。
推荐范例：
https://leetcode-cn.com/tag/recursion/
动态规划
动态规划，又名DP算法（取自其Dynamic Programming的缩写）。它最初是运筹学的一个分支，用来求解决策过程最优化的数学方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题。该方法所耗时间往往远少于朴素解法。
动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分的问题（即子问题），再根据子问题的解来得出原问题的解。动态规划往往用于优化递归问题，例如斐波那契数列。如果我们运用递归的方式来求解会重复计算很多相同的子问题，而用动态规划的思想则可以减少很多计算量。比如我们常见的爬楼梯的问题（https://blog.csdn.net/xiaoyyidiaodiao/article/details/73621545），但需要注意这个问题一般有多种解法。
掌握程度： 这类问题的相似度非常高，希望大家可以达到触类旁通的境界 推荐范例：
买卖股票的最佳时机
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
爬楼梯
https://leetcode-cn.com/classic/problems/climbing-stairs/description/
贪心算法
贪心算法（又称贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，它不从整体最优上加以考虑，所做出的是在某种意义上的局部最优解。比如我们常见的爬楼梯问题。
掌握程度： 如果不是面试算法工程师的话，建议刷完 10 道相对简单的题目即可。 推荐范例：贪心算法范例
https://leetcode-cn.com/tag/greedy
图
图这块知识相对比较深奥，如果不是从事这方面研究的，我们掌握理论和一些经典的算法即可。比如 普利姆算法，克鲁斯卡尔算法等，这些都是非常经典的算法。我们需要知道经典算法的设计逻辑以及优缺点。
掌握程度： 熟悉各类存储结构，精通经典算法的实现思路 推荐范例：图算法的范例
https://leetcode-cn.com/tag/graph/
三、LeetCode 正确的打开方式
大家有没有发现上个章节频繁的出现了 LeetCode 这个字眼，那么这个网站到底是什么呢？在介绍之前还得和大家说下怎么做好题目练习吗。练题网站有力扣 （LeetCode 中文版）、清华 ACM、浙大 ACM。
这几个网站算法学习生态圈都比较稳定，LeetCode 也是其中的一种，我们推荐用力扣（力扣的小编看到的话记得给我们加个鸡腿）。这是一个宝藏网站，里面的内容非常多，大家感兴趣的话可以深入研究下。
这上面的题目一共 有1117 道。我们可以从不同的维度去刷题，比如难易度、问题分类、通过率等。我们推荐根据数据结构的分类来做练习题。比如你今天学了二叉树，那么打开 LeetCode，耗时 2 天做十道简单题的二叉树即可。按照这种思路，差不多 1 个月即可完成上述所描述的题目。
以上经验供大家参考。通过这个网站的可视化界面，可以较直观地对自己的学习有个回顾。推荐使用 C 语言，因为 C 语言更接近底层，编译速度会快那么零点几毫秒。别小看几毫秒的时间哦，因为在 LeetCode 上，算法耗时的最小单位是 1 毫秒。差一毫秒可是差别巨大的！
如果你写的算法仅战胜了 40%的提交记录，我们建议你重写提交下。算法魅力就在于此，毫秒必争！一个好的算法可以让程序的编译速度成几何倍速的增加。也可以直接点击柱状图，会有当前算法耗时的最优算法解。
前面说了一些 LeetCode 的东西，在实际开发过程中，我们安利大家一个 IDEA 的 LeetCode 的插件，名字就叫 leetcode 。使用这个小插件，可以帮助我们快速编译所写的 demo。编写的算法可以直接在编译器里测试 & 提交。
leetcode：
https://github.com/shuzijun/leetcode-editor
杂谈
说个现实的问题，除非是算法工程师，大家在开发的过程中极少用到算法的，那是不是反向推论算法仅是停留在做题&面试，仅需要应付面试即可了？那是不是只要疯狂刷题就可以了！！！
但我们还是建议大家在理论的基础上加以实践，并希望大家可以更深入地学习数据结构与算法，这会帮助我们加深对计算机运行的理解。
个人练习题库，我们比较推荐：
https://github.com/LiuLei0571/LeetCode
书籍我们推荐：《算法 4 》、《漫画算法》、《大话设计模式》、《大话数据结构》、《剑指 offer》。
彩蛋
感谢各位看官阅读到最后，你们的支持是我们创作的源泉。最后给大家出一道我们在实际开发中遇到的算法问题。
有以下一个 json 字符串，编写一个算法测试此 json 是否有回路。action_chains 里面有若干个动作，入口动作是 actionid=1，接着去执行下一个动作，下一个动作的 actionid 是上一个动作的 do 参数，出口是 actionid=100。
{
"action_chains": [
{
"actionid": "1",
"do": "2"
},
{
"actionid": "2",
"do": "3"
},
{
"actionid": "3",
"do": "4"
},
{
"actionid": "4",
"do": "5"
},
{
"actionid": "5"
}
]
}