第4次面试算法讲座课件.ppt

1、第4次 算法&面试 讲座单调队列单调堆栈二叉树遍历（前、中、后）杨氏矩阵查找快排partition及变形荷兰国旗第一个缺失的正整数（排列判断）如果hash是O(1)2-sum最长无重复字符的子串字符串（KMP）最长回文子串前缀相关公司一般没有自己的题库，即使有，面试官也有权自己选择问题面试成功=实力+运气灵活掌握，千万别背题！例1 判断括号是否合法输入只有6种字符的字符串，()判断字符是否合法？左括号入栈，右左括号看栈顶？Match就出栈，否则就错误。例2 数轴上一群鱼，从左到右的顺序知道每条鱼游动的方向（正负），每条鱼的速度相同，但大小都不同，如果大小鱼相遇，小鱼被吃掉，问最后剩几条鱼？扫一

2、遍，遇到正方向入栈，负方向出栈直到一条被吃掉或者栈为空。例3 一个队列，每次进入一个数，不断查询求最近k个数的最大值？本质：对于一个新数x，则比它旧的且不超过它的数是没有用的。算法：如果新来一个数，把过期的扔掉，把比这个数旧的并且不超过它的数都扔掉。队列里的数是严格单调递减的。队首永远是最大值。例如K=2,数字是 4,5,3,2,7,8,1新数新数队列队列4454，535,3 4过期23，2 5过期77 3过期，2比7小88 7比8小18，1例4 给定一个数组和两个整数s=x?把数列改一下:ai=ai x sumi的定义不变：对每个sumi sumi sumi t,sumi sumi-t+1,

3、sumi sumi s的最大值是否大于等于0?求等价于sumi-t,sumi t+1,sumi s的最大值 单调队列！算上二分的复杂度O(NlogM)例4 直方图最大面积矩形用堆栈对每一块找到它能延伸的左右边界对每一块 堆栈顶矮，这一块左边界确定，入 堆栈顶高，堆栈顶右边界确定，出 入栈时左边界确定 出栈时右边界确定 堆栈里的是递增的本质：中间的短板没有用！复杂度 O(n)2，1，5，6，2，3 新数新数堆栈堆栈说明说明H0=222入栈,左边界(-1)H1=112出栈，右边（1），1入栈，左边界(0)H2=55,15入栈，左边界（1）H3=66，5，16入栈，左边边界（2）H4=22,16，5

4、出栈，右边界（4），2入栈左边界（1）H5=33,2,13入栈，左边界(4)H6=03,2,1,出栈 右边界（6）数据数据左右边界左右边界面积面积H0=2（-1，1）2H1=1（0，6）5H2=5（1，4）10H3=6（2，4)6H4=2(1,6)8H5=3(4,6)3普通图的遍历O(m),O(n2)树的遍历 O(n)二叉树的遍历 O(n)在遍历的时候，我们可以得到很多信息 树的高度，节点最大（小）值，从根到该节点的数字和？例5 判断二叉树是否相同？例6 在行列都单增的矩阵里查找一个数。查找9，15-11-7-8-9思考：（非线性）查找有几个正数？T(m*n)=T(0.75*m*n)+O(1)

5、例7：荷兰国旗问题一个数组，只有0,1,2，给它排好序？循环不变式:0.p是0，q.n 1是2,p+1.i 1是1例8（排列判断）整数数组，返回从1开始第一个不在数组中得整数？把Ai换到AAi 1的位置即可例9 2-SUM，一个数组，找到其中两个值，使其和为给定的值X。一般做法：要排好序，两头扫。如果hash是O(1),则2-SUM 可以在O(N)时间内解决。可以先扫一遍都扔进unordered_map,再对每个数查找一遍X ai。复杂度O(N)。例10 给定数组，选择连个下标i,j满足ai aj的前提下j i尽可能大。如果一个数左边有小于等于它的，它不可能作为i。我们可以从左到右扫一遍，同时

6、记录左边的最小值，把可以作为i的保存下来，放入堆栈。注意堆栈的值越靠顶越小。从右向左扫瞄可能的j。弹出i。继续扫。复杂度O(n)。例如 4，3，5，2，1，3，2，3可能的i有4,3,5,2,1,3,2,3然后从右到左扫描 j，对每个j，找到尽可能左的i。堆栈里弹出的是已经找到尽可能大的j了，所以不会再后面考虑了。例11 x轴上每个位置有一棵树直向上的直线，以数值的直线为边界，中间的部分当做一个容器，问最多能盛多少水？两个轴位置i j注意现在一定有xj 0)表示从i开始的字符串和原串能匹配的最长前缀长度。能否O(n)求出pi?套用Manacher算法，假设p1.i 1都已经算好了，原先框最右边界是right，该框对应的左边界是left。我们要计算pi,（1）如果right=i，即i被框住了，i的位置相当于原串的开头的什么位置？i=i left!我们看看pi 由p的定义，注意，在框内的部分i和i往后都是一样的 不出框的话pi至少是min(pi,right i+1)出框的部分暴力比较，更新right,left。同理，考虑右边界，更新的次数，算法是O(n)的。http:/ 曹鹏博士cao_谢谢各位！