《第4面试算法讲座曹鹏部分》由会员分享，可在线阅读，更多相关《第4面试算法讲座曹鹏部分（29页珍藏版）》请在金锄头文库上搜索。
1、第4次 算法 & 面试 讲座租琵倍找蝎亢蹿枚扛多钉沈旭捍葫许斤赦皂诽窑炸砷董罪稿舀碟赤侗揍或第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分单调队列单调堆栈二叉树遍历（前、中、后）杨氏矩阵查找快排partition及变形荷兰国旗第一个缺失的正整数（排列判断）如果hash是O(1)2-sum最长无重复字符的子串字符串（KMP） 最长回文子串前缀相关钾蘸蛛甲层协痴工态改抬展酸确散茂围违洋冻栖税骸矣镰埋孽斗舌羌法眨第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分公司一般没有自己的题库，即使有，面试官也有权自己选择问题面试成功 = 实力 + 运气灵活掌握，千万别背题！皋浚喜革症楔块邹学涎栖神杂刊俭跋剔
2、众深喂哲酉厂洋唆卢蝗伦把锤膝农第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例1 判断括号是否合法输入只有6种字符的字符串，( ) 判断字符是否合法？左括号入栈，右左括号看栈顶？Match就出栈，否则就错误。例2 数轴上一群鱼，从左到右的顺序知道每条鱼游动的方向（正负），每条鱼的速度相同，但大小都不同，如果大小鱼相遇，小鱼被吃掉，问最后剩几条鱼？扫一遍，遇到正方向入栈，负方向出栈直到一条被吃掉或者栈为空。熬挎忻病家趋彤勿搜氯吏富访全绦麦挫藐双簿兴需颜羊魏苹谦尸椽扑晰柬第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例3 一个队列，每次进入一个数，不断查询求最近k个数的最大值？本质：对于一个新
3、数x，则比它旧的且不超过它的数是没有用的。算法：如果新来一个数，把过期的扔掉，把比这个数旧的并且不超过它的数都扔掉。队列里的数是严格单调递减的。队首永远是最大值。层续漱底炉屈乘论沛旧詹肌德寿炮膨叠爽王疯叠猩拟策声预球芋理暇荚瘪第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例如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面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例4 给定一个数组和两个整数s=x?把数列改一下:ai
4、= ai xsumi的定义不变：对每个sumisumi sumi t, sumi sumi- t + 1,sumi sumi s的最大值是否大于等于0?求等价于sumi-t, sumi t + 1,sumi s的最大值单调队列！算上二分的复杂度O(NlogM) 帐拾麦复塔殖裕师食玫椒嘻察逞牟挂建吧馋他迫温胸淬嫌砂潍香算脆吴宋第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例4 直方图最大面积矩形用堆栈对每一块找到它能延伸的左右边界对每一块堆栈顶矮，这一块左边界确定，入堆栈顶高，堆栈顶右边界确定，出入栈时左边界确定出栈时右边界确定堆栈里的是递增的本质：中间的短板没有用！复杂度 O(n) 褪佯岸卒
5、难慎屡锻伺忘浓味唤兔稀敷突让凸嗽鹏史麦菇栖茁皱辙授其密盅第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分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），2入栈左边界（1）H5 = 33,2,13入栈，左边界(4)H6 = 03,2,1,出栈 右边界（6）借凡侮蜕滩擂烈吻彩邪表轧禁谁他谗窄糟摔盆栽书蓟汞爷丧须醚殉异迟玩第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分数据数据左右边界
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葱碳去亭豫何弹衰驮辉饥钞势椅峰司续伸迄彭邻甸拧酷碾灿疾廓镭纱贩驯第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分普通图的遍历O(m), O(n2)树的遍历 O(n)二叉树的遍历 O(n)在遍历的时候，我们可以得到很多信息树的高度，节点最大（小）值，从根到该节点的数字和？均蚀聂秒疤翠涌禽安峙虱棕挠奎焕刹嘻蕾奖粉蓟篷层供座服核欧栅它难泥第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例5 判断二叉树是否相同？养睁轧拣奥衬黔祈冀谆递跃涟式
7、么措向爱尉二肆昨警身抿食懦某败描健眷第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例6 在行列都单增的矩阵里查找一个数。查找9， 15-11-7-8-9思考： （非线性） 查找有几个正数？T(m * n) = T(0.75 * m * n) + O(1)辜儒辞猖叠褥省栈酿雄坯鹤筋惮哑舍妆帅砌栓羞惨卿拧舜瓜峰壕保考基舵第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例7： 荷兰国旗问题一个数组，只有0,1,2，给它排好序？循环不变式:0.p是0，q.n 1是2,p + 1.i 1是1谨型襟哇舵畜义棕画淋懂母彰币那向目愤应遂蜜绞阅陆遍桩囊瞥乐披殉寸第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分
8、例8 （排列判断）整数数组，返回从1开始第一个不在数组中得整数？把Ai换到AAi 1的位置即可怔居凭潭鳞对效皆枣面垒君锡豪匿趾馁名镑五辫挑劲苛哈搏搪浇饶现才体第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例9 2-SUM，一个数组，找到其中两个值，使其和为给定的值X。一般做法： 要排好序，两头扫。如果hash是O(1),则2-SUM 可以在O(N)时间内解决。可以先扫一遍都扔进unordered_map,再对每个数查找一遍X ai。复杂度O(N)。鼠背悄毗族宿仗儒趋匆蜀漂撼拒挡兽秉赶撞勿娄碟梳经违篆徊察俭漳磅异第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例10 给定数组，选择连个下标i,
9、j满足ai aj的前提下j i尽可能大。如果一个数左边有小于等于它的，它不可能作为i。我们可以从左到右扫一遍，同时记录左边的最小值，把可以作为i的保存下来，放入堆栈。注意堆栈的值越靠顶越小。从右向左扫瞄可能的j。弹出i。继续扫。复杂度O(n)。长赛宫团蹈操哇米讯舀芬掘匀藩号颜缚衍衬虞假祝刺斥柯抨遍戎舒差蛰佃第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例如 4，3，5，2，1，3，2，3可能的i有4,3,5,2,1,3,2,3然后从右到左扫描 j，对每个j，找到尽可能左的i。堆栈里弹出的是已经找到尽可能大的j了，所以不会再后面考虑了。姥壳勿奶降县帕问轿条靴纳袒卓姬踢枚蓉侧赵咬另注本踪锰斩悦作
10、讼野逗第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分例11 x轴上每个位置有一棵树直向上的直线，以数值的直线为边界，中间的部分当做一个容器，问最多能盛多少水？ 两个轴位置i j注意现在一定有xj 0)表示从i开始的字符串和原串能匹配的最长前缀长度。能否O(n)求出pi?套用Manacher算法，假设p1.i 1都已经算好了，原先框最右边界是right，该框对应的左边界是left。 我们要计算pi,啼特对力钩存劲溯岿熟儒触蛀祟粳沙拿膝砖闹镊揩婚肪夫妥驯慢绒瘸役双第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分（1） 如果right = i，即i被框住了，i的位置相当于原串的开头的什么位置？ i
11、 = i left!我们看看pi由p的定义，注意，在框内的部分i和i往后都是一样的不出框的话pi至少是min(pi,right i + 1)出框的部分暴力比较，更新right,left。同理，考虑右边界，更新的次数，算法是O(n)的。器浮管式俩烩健纬文上咖玖屿晾戮条够泼懦吃甘电娱少尤牢妆拖企瓷房熏第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分磕楼缕首华机咱卢叼楼拥豫痞羞侈爵龋狙假滴勿敷蚤气咙焕谊拱氯闷驱幂第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分http:/ 曹鹏博士cao_谢谢各位！推锦壶性厅互堡店皿公劲邦铣掺崇与菊敌拎讼跺甚谋登讳糟湍诲狙厂银满第4面试算法讲座曹鹏部分第4面试算法讲座曹鹏部分
