第7次东南大学面试算法讲座.ppt
《第7次东南大学面试算法讲座.ppt》由会员分享,可在线阅读,更多相关《第7次东南大学面试算法讲座.ppt(100页珍藏版)》请在三一文库上搜索。
1、东南大学面试 & 算法讲座 July,东南大学自动化研会 2014-7-16, 晚6:309:00,2,本次讲座大纲,笔试面试考什么 解决笔试面试题的常用算法 常用算法的时间复杂度 包括各类排序算法 O(N)时间复杂度内能解决的问题 包括KMP,最长回文子串Manacher算法 如何学习算法 相互串联 以Trie树、后缀树,贪心、动态规划为例 简单入手,追本溯源 二叉树、红黑树、2-3-4树、B树为例 海量数据处理面试题 十种解决之道,3,笔试面试考什么,4,笔试偏基础,语言基础 int hope; int* hope; double(*p) 3; void (*func) (); 操作系统
2、线程与进程的区别 产生死锁的条件 如何规避死锁 C+内存分配 堆、栈、自由存储区、全局/静态存储区,常量存储区 网络协议 TCP建立连接的三次握手 数据库 概率论与数理统计 推荐数理统计学简史,5,基础不够 补基础,语言 C : C 和指针 征服C 指针 C+: C+ Primer STL 源码剖析 Effective C+ 深度探索C+ 对象模型,6,面试偏算法,数据结构上的增删改查 查找、遍历、排序 算法 分治、递归、回溯 贪心、动态规划 海量数据处理,7,基于各个数据结构上的增删改查,字符串 字符串库函数的编写,例如atoi 等 字符串查找、翻转、匹配 数组 查找(如二分查找、杨氏矩阵查
3、找) 链表 翻转、遍历、查找、删除、合并 Hash表 查找 树 遍历(前序、中序、后序) set、map 高级树的查找(红黑树、B树、R树) 图 遍历 查找(DFS、BFS) 最短路径算法,8,知道了考什么,怎么破,9,笔试面试常用算法,穷举(递归回溯)“万能的” 求n个数的全排列 & 8皇后(N皇后问题) 分治 分而治之,然后归并 递归回溯 DFS 空间换时间 hashtable 巧用数据结构 堆 能排序,考虑排序 前后两个指针往中间扫 若已经排好序,想想有无必要二分 不能排序 贪心 最小生成树 Prim, Krusal 最短路 dijkstra 动态规划 如 01背包问题,每一步都在决策
4、细节处理 注意边界条件,10,各类算法的时间复杂度,11,O(1) 到 O(nlogn),O(1) 基本运算, ,%,寻址 Hash表的期望复杂度 O(logn) 二分查找 O(n1/2) 枚举约数 O(n) 线性查找 建立堆 O(nlogn) 归并排序 快速排序的期望复杂度 基于比较排序的算法下界,12,O(n2) 到 O(nn),O(n2) 集合里枚举所有二元组、朴素最近点对 O(n3) 集合里枚举三元组、Floyd最短路、普通矩阵乘法 O(2n) 枚举全部的子集 O(2nn) TSP的动态规划算法 O(n!) 枚举全排列 O(nn) 枚举1n的n维数组的全部元素 总结 O(1) O(lo
5、gn) O(n1/2) O(n) O(nlogn) O(n2) O(n3) O(2n) O(2nn) O(n!) O(nn),13,各种排序算法的时间复杂度,14,O(N)的时间复杂度能解决什么问题?,15,O(N)时间内能解决的问题,字符串 字符串循环位移 最长回文子串 数组 寻找最小的K个数 2-sum 最大连续子数组和 快排的partition 奇偶排序 荷兰国旗问题 完美洗牌问题 最大面积直方图 最大连续乘积子数组 查找排序 杨氏矩阵查找 出现次数超过一半的数字 建立堆 计数排序 二叉查找树的前中后序遍历 KMP Manacher,16,字符串翻转,翻转 定义字符串左旋转操作:把字符串
6、前面的若干个字符移动到字符串尾部,如把字符串 abcdef 左旋转 3 位得到字符串 defabc。 要求时间复杂度为 O(n),空间复杂度为 O(1)。 暴力移位 三步翻转(字符串 abcdef - defabc) X:abc,Y:def; X-XT,得:abc-cba;Y-YT,得:def-fed XTYT,得到:cbafed-defabc,即(XTYT)T=YX,17,寻找最小的k个数,输入n个整数,输出其中最小的k个。 例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。,18,最大子数组最大和,题目描述 输入一个整形数组,数组里有正数也有负数。数组中连
7、续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。 i)一维:输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,因此输出为该子数组的和18。 暴力循环 O(N)遍历 1 -2 3 10 -4 7 2 -5 b : 0 1 -1 3 13 9 16 18 13 sum: 0 1 1 3 13 13 16 18 18,19,ii) 二维 iii)子数组” 并不只是一个二维数组或矩形,而是联通的元素(上下或左右相邻即视为联通) iv)如果是个轮胎呢?,20,寻找和为定值的两个数,
8、输入一个数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。 要求时间复杂度是O(N)。如果有多对数字的和等于输入的数字,输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。 解答: 百试不厌:暴力穷举 如果无序,先排序,排完序后,i j前后两个指针往中间扫,21,快速排序算法的一个实现,一前一后两指针同往后扫 j 指针从第一个元素扫到倒数第二个,遇到比主元小,(i+1)与 j 所指元素互换 PARTITION(A, p, r) 1 x Ar 2 i p - 1 3 for j p to r - 1 4 do if Aj
9、 x 5 then i i + 1 6 exchange Ai Aj 7 exchange Ai + 1 Ar 8 return i + 1 QUICKSORT(A, p, r) 1 if p r 2 then q PARTITION(A, p, r) /关键 3 QUICKSORT(A, p, q - 1) 4 QUICKSORT(A, q + 1, r),22,快速排序实现之步骤一,int partition(int data,int lo,int hi) int key=datahi; /以最后一个元素,datahi为主元 int i=lo-1; for(int j=lo;jhi;j+)
10、 /注,j从p指向的是r-1,不是r。 if(dataj=key) i=i+1; swap( ,23,快速排序实现之步骤二,void QuickSort(int data, int lo, int hi) if (lohi) int k = partition(data, lo, hi); QuickSort(data, lo, k-1); QuickSort(data, k+1, hi); ,24,25,奇偶排序,题目描述 输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。 解法: 暴力移位 维护两个指针,步骤如下:
11、 一个指针指向数组的第一个数字,向后移动; 一个指针指向最后一个数字,向前移动; 如果第一个指针指向的数字是偶数且第二个指针指向的数字是奇数,我们就交换这两个数字。 变形: 给定一个整数数组,其元素分为正数、负数和0,现请把正数放左边,负数放右边,0在中间 荷兰国旗问题,26,荷兰国旗问题,题目描述 相同的球放到一起,让你按顺序输出红白蓝三种颜色的球,可以用012来表示,要求只能扫描一次数组 将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。,27,荷兰国旗问题思路,类似快排中partition过程,用三个指针,一前begin,一中current,一后end,current遍
12、历 整个数组序列: current指0,与begin交换,而后current+,begin+; current指1,不做任何交换(即球不动),而后current+; current指2,与end交换,而后,current指针不动,end-。 快排中的partition过程?,28,解决步骤1 current指0,与begin交换 而后current+,begin+ current指1,不做任何交换 而后current+ current指2,与end交换 而后,current不动,end-,29,解决步骤2 current指0,与begin交换 而后current+,begin+ current
13、指1,不做任何交换 而后current+ current指2,与end交换 而后current不动,end-,30,再进一步,题目描述 给定一个未排序的整数数组,有正数和负数,重新排列使得负数在正数前面,并且要求不改变原来的正负数之间的相对顺序 1 7 -5 9 -12 15 -5 -12 1 7 9 15,31,如何降低时间复杂度,减少不必要的操作 比如寻找出现次数超过一半的数字 数组排完序后直接输出第N/2处的那个数,不必再统计每个数字的出现次数 空间换时间 比如借助Hash表达到快速映射的目的 根据问题本身的特性使用对应的技巧 比如KMP算法中,对模式串的预处理,通过实现求解出一个nex
14、t数组后,后续匹配失配时直接查next数组得到下一次匹配的位置。 巧妙的算法 比如最长回文子串Manacher算法,32,字符串匹配KMP,朴素算法 O( (n-m+1)m ) 有限自动机算法 O(n) KMP O(n),33,Knuth - Morris - Patt,KMP O(n),34,求模式串的next,35,Next的描述性说法,对于Aj =a0 a1 .aj-1 aj,查找字符串Aj的最大相等k前缀和k后缀。 即:查找满足条件的最大的k,使得 a0 a1 .ak-1 ak = aj-k aj-k+1.aj-1 aj 则对于pattern的前j+1序列字符 若patternk+1=
15、patternj+1 nextj+1=next(j)+1 若patternk+1patternj+1 如果此时 pattern nextk + 1 = patternj + 1,则nextj + 1 = nextk + 1 否则重复此过程。,36,求字符串的最长回文子串,回文子串的定义: 给定字符串str,若s同时满足以下条件: s是str的子串 s是回文串 则,s是str的回文子串。求str中最长的那个回文子串。 解决策略 枚举中心位置,O(N2) Manacher算法,线性O(N),37,Manacher 算法step1预处理,每个字符两边插入一个特殊的符号# abbc #a#b#b#c#
16、 aba #a#b#a# 继续插入一个字符 字符串12212321 S = “$#1#2#2#1#2#3#2#1#“; 用一个数组 Pi 来记录以字符Si为中心的最长回文子串向左/右扩张的长度(包括Si) 比如S和P的对应关系 S # 1 # 2 # 2 # 1 # 2 # 3 # 2 # 1 # P 1 2 1 2 5 2 1 4 1 2 1 6 1 2 1 2 1 其中,Pi-1正好是原字符串中回文串的总长度,38,Manacher 算法step 2计算Pi,增加两个辅助变量id和mx id表示最大回文子串中心的位置 mx则为id+Pid,也就是最大回文子串的边界。得到一个很重要的结论:
17、如果mx i,那么Pi = Min(P2 * id - i, mx - i) 令j = 2 * id - i,也就是说j是i关于id的对称点。 当 mx - i Pj ,以Sj为中心的回文子串被包含在以Sid为中心的回文子串中,因 i 和 j 对称,以Si为中心的回文子串必然被包含在以Sid为中心的回文子串中,所以Pi = Pj。 当 Pj = mx - i ,以Sj为中心的回文子串不一定被完全包含于以Sid为中心的回文子串中,但是基于对称性可知,图中两个绿框所包围的部分是相同的,也就是说以Si为中心的回文子串,其向右至少会扩张到mx的位置,也就是说 Pi = mx - i。,39,代码线性时
18、间解决最长回文(Manacher),void Manacher() int i, mx = 0; int id; for(i=1; i i ) pi = MIN( p2*id-i, mx-i ); else /mx mx ) mx = pi + i; id = i; ,40,如何学习算法?,41,算法学习方法论,基础很重要 学习什么,心中有大纲 算法解决什么问题,解决策略是什么 广搜 一层一层往外遍历,寻找最短路径 策略:队列 最小生成树 最小代价连接所有点 策略:贪心(Prim:贪心+权重队列) Dijkstra 寻找单源最短路径 策略:贪心+非负权重队列 Floyd 多结点对的最短路径 策
19、略:动态规划 方法论 对比联系 从简单入手,追本溯源,42,要则一:把相关算法串联起来,相互比对 比如trie树、后缀树 贪心、动态规划 要则二:从简单入手,追本溯源 二叉树、红黑树、2-3-4树、B树,43,Trie 树,每个节点是一个字母 从根到某节点的路径作为一个单词 每个节点维护一个boolean值 优化: 压缩节点 时间复杂度: 查找O(len) 空间复杂度: 跟公共前缀有关,44,44,存储前缀,统计后缀,Trie树 + TOP K hashmap+堆,hashmap+堆统计出如10个近似的热词,45,没这么简单,(讨论) 搜索引擎的智能提示 注意只能解决前缀的问题 如何存储?分布
20、? 有无slave & master? P2P? 如何更新? 尽量透明? 中文怎么处理? 化成拼音? 用途:最长前缀匹配!,46,后缀树 1/4,以字符串S=XMADAMYX为例,它的长度为8,所以S18, S28, . , S88都算S的后缀,我们一般还把空字串也算成后缀。这样,我们一共有如下后缀(对于后缀Sin,我们说这项后缀起始于i): S18, XMADAMYX, 也就是字符串本身,起始位置为1 S28, MADAMYX,起始位置为2 S38, ADAMYX,起始位置为3 S48, DAMYX,起始位置为4 S58, AMYX,起始位置为5 S68, MYX,起始位置为6 S78, Y
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 东南大学 面试 算法 讲座
链接地址:https://www.31doc.com/p-2608205.html