1. 前言
对于软件开发校招而言，不管是应聘前端、后端还是移动端岗位，笔试是大部分同学都无法避免的一个环节，笔试中占据最重要地位的肯定是算法问题，如何高效并且快速的准备校招算法就是本章需要关注的问题。
2. 笔试
2.1 整体流程
我们只需要分析下招聘通知，就不难发现互联网大厂在筛选简历时会优先考虑这几类同学：
学校：大厂青睐公认的名校，例如清华、北大、上交、复旦等，或者是传统计算机强校：浙大、北邮、西安交大等。
竞赛经历：参加ACM-ICPC（国际大学生程序设计竞赛）并且在区域赛或者全国赛获得好名次、CCPC（中国大学生程序设计竞赛），或者蓝桥杯比赛等。
大厂实习经历：最好是BAT（百度、腾讯、阿里）或者TMD（头条、美团、滴滴），或者是一些知名独角兽（例如商汤、猿辅导）等有实习经历。
具备上述学历背景和经历的同学，通过熟人内推的方式，往往能免简历筛选和笔试，直接进入到面试流程。
但是对于大多数参加计算机校招的同学来说，往往都不具备上述几个优势，我们应该关心的是，作为普通条件的学生，如何高效快速的准备校招笔试。
一般来说，一轮完整的技术校招需要经过的流程如下：
面试流程
如图，可以看出，如果我们的算法能力不够应付笔试环节，往往都没有面试的机会，简历就被无情筛选掉了。而且对于头部互联网公司来说，很多岗位的投录比（简历投递人数/最终录取人数）过高，只能通过笔试提前筛选。
大部分情况下，候选人在经过了笔试和简历筛选之后，会经历2到3轮现场面试，通过之后就能被顺利录取。
所以除了准备关于计算机基础的面试题目之外，笔试算法也是关注的核心。
2.2 笔试考察内容
目前大部分的互联网公司都支持远程笔试和面试，具体的流程如下：
笔试流程
在候选人投递简历之后，企业会提前发送笔试邮件告知候选人。
因为候选人投递简历的时间比较分散，所以互联网企业一般会将候选人分为不同的批次，被分到同一批次的用户参加同一场笔试，
笔试题型一般分为选择题、问答题、编程题，笔试时间一般是一个半小时到两个小时。
因为问答题需要人为改卷，选择题和编程题都可以系统自动判定分数，所以选择题+编程题的出题方式比较常见，其中编程题大多是2到4道，主要都是算法题，完成语言不限制（一般都支持C++、Java、Python、Javascript这几种语言）。
2.3 笔试如何准备
选择题一般是考察候选人的计算机基础知识，包含计算机网络、操作系统、计算机组成等。如果是特定的面试岗位，例如Java后端工程师，也可能会涉及到特定语法，例如考察 Java 的多线程相关知识。
选择题一般靠看书，例如通过阅读《计算机网络：自顶向下方法》等教科书，况且目前网上有诸多已经整理好的开源题库，例如慕课网的相关教程。
算法题则比较特殊，就笔者的观察，大部分的候选人在不做准备的情况下都缺乏解决困难笔试题的能力。
因为即使是计算机专业的同学，所接受的大学编程通识教育，一般只涉及基础的数据结构教程。
在约定的笔试时间内，对于没有经过特定训练的候选人，还可能受到紧张等心理因素的影响，往往会难以编写无误的代码，最终结果只能无缘面试。
笔试考察的算法题难度浮动比较大，涵盖的知识也从基础的数据结构，例如堆栈和二叉树，到比较复杂的算法过程，例如深度优先查找算法、广度优先查找算法、动态规划算法等。但是我们从整体上分析，就不难发现这些题目大部分都具有固定的解题模板以及解题思路。
大厂面试官的笔试题来源，可以肯定90%来自 LeetCode 算法网站以及《剑指offer》这本算法书籍，所以候选人应该将关注的重点放在这两块内容。
本章后续的小节会给出一些经典的数据结构和算法解题模板和思路。
3. 小结
本章节介绍了校招的整体流程以及笔试需要准备的内容，之后的章节会针对数据结构与算法中的典型题目做出分析，题海无涯，候选人需要做到举一反三。
1. 前言
栈和队列相关的题目是校招中出现频率一般，但是是属于相对基础的题型。我们要关注两类问题，栈和队列的添加和删除操作，以及栈和队列之间的区别和联系。
2. 栈和队列
2.1 数据结构
首先我们给出栈和队列的数据结构定义：
（1）栈（Stack）：允许在某一端插入元素（即push操作），以及删除元素（即pop操作）的数据结构，必须满足后进先出（LIFO：Last In First Out）的运算规则。一个典型的栈数据结构如下图所示：
栈结构
（2）队列（Queue）：允许在某一端插入元素（即enqueue操作），以及在另一端删除元素（即dequeue操作）的数据结构，必须满足先进先出（FIFO：First In First Out）的运算规则。一个典型的队列数据结构如下图所示：
队列结构
2.2 用两个栈实现一个队列
面试官提问：能否用两个栈实现一个队列的数据结构？
题目解析：
反转链表是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/。
本题是一道非常经典的面试题，我们不能直接使用语言自带的Queue实现类，需要手动用两个栈来模拟队列的操作。
在解题之前，我们需要对栈和队列有个前置理解，栈支持入栈和出栈操作，队列支持入队和出队操作。并且从题目看，队列还需要实现peek函数（返回队列的头部元素）和empty函数（判断队列是否为空）。举例来说，我们假设实现的队列类名是MockQueue，基础的操作案例示例：
MockQueue queue = new MockQueue();queue.push(100); //将100放入队列queue.push(200); //将200放入队列queue.empty(); //判断队列是否为空，return falsequeue.pop(); //弹出队列的一个元素queue.peek(); //返回队列的头部元素，return 100
我们用 stack1、stack2 来表示两个栈，还是以小规模数据作为案例开始分析，对于一个数组[1,2,3,4]，我们将其存放到第一个栈stack1中，那么出栈的顺序是[4,3,2,1]，明显不满足队列的要求。入栈和出栈的操作是将数组逆序排列了一遍，从几何的角度可以看成旋转了180度，如果连续两次旋转180度，那么数组就会回到原点，分析到这里解法就呼之欲出了。
从分工上看，stack1 负责 push，stack2 负责 pop。
（1）入队的操作：我们直接把值放到 stack1；（2）出队的操作：首先判断 stack2 是否为空，如果为空就把 stack1 中的元素全部压入 stack2，最后弹出 stack2 的栈顶元素；（3）返回队列头部元素的操作：peek 操作和 pop 操作类似，区别在于不会弹出 stack2 的栈顶元素；（4）判断队列是否为空的操作：直接判断 stack1 和 stack2 是否同时为空就行。
下面给出Java源码的实现，示例：
class MockQueue { //首先我们需要定义两个Stack数据结构 Stack<Integer> s1; Stack<Integer> s2; public MockQueue() { // 初始化对象 s1 = new Stack<>(); s2 = new Stack<>(); } public void push(int x) { //入队操作 s1.push(x); } public int pop() { //出队操作 if(s2.isEmpty()){ while(!s1.isEmpty()){ s2.push(s1.pop()); } } return s2.pop(); } public int peek() { //从队列头部获取元素 if(s2.isEmpty()){ while(!s1.isEmpty()){ s2.push(s1.pop()); } } return s2.peek(); } public boolean empty() { //判断队列是否为空 return s1.isEmpty() && s2.isEmpty(); }}
3. 小结
本章节我们介绍了最基础的数据结构，栈和队列，其中栈在动态规划以及二叉树问题中也经常出现。在使用栈和队列解决算法问题时，需要特别注意容器为空的情况，防止抛出异常。这类边界问题的判断，在其他算法问题中也是注意点，例如二叉树首先要判断 root 是否为空，防止空指针访问异常。
1. 前言
排序算法是数据结构中最基础的算法，快速排序则是面试中最常见的排序算法。无论是校招面试还是社招面试，快速排序算法的出现频率远高于其他算法，而且经常会要求候选人白板手写实现算法。快速排序算法的核心是分治处理，重点是分析时间复杂度。
2. 快速排序算法
面试官提问：快速排序算法是怎么实现的？能手写实现一个快排算法吗？
题目解析：
为了实现bug free（基本没有逻辑缺陷）的白板编程，候选人可以将解决这个题目的过程分为两个步骤：
（1）分析快速排序算法的步骤，并且编码实现；（2）完成编码后，使用一个小规模的数据作为测试样例，模拟算法流程验证代码逻辑是否符合预期。
2.1 快速排序步骤
快速排序算法的核心是分治算法，所谓分治（Divide and Conquer）就是将一个复杂的问题分成两个或者多个相同或者相似的子问题，再把这些子问题分成多个相同或者相似的子问题，直到子问题能够被简单求解，把子问题的解合起来就是原始问题的解。
快排的分治思维在于将大的数组拆分为两个需要排序的左右子数组，再对子数组套用相同算法，直到子树组只有一个数字，一个数字的数组本身就是有序的，构成了原子问题的解。快排的核心步骤拆分为：
（1）选择基准：对于数组 A，选择一个数字作为基准值（pivot），习惯选择数组第一个元素作为 pivot；（2）构造分区：定义 left 和 right 左右指针，将小于基准的元素移动到左边，将大于基准的元素移动到右边；（3）递归求解：对于基准左边的数组 A1、基准右边的数组 A2 重复第一步和第二步，直到所有的子树组已经满足排序性质（子数组为空或者子树组只有一个元素）。
快速排序的算法实现代码以及解析，示例：
public void quicksort(int[] A,int left, int right) { //1. 递归终止条件，如果不构成数组结束算法 if(left > right) return; int i, j, t, pivot; //2. 选择第一个元素作为pivot pivot = A[left]; i = left; j = right; while(i != j) { //3.1 这里要注意顺序，必须先从右边开始找到第一个比pivot小的数 while(A[j] >= pivot && i < j) j--; //3.2 然后从左边找到第一个比pivot大的数字 while(A[i] <= pivot && i < j) i++; //3.3 交换两个数在数组中的位置 if(i < j) { t = A[i]; A[i] = A[j]; A[j] = t; } } //4. 最终将基准数归位 A[left] = A[i]; A[i] = pivot; //递归处理左边的分数组 quicksort(A,left, i-1); //递归处理右边的分数组 quicksort(A,i+1, right); }
2.2 小型数组模拟
下面我们使用一个小规模的数组模拟快速排序的过程，原始数组A的顺序是22、11、44、10、33。
（1）首先给定初始值：pivot = nums[left] = 22，left=0，right=4。
index01234
数组值2211441033
指针left
right
（2）从右到左找到 index=3 的位置，nums[3] 比 pivot 小；从左到右找到 index=2 的位置，nums[2] 比 pivot 大。
index01234
数组值2211441033
指针left
ijright
（3）交换坐标 i 和 j 所在的数组值。
index01234
数组值2211104433
指针left
i，j
right
（3）坐标 i 和 j 碰头，本次查找结束，交换 pivot 的值和 nums[i] 的值。
index01234
数组值1011224433
指针left
i，j
right
（4）本次查询完全结束，对坐标[0，1]的子数组和坐标[3，4]的子树组进行相同的递归操作，结束之后，数组A得到结果10、11、22、33、44。
2.3 快排考察点
关于快排，候选人需要注意几个关键的考察点：
（1）快排的平均时间复杂度为O（N*logN），最坏状态下时间复杂度为O（N^2），一般不会涉及具体的数学证明；（2）快排不是稳定排序算法，例如原始数组存在两个相同的数值，排序可能会交换两个值的顺序；（3）快速排序的核心思路是分治算法，实现方式是递归。
3. 小结
本章节介绍了面试最常见的排序算法算法：快排的算法思路以及使用 Java 实现了一个快排的算法模板。候选人可以使用小规模的数组测试现场编写的算法是否符合预期，特别需要注意快排的时间复杂度。
1. 前言
相对于各种复杂的二叉树（例如平衡二叉树、完美二叉树），单链表的数据结构简单，只涉及到一个值和指针的操作，所以面试中经常会出现需要手写单链表的算法题。反转链表应该是单链表中考察频率最高的题目，题目看起来比较简单，但是因为涉及的指针操作较多，要实现一遍 bug free 也不太容易。
2. 反转链表
2.1 算法实现
面试官提问：如何反转一个单链表？手写实现一下源码。
题目解析：
反转链表是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/reverse-linked-list/。
反转链表有多种解法：
（1）比较暴力（brute force）的方法是将链表的值放入一个有序数组，然后倒序从数组中取值，重新放入原有的链表。优点是算法简单，缺点是需要使用额外的数组空间，并且面试官一般不会接受这种不够优雅的算法；（2）递归算法，递归本质上也会使用额外的栈空间（stack memory），优点是算法简洁，一般来说面试官也能接受递归；（3）循环算法，使用多个指针在一次循环里改变链表顺序，不会使用额外的空间，时间复杂度是O（N），这里只介绍这个方法。
循环算法中，我们需要借助三个指针，before 指针指向上一个操作节点，head 指针指向当前操作节点，next 指针指向下一个操作节点。算法可以拆分为两个步骤：
（1）对于空链表以及只有单个节点的链表，直接返回链表本身，不需要进行反转；（2）对于普通链表，通过循环三个指针的操作实现链表反转，我们使用Java实现反转算法。
示例：
class Solution { public ListNode reverseList(ListNode head) { //1. 判断边界条件 if(head == null || head.next == null){ return head; } //2. 迭代反转 ListNode dummy = head; ListNode next, before = null; while(head != null){ //3.1 反转 next = head.next; head.next = before; //3.2 往后移动一位 before = head; head = next; } return before; }}
为了校验我们的算法是否有效，假设一个包含5个节点的链表，算法模拟的过程如下：
最开始给定的原始链表的结构如下，其中黄色部分代表指针，蓝色部分代表具体值：
初始状态
经过3.1步骤之后，链表的第一个节点被反转，指向了before节点，此时before节点还是Null：
执行操作3.1
然后经过3.2步骤后，我们把before、head、next的值都往后移动一位，第一个节点就完全实现了反转：
执行操作3.2
接下来，我们重复上述步骤，直到 head 节点指向 Null ，即完成了整个链表的反转，返回 before 节点就是新链表的头节点。
结束状态
2.2 细节考察
分析算法的时间复杂度和空间复杂度：上述循环算法，因为没有使用递归，没有使用额外的普通数组辅助存储，只是使用了两个临时变量，所以空间复杂度为O（1）。因为通过单循环顺序遍历链表，所以时间复杂度为O（N）。
对于节点数量少于两个的链表，需要提前返回原始链表，防止 NullPointerException空指针异常。
3. 小结
本章节介绍了单链表中最经典的反转链表问题，候选人从编写算法源码、通过小规模测试样例验证算法是否符合预期以及分析算法的时间和空间复杂度三个纬度入手，给出面试官满意的答案。
1. 前言
上个章节介绍了单链表反转，单链表还存在一些经典的问题，例如找到链表的倒数第 K 个节点，或者在原始链表上进行快速排序，或者是判断一个单链表是否成环，这些问题看似没有共同性，但是都可以使用快慢指针（Fast-Slow Point）方法解决。
2. 链表成环问题
面试官提问：给定一个单链表，判断链表是否存在环？能否在不使用额外空间的情况下解决问题？
题目解析：
链表成环问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/linked-list-cycle/。
暴力破解方法是使用额外的数组结构，数组每一个元素存储链表的值以及节点哈希地址，在遍历链表的时候，如果发现遍历到相同哈希地址的节点，说明链表有环，否则直到遍历到链表末尾节点为止。
但是面试官要求在原始数组上操作，空间复杂度控制在O（1）。
使用单个指针则没有记忆能力，所以肯定要使用两个以上的指针遍历链表，最常用解法就是快慢指针法。
经典快慢指针的算法核心思路是：
（1）初始定义：定义一个指针 slow，每次走一个 Node 节点；定义一个指针 fast，每次走两个 Node 节点；（2）终止条件一：当快指针走到了 Null 节点，说明链表没有成环；（3）终止条件二：当快指针和慢指针同时走到了一个节点，说明该链表有环；（4）附加计算一：当满足链表有环时，将慢指针重置到链表头部，然后快慢指针同时走，每次只走一个节点，当两个指针再次相遇时，相遇点即是链表的环入口；（5）附加计算二：当满足链表有环时，停止快指针，每次慢指针走一个 Node 节点，当两个节点再次相遇时，慢指针重新走的长度即是链表长度。
最重要的环节在于如何证明慢指针和快指针会在环中相遇，我们假设一个通用的有环链表如下图所示：
环状链表
其中A—>B 的距离为 x，B—>C 的距离为y，C—>B 的距离为 z。
假设慢指针走了a步，那么快指针走了2a步，因为相遇时快指针已经在环上循环了n次，所以满足公式：2*(x+y) = x+y+n*(y+z)，所以x+y = n * (y+z)。快慢指针之间的距离会逐渐增大，结果是要么快指针提前走到了链表末尾，要么是快指针刚好多走出n个链表长度，说明链表有环。
我们在白板上可以写出算法实现，示例：
public class Solution { public boolean hasCycle(ListNode head) { //如果链表为空或者只有一个节点，肯定不成环 if(head==null || head.next==null){ return false; } ListNode slow = head; head=head.next; while(head!=null && head.next!=null){ //当快慢指针相遇，说明链表有环 if(slow==head){ return true; } slow=slow.next; head=head.next.next; } return false; }}
算法的时间复杂度为O（N），其中N表示链表长度，空间复杂度为O（1），因为没有使用额外辅助空间。
3. 小结
本章节介绍了最基础的快慢指针算法，快慢指针是解决链表问题的银弹。例如找到链表的倒数 K 个节点，也可以另快慢指针间距为 K，两者步长相同，最终慢指针走到的节点即是目标节点。对于快慢指针用法，候选人需要注意两点： ① 边界条件：如果是空链表或者单节点链表，直接使用快慢指针可能会导致空指针异常，需要特殊处理； ② 快慢指针不一定是步长相差两倍，可能是步长相同，但是一个走在前，一个走在后。
1. 前言
二叉树算法题也是面试中常见的一类题目，相对于链表，二叉树每个节点存在两个指针，结构更为复杂。但是相对于节点中有多个指针的多叉树，双节点的操作相对简洁，所以比较适合在面试中的白板编程。二叉树有一些经典问题，例如判断一颗二叉树是否属于平衡二叉树，将一颗二叉树展开为单链表，求解二叉树的深度，二叉树的前序、中序、后序遍历等。这些题目存在基本的算法模板，本章将探讨求解二叉树深度题目。
2. 二叉树深度
面试官提问：给定一个二叉树根节点，如何求解这棵二叉树最大深度？
题目解析：
求解二叉树深度问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/maximum-depth-of-binary-tree/。
首先给出二叉树最大深度的定义：二叉树从根节点到所有叶子节点的最长一条路径。例如下图的二叉树，最大深度路径就是3 -> 20 -> 16以及3 -> 20 -> 8，所以最大深度为2。
二叉树结构
求解二叉树问题的通用解法是递归算法，使用递归需要满足三个条件：
（1）初始问题可以拆分为多个子问题；（2）子问题除了数据量不同，求解思路和初始问题相同；（3）必须存在递归终止条件。
递归算法的优势是代码简洁，在面试过程中白板编程能容易实现 bug free，所以比较推荐候选人尽量采用递归。
二叉树自身的数据结构也可以通过递归实现，对于根节点以及任何一个中间节点，本质上都是存在两个左右子树指针（叶子节点的子树存在，但为空）。
回到题目，对于任何一个节点，如果我们知道左右子树的深度，那么左右子树深度的最大值加一，就是当前节点的深度，这就是子问题的通用解法。最后，确定递归终止条件：如果我们遍历到了空节点，那么停止搜索，算法的 Java 实现，示例：
class Solution { public int maxDepth(TreeNode root) { //主函数入口 int depth=0; depth=calDepth(root, depth); return depth; } public int calDepth(TreeNode node, int depth){ //递归终止条件：如果到了空节点，直接返回深度 if(node==null) return depth; //深度+1 depth++; //返回左右子树的最大深度 return Math.max(calDepth(node.left, depth), calDepth(node.right,depth)); }}
从本题中我们可以抽象得到二叉树问题的常见通用解决方案。
二叉树递归本质上属于深度优先搜索算法，我们定义深度优先搜索的 DFS函数，在 DFS 中首先要给出递归终止条件，常见的终止条件是二叉树的叶子节点或者空节点，其次是对于函数入参根节点的左子树和右子树调用函数，在不同函数之间定义 counter 记录结果值或者中间变量值。
算法的伪代码，示例：
public void Solution(TreeNode root){ //调用递归函数 dfs(root,counter);}public Object dfs(TreeNode root, Object counter){ //1. 递归终止判断 if(...) ... //2. 递归调用 dfs(root.left, counter_1); dfs(root.right, counter_2); ...}
3. 小结
本章节中我们给出了二叉树最大深度的算法解法，候选人在编写代码时需要注意边界条件，完成之后可以通过少数几个节点的简单二叉树验证算法运行是否符合预期。最后，我们给出了二叉树搜索的通用递归解法，对于相似的题目，例如求解二叉树的高度，判断一颗二叉树是否属于平衡二叉树，都可以使用递归。
1. 前言
除了可以直接使用递归处理的二叉树问题，二叉树中还有一些典型的算法问题，需要和其他的数据结构配合解决，例如使用堆、栈以及队列数据结构配合查找的过程，可以避免使用递归算法。
2. 二叉树视图
2.1 二叉树右视图
面试官提问：给定一颗二叉树，求出从二叉树右边看到的所有节点结果集合。
题目解析：
求解二叉树右视图问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/binary-tree-right-side-view/。
首先给出二叉树右视图的定义：从二叉树的右边看到的第一个节点，即是当前层数的结果节点，把所有的结果节点添加到集合，即是结果集合。
二叉树右视图
举例来说，对于上图中的二叉树结果，其右视图的结果集是[3,20,8]。
根据题意，最明显的方法是层次遍历二叉树，也就是BFS广度优先搜索算法，按照这个思路。
我们使用双向队列作为数据结构存储层次遍历的结果，我们要解决两个问题，一是如何实现层次遍历，二是如何判断是否是每层的最右边的节点。
（1）初始条件：首先把根节点放入双向队列尾部；（2）最右判断：每次首先得到双向队列当前的长度 size，这是一个固定值，对于第一层来说，因为只有一个根节点，所以 size-1 的位置就是最右边的节点；（3）循环处理：以size作为循环次数，从双向队列头部开始，不断弹出节点，将每个节点的非空左右子树加入双向队列尾部。当遍历到 size-1 的位置时，就是当前层数的最右节点。一直循环，直到双向队列为空，即处理完所有的二叉树节点。
在 Java中 使用 ArrayDeque 数据结构实现双向队列，下面给出 Java 算法的源码以及注解，示例：
public List<Integer> rightSideView(TreeNode root) { Queue<TreeNode> q= new ArrayDeque<>(); List<Integer> res = new ArrayList<>(); //如果是空节点，直接返回空结果集 if(root == null) return res; //将根节点添加到队列 q.offer(root); while(!q.isEmpty()){ int size = q.size(); for(int i = 0; i< size; i++){ //从双向队列头部弹出第一个节点 TreeNode node = q.poll(); //如果是当前层数的最后一个节点，就是需要的右视图节点 if(i == size-1) res.add(node.val); //弹出节点的有效左节点加入队列 if(node.left != null) q.offer(node.left); //弹出节点的有效右节点加入队列 if(node.right != null) q.offer(node.right); } } //返回结果集 return res;}
当然除了 BFS 算法外，本题目也可以使用 DFS 算法，即通过前序遍历获取需要的最右节点，这里不再赘述。
2.2 二叉树左视图、二叉树层次遍历
求解二叉树左视图、二叉树右视图、二叉树层次遍历问题，都可以使用双向队列求解。
（1）二叉树右视图：每次获取当前层双向队列的最后一个节点；（2）二叉树左视图：每次获取当前层双向队列的第一个节点；（3）二叉树层次遍历：对于每遍历一次 size ，结果添加到一个单独的列表。
3. 小结
候选人在学习算法问题时，需要注意举一反三，目前算法网站的面试题题库已经接近 2000 题，如果企图通过刷遍题库的方式提高算法能力，是非常消耗精力的。所以要做到精简问题和总结算法套路，例如本章中介绍的二叉树和双向队列配合使用，实现广度优先搜索，就是一个非常典型的算法模板，可以多加熟悉。
1. 前言
动态规划（Dymamic Programming，简称 DP）应该是面试中出现频率最多并且公认难度最大的一类题型，动态规划问题非常灵活，没有统一的模板。动态规划中最简单的问题，例如爬楼梯，状态转移方程非常简单，但是大部分问题都没有通用的状态转移方程，所以如果缺乏对DP问题的练习，在笔试和面试中就有卡壳无从下手的风险。候选人的目标应该是尽可能的找到不同题目之间的相似点并举一反三。
2. 最大子数组和
面试官提问：给定一个数组，求解数组中连续子树组的最大和。
题目解析：
求解最大子数组求和问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/maximum-subarray/。
我们以小型数据的数组作为样例分析，什么是连续子数组的最大和：
样例输入：[-2,1,-3,4,-1,2,1,-5,4]
样例输出：6
样例解释：连续子数组 [4,-1,2,1] 的和最大，求和结果为6。
这里需要特别明确子树组和子序列的区别，
（1）子树组定义：一个或者连续多个数组中元素组成一个子数组；（2）子序列定义：在原来数组中找出一部分组成的序列。
结论：子树组一定是连续的数字，但是子序列只需要保证前后顺序上的有序，数字之间不一定连续。
在明确子数组定义之后，我们用一句话概括 DP 的核心解题思路：我们要找到某个子问题的最优解，然后在它的帮助下，找到下一个子问题的最优解。
例如对于爬楼梯问题，对于 n 个台阶，每次能够跳一个台阶或者两个台阶，我们知道对于第 k 个台阶，一定是从第 k-1 个台阶再跳一个台阶，或者是从第k-2个台阶再跳两个台阶上来，所以只需要知道第 k-1 个台阶的路径个数和第k-2个台阶的路径个数，求和就是最终的答案。其中第 k-1 和第 k-2 个台阶的路径就是子问题。
将上述的语义切换到算法上来，就是需要找到状态转移方程以及状态的初始值。
最大子树组和问题中，状态的初始含义非常明确：如果数组的长度为空，那么不存在子树组，直接返回最大和为零。
初始状态结果为零的含义是，最后返回的最大子树组和一定不是负数，因为和为负数还不如直接用空数组返回零。
对于一般子问题，我们假设 dp[i] 表示以 nums[i] 作为子树组末尾元素的前i个数字构成的子树组的最大和，nums[i]表示数组中的第i个元素。举例来说，对于数组[a1，a2，a3]，dp[2] 只有三种构成可能：[a1，a2，a3]，[a2，a3]，[a3]，都是以 a3 作为子数组结尾元素。
那么假设已经遍历到了第i个数字，如果 dp[i-1] 小于零，说明数组的前 i-1 个子树组的和最大也是负数，前面说过，负数对于求解结果是没有帮助的，所以如果 dp[i-1] 小于零，dp[i] 直接选择 nums[i] 作为只有一个元素的子数组，和最大值就是 nums[i]。如果 dp[i-1] 大于零，说明加上前面的子树组会让结果更大，那么需要加上。
上面的语义用dp方程表示如下：
dp[i] = 0 如果nums.length=0；
dp[i] = nums[i] 如果dp[i-1] < 0；
dp[i] = nums[i] + dp[i-1]，如果dp[i-1] > 0 。
最后，我们需要返回的是 dp 数组中的最大值。
从状态转移方程可以看出，我们其实只需要 dp[i-1]，所以使用一个临时变量去保存它，能将空间复杂度降低到O（1）。示例：
public int maxSubArray(int[] nums) { //边界条件判断 if (nums.length == 0){ return 0; } //表示dp[i-1] int prev = nums[0]; //表示dp[i] int cur = nums[0]; //结果 int max = nums[0]; for (int i = 1; i < nums.length; i++){ if (prev > 0){ //如果dp[i-1] > 0 cur = prev + nums[i]; } else { //如果dp[i-1] <= 0 cur = nums[i]; } max = Math.max(max, cur); prev = cur; } return max;}
3. 小结
本章节介绍了动态规划中最简单的一种问题，就是在数组中找到满足要求的极大值或者极小值，通常只需要构建一个简洁的状态转移方程就可以解决问题。如果状态转移方程中只涉及到连续的两个或者三个位置的值变化，甚至可以将状态数组压缩到单个变量，将空间复杂度从O（n）优化到O（1）。
1. 前言
在上个章节中我们讨论了最常见的一维数组以及对应一维状态转移方程的解决方案，但是动态规划的难点在于很多情况下使用一维的状态转移方程并不能解决问题，需要使用二维甚至三维的转移方程。多维方程的状态转移函数需要抽象不同对象，例如多个字符串或者数组之间的关系。
2. 最长公共子序列
面试官提问：给定两个字符串，求解最长公共子序列。
题目解析：
求解最长公共子序列问题是来源于算法网站LeetCode的经典题目，题目链接：https://leetcode.com/problems/longest-common-subsequence/。
首先是明确子序列的定义，例如对于字符串imooc，那么im、imo、imc都是它的子序列，子序列可以连续也可以不连续，如果是连续出现的，例如字符串imoo，一般被叫做子序列串。
其次是明确公共子序列的定义，对于两个字符串，如果包含相同的子序列，那么这个子序列就是两个字符串的公共子序列，例如imooc和moocer的公共子序列就有m和mo等，所有公共子序列中最长的子序列就是最长公共子序列（Longest Common Subsequence）。
首先从定性的角度来看，如果两个字符串中，一个字符串的长度为零，那么最长公共子序列长度一定为零。
其次从定量的角度分析这个问题，例如给定的两个字符串分别是X={x1,x2,x3 ... xm} 和Y={y1,y2,y3 ... ym}，表示X字符串是通过x1、x2一直到xm个连续字符组成，Y字符串同理。求解动态规划的通用方案是找到子问题的共性，字符串的子问题就是子字符串，我们假设X'={x1,x2,x3 ... xi} 和 Y'={y1,y2,y3 ... yi} 的最长公共子序列是L，其中i<m。那么按照递归就有两种状态转移流程：
（1）如果xi=yi，也就是两个字符串的子字符串的最后一个字符刚好相等，那么{L,x(i+1)}或者{L,y{i+1}}就是新的最长公共子序列；
（2）如果xi≠yi，也就是两个字符串的子字符串的最后一个字符并不相等，那么问题就可以转换为求下面两种情况的最长公共子序列：
第一种情况：X'={x1,x2,x3 ... x(i-1)} ，Y'={y1,y2,y3 ... yi}的最长公共子序列，假设为L1；第二种情况：X'={x1,x2,x3 ... xi} ，Y'={y1,y2,y3 ... y(i-1)}的最长公共子序列，假设为L2。
最终需要的结果就是L = max(L1，L2)。
我们用 Java 语言实现上面描述的算法，示例：
class Solution { public int longestCommonSubsequence(String text1, String text2) { int n = text1.length(); int m = text2.length(); int[][] dp = new int[n+1][m+1]; //设置dp方程初始值 for(int i = 0; i < n+1; i++){ for(int j = 0; j < m+1; j++){ if(i == 0 || j == 0){ dp[i][j] = 0; } } } //循环更新状态 for(int i = 1; i < n+1; i++){ for(int j = 1; j < m+1; j++){ if(text1.charAt(i-1) == text2.charAt(j-1)){ //如果这个位置的字符相同，说明相对于dp[i-1][j-1]刚好长一个字符 dp[i][j] = 1 + dp[i-1][j-1]; } else{ // 否则采用公共长度最长的 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } //返回结果 return dp[n][m]; }}
3. 小结
本章节介绍了动态规划中最经典的最长公共子序列问题，相对于一维数组下的动态规划，二维数组的动态规划一般不能压缩空间，即时间复杂度基本都是O（n^2）的级别。字符串和动态规划结合的类似问题还有最长上升子序列、字符串的编辑距离等。候选人需要从小型数据案例开始分析状态转移的核心，问题一般都能迎刃而解。
