第4次面试算法讲座曹鹏部分.ppt
《第4次面试算法讲座曹鹏部分.ppt》由会员分享,可在线阅读,更多相关《第4次面试算法讲座曹鹏部分.ppt(29页珍藏版)》请在三一文库上搜索。
1、曹鹏 2013-11-24,第4次 算法 & 面试 讲座,何为O(N)? N是什么?,单调队列 单调堆栈 二叉树遍历(前、中、后) 杨氏矩阵查找 快排partition及变形 荷兰国旗 第一个缺失的正整数(排列判断) 如果hash是O(1) 2-sum 最长无重复字符的子串 字符串(KMP) 最长回文子串 前缀相关,题外话,公司一般没有自己的题库,即使有,面试官也有权自己选择问题 面试成功 = 实力 + 运气 灵活掌握,千万别背题!,普通堆栈,例1 判断括号是否合法 输入只有6种字符的字符串,( ) 判断字符是否合法? 左括号入栈,右左括号看栈顶?Match就出栈,否则就错误。 例2 数轴上一
2、群鱼,从左到右的顺序知道每条鱼游动的方向(正负),每条鱼的速度相同,但大小都不同,如果大小鱼相遇,小鱼被吃掉,问最后剩几条鱼? 扫一遍,遇到正方向入栈,负方向出栈直到一条被吃掉或者栈为空。,单调队列,例3 一个队列,每次进入一个数,不断查询求最近k个数的最大值? 本质:对于一个新数x,则比它旧的且不超过它的数是没有用的。 算法: 如果新来一个数,把过期的扔掉,把比这个数旧的并且不超过它的数都扔掉。队列里的数是严格单调递减的。队首永远是最大值。,单调队列样例,例如K = 2, 数字是 4,5,3,2,7,8,1,单调队列的应用,例4 给定一个数组和两个整数s=t,求所有长度在st之间的子数组(连
3、续)的平均值的最大值。(注意本题不是O(N)!) 分析: 假设下标从1开始,我们记录前缀和sumi = a1 + a2 +ai。 那么以i结尾的满足条件的每个长度的子数组的和分别是:sumi sumi t, sumi sumi- t + 1,sumi sumi s。 我们求的是平均值的最大值,当然可以枚举全部!,单调队列的应用续,二分? 给定x,能否求出是否存在满足条件的子数组,平均值=x? 把数列改一下:ai = ai x sumi的定义不变: 对每个sumi sumi sumi t, sumi sumi- t + 1,sumi sumi s的最大值是否大于等于0? 求等价于sumi-t,
4、sumi t + 1,sumi s的最大值 单调队列! 算上二分的复杂度O(NlogM),单调堆栈,例4 直方图最大面积矩形 用堆栈对每一块找到它能延伸的左右边界 对每一块 堆栈顶矮,这一块左边界确定,入 堆栈顶高,堆栈顶右边界确定,出 入栈时左边界确定 出栈时右边界确定 堆栈里的是递增的 本质:中间的短板没有用! 复杂度 O(n),单调堆栈,2,1,5,6,2,3,单调堆栈,图的遍历,普通图的遍历 O(m), O(n2) 树的遍历 O(n) 二叉树的遍历 O(n) 在遍历的时候,我们可以得到很多信息 树的高度,节点最大(小)值,从根到该节点的数字和?,二叉树的遍历,例5 判断二叉树是否相同?
5、,杨氏矩阵查找,例6 在行列都单增的矩阵里查找一个数。 查找9, 15-11-7-8-9 思考: (非线性) 查找有几个正数?T(m * n) = T(0.75 * m * n) + O(1),简单地扫描,例7: 荷兰国旗问题一个数组,只有0,1,2,给它排好序? 循环不变式:0p是0,qn 1是2,p + 1i 1是1,简单地扫描,例8 (排列判断)整数数组,返回从1开始第一个不在数组中得整数? 把Ai换到AAi 1的位置即可,两头扫2-SUM,例9 2-SUM,一个数组,找到其中两个值,使其和为给定的值X。 一般做法: 要排好序,两头扫。 如果hash是O(1),则2-SUM 可以在O(N
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 面试 算法 讲座 部分
链接地址:https://www.31doc.com/p-2604583.html