第7次东南大学面试&算法讲座.ppt

东南大学·面试 & 算法讲座 July,东南大学自动化研会 2014-7-16, 晚6:30~9:00,2,本次讲座大纲,笔试面试考什么 解决笔试面试题的常用算法 常用算法的时间复杂度 包括各类排序算法 O(N)时间复杂度内能解决的问题 包括KMP，最长回文子串Manacher算法 如何学习算法 相互串联 以Trie树、后缀树，贪心、动态规划为例 简单入手，追本溯源 二叉树、红黑树、2-3-4树、B树为例 海量数据处理面试题 十种解决之道,3,笔试面试考什么,4,笔试偏基础,语言基础 int hope; int* hope; double(*p) [3]; void (*func) (); 操作系统 线程与进程的区别 产生死锁的条件 如何规避死锁 C++内存分配 堆、栈、自由存储区、全局/静态存储区，常量存储区 网络协议 TCP建立连接的三次握手 数据库 概率论与数理统计 推荐《数理统计学简史》,5,基础不够 补基础,语言 C ： 《C 和指针》 《征服C 指针》 C++： 《C++ Primer》 《STL 源码剖析》 《Effective C++》 《深度探索C++ 对象模型》,6,面试偏算法,数据结构上的增删改查 查找、遍历、排序 算法 分治、递归、回溯 贪心、动态规划 海量数据处理,7,基于各个数据结构上的增删改查,字符串 字符串库函数的编写，例如atoi 等 字符串查找、翻转、匹配 数组 查找（如二分查找、杨氏矩阵查找） 链表 翻转、遍历、查找、删除、合并 Hash表 查找 树 遍历（前序、中序、后序） set、map 高级树的查找（红黑树、B树、R树） 图 遍历 查找（DFS、BFS） 最短路径算法,8,知道了考什么，怎么破,9,笔试面试常用算法,穷举（递归回溯）——“万能的” 求n个数的全排列 & 8皇后（N皇后问题） 分治 分而治之，然后归并 递归回溯 DFS 空间换时间 hashtable 巧用数据结构 堆 能排序，考虑排序 前后两个指针往中间扫 若已经排好序，想想有无必要二分 不能排序 贪心 最小生成树 Prim, Krusal 最短路 dijkstra 动态规划 如 01背包问题，每一步都在决策 细节处理 注意边界条件,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(logn) 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,字符串翻转,翻转 定义字符串左旋转操作：把字符串前面的若干个字符移动到字符串尾部,如把字符串 abcdef 左旋转 3 位得到字符串 defabc。

要求时间复杂度为 O(n)，空间复杂度为 O(1) 暴力移位 三步翻转（字符串 abcdef - defabc） X：abc，Y：def； X-X^T，得：abc-cba；Y-Y^T，得：def-fed X^TY^T，得到：cbafed-defabc，即(X^TY^T)^T=YX,17,寻找最小的k个数,输入n个整数，输出其中最小的k个 例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和418,最大子数组最大和,题目描述 输入一个整形数组，数组里有正数也有负数数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和求所有子数组的和的最大值要求时间复杂度为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,寻找和为定值的两个数,输入一个数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。

要求时间复杂度是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 ← A[r] 2 i ← p - 1 3 for j ← p to r - 1 4 do if A[j] ≤ x 5 then i ← i + 1 6 exchange A[i] A[j] 7 exchange A[i + 1] A[r] 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=data[hi]; //以最后一个元素，data[hi]为主元 int i=lo-1; for(int j=lo;jhi;j++) ///注，j从p指向的是r-1，不是r。

{ if(data[j]=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) 解法： 暴力移位 维护两个指针，步骤如下： 一个指针指向数组的第一个数字，向后移动； 一个指针指向最后一个数字，向前移动； 如果第一个指针指向的数字是偶数且第二个指针指向的数字是奇数，我们就交换这两个数字 变形： 给定一个整数数组，其元素分为正数、负数和0，现请把正数放左边，负数放右边，0在中间 荷兰国旗问题,26,荷兰国旗问题,题目描述 相同的球放到一起，让你按顺序输出红白蓝三种颜色的球，可以用012来表示，要求只能扫描一次数组 将乱序的红白蓝三色小球排列成有序的红白蓝三色的同颜色在一起的小球组。

27,荷兰国旗问题思路,类似快排中partition过程，用三个指针，一前begin，一中current，一后end，current遍历 整个数组序列： 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指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算法中，对模式串的预处理，通过实现求解出一个next数组后，后续匹配失配时直接查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序列字符 若pattern[k+1]==pattern[j+1] next[j+1]=next(j)+1 若pattern[k+1]≠pattern[j+1] 如果此时 pattern[ next[k] + 1 ] == pattern[j + 1]，则next[j + 1] = next[k] + 1 否则重复此过程36,求字符串的最长回文子串,回文子串的定义： 给定字符串str，若s同时满足以下条件： s是str的子串 s是回文串 则，s是str的回文子串求str中最长的那个回文子串 解决策略 枚举中心位置，O(N2) Manacher算法，线性O(N),37,Manacher 算法step1——预处理,每个字符两边插入一个特殊的符号# abbc → #a#b#b#c# aba → #a#b#a# 继续插入一个字符 字符串12212321→ S[] = “$#1#2#2#1#2#3#2#1#“; 用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度（包括S[i]） 比如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 其中，P[i]-1正好是原字符串中回文串的总长度,38,Manacher 算法step 2——计算P[i],增加两个辅助变量id和mx id表示最大回文子串中心的位置 mx则为id+P[id]，也就是最大回文子串的边界。

得到一个很重要的结论： 如果mx 。