西电面试算法讲座演示文稿

西电面试算法讲座演示文稿当前第1页\共有95页\编于星期日\16点优选西电面试算法讲座当前第2页\共有95页\编于星期日\16点以前的不足对着PPT一本正经念到底堆砌知识、没有要害100页PPTPPT上字多、不够一目了然体力不支、互动太少当前第3页\共有95页\编于星期日\16点第一部分、面试当前第4页\共有95页\编于星期日\16点笔试面试考什么当前第5页\共有95页\编于星期日\16点笔试偏基础语言基础inthope;int*hope;double(*p)[3];void(*func)();操作系统线程与进程的区别产生死锁的条件如何规避死锁C++内存分配堆、栈、自由存储区、全局/静态存储区，常量存储区网络协议TCP建立连接的三次握手数据库概率论与数理统计推荐《数理统计学简史》当前第6页\共有95页\编于星期日\16点面试偏算法数据结构上的增删改查查找、遍历、排序算法分治、递归、回溯贪心、动态规划海量数据处理当前第7页\共有95页\编于星期日\16点基于各个数据结构上的增删改查字符串字符串库函数的编写，例如atoi等字符串查找、翻转、匹配数组查找（如二分查找、杨氏矩阵查找）链表翻转、遍历、查找、删除、合并Hash表查找树遍历（前序、中序、后序）set、map高级树的查找（红黑树、B树、R树）图遍历查找（DFS、BFS）最短路径算法当前第8页\共有95页\编于星期日\16点知道了考什么，怎么破当前第9页\共有95页\编于星期日\16点笔试面试常用算法穷举（递归回溯）——“万能的”求n个数的全排列&8皇后（N皇后问题）分治分而治之，然后归并递归回溯DFS空间换时间hashtable巧用数据结构堆能排序，考虑排序前后两个指针往中间扫若已经排好序，想想有无必要二分不能排序贪心最小生成树Prim,Krusal最短路dijkstra动态规划如01背包问题，每一步都在决策细节处理注意边界条件当前第10页\共有95页\编于星期日\16点各类算法的时间复杂度当前第11页\共有95页\编于星期日\16点O(1)到O(nlogn)O(1)基本运算，＋，－，＊，／，%，寻址Hash表的期望复杂度O(logn)二分查找O(n1/2)枚举约数O(n)线性查找建立堆O(nlogn)归并排序快速排序的期望复杂度基于比较排序的算法下界当前第12页\共有95页\编于星期日\16点O(n2)到O(nn)O(n2)集合里枚举所有二元组、朴素最近点对O(n3)集合里枚举三元组、Floyd最短路、普通矩阵乘法O(2n)枚举全部的子集O（2nn)TSP的动态规划算法O(n!)枚举全排列O(nn)枚举[1..n]的n维数组的全部元素……总结O(1)<O(logn)<O(n1/2)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O（2nn)<O(n!)<O(nn)当前第13页\共有95页\编于星期日\16点各种排序算法的时间复杂度当前第14页\共有95页\编于星期日\16点O(N)的时间复杂度能解决什么问题？当前第15页\共有95页\编于星期日\16点O(N)时间内能解决的问题字符串字符串循环位移最长回文子串数组寻找最小的K个数2-sum最大连续子数组和快排的partition奇偶排序荷兰国旗问题完美洗牌问题最大面积直方图最大连续乘积子数组查找排序杨氏矩阵查找出现次数超过一半的数字建立堆计数排序二叉查找树的前中后序遍历ManacherKMP当前第16页\共有95页\编于星期日\16点字符串翻转把字符串abcdef左旋转3位得到字符串defabc。要求时间复杂度为O(n)，空间复杂度为O(1)。暴力移位三步翻转（字符串abcdef->defabc）X：abc，Y：def；X->X^T，得：abc->cba；Y->Y^T，得：def->fedX^TY^T，得到：cbafed->defabc，即(X^TY^T)^T=YX当前第17页\共有95页\编于星期日\16点寻找最小的k个数输入1，2，3，4，5，6，7和8这8个数字请输出其中最小的4个数字：1，2，3和4当前第18页\共有95页\编于星期日\16点寻找和为定值的两个数输入数组1、2、4、7、11、15和数字15由于4+11=15，因此输出4和11解答：百试不厌：暴力穷举如果无序，先排序，排完序后，ij前后两个指针往中间扫当前第19页\共有95页\编于星期日\16点编程艺术github当前第20页\共有95页\编于星期日\16点第二部分、算法当前第21页\共有95页\编于星期日\16点如何学习算法？当前第22页\共有95页\编于星期日\16点算法学习方法论基础很重要学习什么，心中有大纲算法解决什么问题，解决策略是什么广搜一层一层往外遍历，寻找最短路径策略：队列最小生成树最小代价连接所有点策略：贪心（Prim：贪心+权重队列）Dijkstra寻找单源最短路径策略：贪心+非负权重队列Floyd多结点对的最短路径策略：动态规划方法论循序渐进对比联系从简单入手，追本溯源当前第23页\共有95页\编于星期日\16点如何学习算法之一要则一：循序渐进KMP当前第24页\共有95页\编于星期日\16点有一个算法，本科期间无数人被虐过，是哪个算法？当前第25页\共有95页\编于星期日\16点字符串的查找匹配有一个文本串S和一个模式串P请查找P在S中的位置当前第26页\共有95页\编于星期日\16点暴力！一步步往后匹配当前第27页\共有95页\编于星期日\16点继续暴力匹配失败，回溯当前第28页\共有95页\编于星期日\16点改进暴力！利用模式串中具有相同的前缀后缀不做没用的重复匹配当前第29页\共有95页\编于星期日\16点找模式串中最大的相同前缀后缀考察前缀后缀得到：最大前缀后缀公共元素长度字符ABCDABD最大前缀后缀公共元素长度0000120模式串的各个子串前缀后缀最大公共元素长度A空空0ABAB0ABCA,ABC,BC0ABCDA,AB,ABCD,CD,BCD0ABCDAA,AB,ABC,ABCDA,DA,CDA,BCDA1ABCDABA,AB,ABC,ABCD,ABCDAB,AB,DAB,CDAB,BCDAB2ABCDABDA,AB,ABC,ABCD,ABCDAABCDABD,BD,ABD,DABD,CDABDBCDABD0当前第30页\共有95页\编于星期日\16点失配时，模式串向右移动的位数为已匹配字符数-失配字符的上一位字符所对应的最大长度值字符ABCDABD最大前缀后缀公共元素长度0000120当前第31页\共有95页\编于星期日\16点基于《前后缀的最大公共元素长度》匹配1/2D跟空格失配时向右移动的位数=已匹配的字符数-上一位字符B对应的最大公共元素长度6-2=4再度失配，向右移动：2-0=2位字符ABCDABD最大前缀后缀公共元素长度0000120当前第32页\共有95页\编于星期日\16点基于《前后缀最大公共长度》匹配2/2A跟空格失配，向右移动一位D跟C失配时向右移动的位数为已匹配的字符数-上一位字符B对应的最大长度即：6-2=4匹配成功。字符ABCDABD前缀后缀最大公共元素长度0000120当前第33页\共有95页\编于星期日\16点“前后缀”概念引申出next数组前缀后缀的最大公共元素长度失配时移动位数：已匹配字符数-失配字符的上一位字符所对应的最大长度值next数组把上面的“最大长度值”整体向右移动一位，然后初始值赋为-1失配时移动位数：失配字符所在位置-失配字符对应的next值j-next[j]注意：无论是哪种匹配方法，得出的向右移动位数一样模式串ABCDABDnext-1000012模式串ABCDABD前后缀最大公共元素长度0000120当前第34页\共有95页\编于星期日\16点基于《next数组》匹配1/2Next数组失配时移动位数：j-next[j]j从0开始计数：向右移动6-2=4位再次失配向右移动：j-next[j]=2-0=2位字符ABCDABDNext值-1000012当前第35页\共有95页\编于星期日\16点基于《next数组》匹配2/2接上移动两位之后A跟空格不匹配，再次后移一位D处失配，向右移动j-next[j]=6-2=4位字符ABCDABDNext值-1000012当前第36页\共有95页\编于星期日\16点KMP算法假设现在文本串S匹配到i位置，模式串P匹配到j位置如果j=-1，或者当前字符匹配成功（即S[i]==P[j]），都令i++，j++，继续匹配下一个字符；如果j!=-1，且当前字符匹配失败（即S[i]!=P[j]），则令i不变，j=next[j]。此举意味着失配时模式串P相对于文本串S向右移动了j-next[j]位。当前第37页\共有95页\编于星期日\16点intKmpSearch(char*s,char*p){inti=0,j=0;intsLen=strlen(s);intpLen=strlen(p);while(i<sLen&&j<pLen){

//①如果j=-1，或者当前字符匹配成功（即S[i]==P[j]），都令i++，j++

if(j==-1||s[i]==p[j]){i++;j++;}else{

//②如果j!=-1，且当前字符匹配失败（即S[i]!=P[j]），则令i不变，j=next[j]

j=next[j];}}if(j==pLen)returni-j;elsereturn-1;}当前第38页\共有95页\编于星期日\16点next数组的递推计算对于值k，已有p0p1,...,pk-1=pj-kpj-k+1,...,pj-1，相当于next[j]=k。下面的问题是：已知next[0,...,j]，如何求出next[j+1]呢？pk=pjpk!=pj当前第39页\共有95页\编于星期日\16点当前第40页\共有95页\编于星期日\16点voidGetNext(char*p,intnext[]){intpLen=strlen(p);next[0]=-1;intk=-1;intj=0;while(j<pLen-1){

//p[k]表示前缀，p[j]表示后缀

if(k==-1||p[j]==p[k]){++k;++j;next[j]=k;}else{

//拿前缀去跟后缀匹配，如果pk跟pj失配，继续递归前缀索引p[next[k]]k=next[k];}}}当前第41页\共有95页\编于星期日\16点当前第42页\共有95页\编于星期日\16点如何学习算法之二要则二：把相关算法串联起来，相互比对贪心、动态规划当前第43页\共有95页\编于星期日\16点贪心与动规贪心：“最优子结构+局部最优”动态规划：“最优独立重叠子结构+全局最优”。枚举所有状态，然后剪枝，寻找最优状态同时将每一次求解子问题的结果保存在一张“表格”中以后再遇到重叠的子问题，从表格中保存的状态中查找（俗称记忆化搜索）当前第44页\共有95页\编于星期日\16点动态规划当前第45页\共有95页\编于星期日\16点两个简单的例子最短路径：A->B经过x1，x2，x3故枚举所有可能从A到B要经过的路径选择一条最优如何求最优比较如何比较？写DP方程，求min比如二维数组最小路径和一个二维矩阵M*N矩阵matrix中，找出一条路径，只能向右或向下，求路径经过元素之和最小当前位置(i,j)上一个位置只可能是(i-1，j)或(i,j-1)path[i][j]=min(path[i][j-1],path[i-1][j])+matrix[i][j]当前第46页\共有95页\编于星期日\16点寻找和为定值的多个数输入两个整数n和m，从数列1，2，3.......n中随意取几个数,使其和等于m,要求将其中所有的可能组合列出来。 list1.push_front(n);//典型的01背包问题 find_factor(sum-n,n-1);//放n，n-1个数填满sum-nlist1.pop_front();find_factor(sum,n-1);//不放n，n-1个数填满sum动态规划适用条件最优子结构独立重叠子问题当前第47页\共有95页\编于星期日\16点如何学习算法之三要则三：从简单入手，追本溯源二叉树、红黑树、2-3-4树、B树当前第48页\共有95页\编于星期日\16点追本溯源红黑树为何要有RB-Tree完全平衡完全二叉树高度平衡AVL树先理解二叉树的插入、删除后理解红黑树的插入修复、删除修复B树先学习2-3-4树，理解结点饱和分裂，结点稀缺合并为何？因为2-3-4树在计算机科学中是阶为4的B树意味着什么？意味着2-3-4树中每个结点的关键字数目是：1-3个（ceil(m/2)-1）<=n<=m-1m为阶数，即孩子树，等于4当前第49页\共有95页\编于星期日\16点二叉树到完全二叉树树的深度越小，搜索时间logn（n即为树的深度）当前第50页\共有95页\编于星期日\16点AVL树高度平衡树AVL树中任何节点的两个子树的高度最大差别为一当前第51页\共有95页\编于星期日\16点红黑树的5个性质每个结点要么是红的，要么是黑的。根结点是黑的。每个叶结点（叶结点即指树尾端NIL指针或NULL结点）是黑的。如果一个结点是红的，那么它的俩个儿子都是黑的。对于任一结点而言，其到叶结点树尾端NIL指针的每一条路径都包含相同数目的黑结点。

当前第52页\共有95页\编于星期日\16点二叉树的插入插入一个节点当前第53页\共有95页\编于星期日\16点红黑树的插入插入一个元素后，需要修复，修复有两种手段重新着色旋转操作：左旋与右旋当前第54页\共有95页\编于星期日\16点红黑树的插入修复代码3种插入修复情况当前第55页\共有95页\编于星期日\16点2-3-4树当前第56页\共有95页\编于星期日\16点2-3-4树的查找当前第57页\共有95页\编于星期日\16点2-3-4树的插入1/3当前第58页\共有95页\编于星期日\16点2-3-4树的插入2/3当前第59页\共有95页\编于星期日\16点2-3-4树的插入3/3关键字数要超过4时就要开始分裂4阶的B树的关键字数满足：大于等于1，小于等于3当前第60页\共有95页\编于星期日\16点2-3-4树一次完整的插入示例1/2不断插入多个元素的过程当前第61页\共有95页\编于星期日\16点2-3-4树一次完整的插入示例1/2接上，继续插入元素N、B、X当前第62页\共有95页\编于星期日\16点看过了红黑树的插入看过了2-3-4树分裂接下来，看另外一种新树它与红黑树最大的区别在于，它的结点可以有许多子女，从几个到几千个当前第63页\共有95页\编于星期日\16点B树出现缘由二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下

当前第64页\共有95页\编于星期日\16点一棵B树的示例查找文件29一直往下，3次磁盘IO操作和3次内存查找当前第65页\共有95页\编于星期日\16点B树的插入示例1/5一棵5阶（即树中任一结点至多含有4个关键字，5棵子树）B树根结点至少得有2个孩子5阶，2-4个key，3-5个childrenB树除根结点之外的结点（包括叶子结点）的关键字的个数n必须满足：（ceil(m/2)-1）<=n<=m-12<=关键字数<=4m为孩子数，即子树的数目，等于5当前第66页\共有95页\编于星期日\16点B树的插入示例2/5插入以下字符字母到一棵空的B树中非根结点关键字数小了（小于2个）就合并大了（超过4个）就分裂）：CNGAHEKQMFWLTZDPRXYS当前第67页\共有95页\编于星期日\16点B树的插入示例3/5CNGAHEKQMFWLTZDPRXYS③当咱们插入E,K,Q时，不需要任何分裂操作：④插入M需要一次分裂，M恰好是中间关键字元素，以致向上移到父节点中：当前第68页\共有95页\编于星期日\16点B树的插入示例4/5CNGAHEKQMFWLTZDPRXYS⑤插入F,W,L,T不需要任何分裂操作：⑥插入Z时，中间元素T上移到父节点中：当前第69页\共有95页\编于星期日\16点B树的插入示例5/5CNGAHEKQMFWLTZDPRXYS⑦插入D时，D上移到父节点中，然后字母P,R,X,Y陆续插入：⑧插入S时，中间元素Q上移到父节点中，Q上移导致父结点“DGMT”也满了，将父节点中的中间元素M上移到新形成的根结点中，从而致使树的高度增加一层。当前第70页\共有95页\编于星期日\16点B+树一棵m阶的B+树和m阶的B树的异同点在于：有n棵子树的结点中含有n-1个关键字所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。(而B树的叶子节点并没有包括全部需要查找的信息)所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。(而B树的非终节点也包含需要查找的有效信息)当前第71页\共有95页\编于星期日\16点B*树B*-tree是B+-tree的变体在B+树的基础上，所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针)；B*树中非根和非叶子结点再增加指向兄弟的指针；B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3（代替B+树的1/2）当前第72页\共有95页\编于星期日\16点总结有了二叉树，为何要有AVL平衡树？有了AVL树，为何要有红黑树？有了红黑树，为何要有B树？当前第73页\共有95页\编于星期日\16点海量数据处理当前第74页\共有95页\编于星期日\16点十个密匙哈希分治simhash算法外排序MapReduce多层划分BitmapBloomFilterTrie树数据库倒排索引当前第75页\共有95页\编于星期日\16点76万丈高楼平地起Reb-Blacktreeset/map（map同时拥有key和value，set的key就是value）multiset/multimap（允许重复键值）hashtablehashmap/hashset/hash_multiset/hash_multimap（允许重复键值）备注：C++11标准命名了基于hash函数实现的unordered_set/unordered_map/unordered_multiset/unordered_multimap相当于hash_set、hash_ma，和hash_multiset、hash_multimap。当前第76页\共有95页\编于星期日\16点77分而治之/hash映射+hash统计+堆/快速/归并排序海量日志数据，提取出某日访问百度次数最多的那个IP分而治之/hash映射，比如模1000，把整个大文件映射为1000个小文件hash_map(ip，value)来进行频率统计（hash_map对那1000个文件中的所有IP进行频率统计，然后依次找出1000个文件中频率最大的那个IP）再在这1000个最大的IP中，找出那个频率最大的IP当前第77页\共有95页\编于星期日\16点类似问题变形hash函数映射+hashmap统计+堆排有100W个关键字，长度小于等于50字节。用高效的算法找出top10的热词，并对内存的占用不超过1MB。假设已有10w个敏感词，现给你50个单词，查询这50个单词中是否有敏感词。单机5G内存，磁盘200T的数据，分别为字符串，然后给定一个字符串，判断这200T数据里面有没有这个字符串，怎么做？如果查询次数会非常的多,怎么预处理？当前第78页\共有95页\编于星期日\16点simHash的具体算法分词给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN/博客/结构/之/法/算法/之/道/的/作者/July”，然后为每个特征向量赋予权值：CSDN(4)博客(5)结构(3)之(1)法(2)算法(3)之(1)道(2)的(1)作者(5)July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。hash○通过hash函数计算各个特征向量的hash值，hash值为二进制数01组成的n-bit签名。比如“CSDN”的hash值Hash(CSDN)为100101，“博客”的hash值Hash(博客)为“101011”。就这样，字符串就变成了一系列数字。加权W=Hash*weight。W(CSDN)=100101*4=4-4-44-44，W(博客)=101011*5=5-55-555。合并将上述各个特征的加权结果累加，变成一个序列串。如：“4+5,-4+-5,-4+5,4+-5,-4+5,4+5”，得到“9,-9,1,-1,1”。降维对于n位签名的累加结果，如果大于0则置1