July_algorithm 10.面试精讲.pdf

《July_algorithm 10.面试精讲.pdf》由会员分享，可在线阅读，更多相关《July_algorithm 10.面试精讲.pdf（73页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、面试精讲七月算法邹博2015年11月15日10月算法在线班2/73时间复杂度 假定函数MyFunc()的时间复杂度为O(1)，则下列代码的时间复杂度关于整数n是多少？(NlogN)/(N)注：表示复杂度是紧的，如堆排序中，建堆的时间复杂度为(N)，而非(NlogN)；当然，可以说建堆的时间复杂度为O(NlogN)，因为O记号不要求上确界。10月算法在线班3/73时间复杂度分析 内层循环中，对于给定的i，j从 累加到i，循环次数为 外层循环中，i从1到n遍历，每次变成当前值的3倍，即1,3,9,27，通项为 将内层循环次数按照递增3倍做累加后，得循环总次数：3ii 32Nkkk3,2,1,03N

2、Timekkkk3133131323279313233281322732932332132110月算法在线班4/73图示分析 从下面的图示能够清楚的反映这一问题：上图中，当外层循环的i位于紫色位置时，内层循环执行的是紫色的；下次循环，当外层循环的i位于红色位置 3*i时，内层循环执行的是红色的，依次类推。所以，循环次数的上限为N。从而，时间复杂度为O(N)。10月算法在线班5/73集合的表达 将全集I划分为若干子集S1,S2,Sn，使得S1S2Sn=I，且S1S2Sn=。则S1,S2,Sn称为全集I的一个可行划分。思考：用何种数据结构方便表达呢？10月算法在线班6/73集合的性质 自反性(a)

3、，对称性(a、b)传递性：如果c是b的子结点，b是a的子结点，则a、b、c位于相同的集合中。由于集合中元素是等价的，选择任意一个元素作为代表，其他元素都指向该元素，即完成一个集合的表达；称指向元素为子结点，被指向元素为父结点。10月算法在线班7/73Code10月算法在线班8/73Code10月算法在线班9/73并查集的应用 某国家有N个小岛组成，经过多年的基础设施积累，若干岛屿之间建立了若干桥梁。先重新完善该国的行政区划，规定只要有桥梁连接的岛屿则归属同一个城市(可以通过其他岛屿中转)，问该国一共多少个城市？求给定图G的连通分量的数目。解决方案：集合划分10月算法在线班10/73Code10

4、月算法在线班11/73思考：有向图呢？对一个有向图，如果每个节点都存在到达其他任何节点的路径，那么就称它是强连通的。判断图是强连通图的算法：任取有向图G的某结点S，从S开始进行深度优先搜索，若可以遍历G的所有结点，则将G的所有边反向，再次从S开始进行深度优先搜索，如果再次能够遍历G的所有结点，则G是强连通图，两次搜索有一次无法遍历所有结点，则G不是强连通图。此外，上述搜索可以换成广度优先搜索等其他方案。10月算法在线班12/73Trie树 Trie树是一种哈希多叉树，又称字典树、单词查找树或前缀树，用于在大量字符串中快速检索。英文字母的字典树是一个26叉树 数字的字典树是一个10叉树。10月算

5、法在线班13/73Trie数的特点及性质 典型应用：统计和排序大量的字符串(但不仅限于字符串)，所以经常被文字处理系统用于文本词频统计。优点：利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较，查询效率比哈希表高。缺点：如果存在大量字符串且这些字符串基本没有公共前缀，则相应的Trie树将非常消耗内存。三个基本性质：根结点不包含字符，除根结点外每一个结点都只包含一个字符。从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串。每个结点的所有子结点包含的字符都不相同。10月算法在线班14/73Trie树举例 词典：a、b、c、aa、ab、ac、ba、ca、aba、abc

6、、baa、bab、bac、cab、abba、baba、caba、abaca、caaba10月算法在线班15/73Trie树举例10月算法在线班16/73压缩：左孩子-右兄弟10月算法在线班17/73对左孩子-右兄弟表示法的思考 只记录有效索引指针，形成如下结构 利用“左孩子-右兄弟”表示方法，如何将一颗树转换成二叉树？如何将N颗树(森林)转换成二叉树？10月算法在线班18/73树转换成二叉树10月算法在线班19/73树转二叉树的右孩子 任意一颗树转换成二叉树，右孩子为空的数目为原树非叶结点+1。对于一颗树(非二叉树)，因为任何一个非叶结点必然有孩子，所以，它必然有最右孩子。从而，这个最右孩子转

7、换到二叉树结点后，右指针必然为空。同时，根结点必然没有兄弟，所以，根结点转换成二叉树结点后，必然右孩子为空。任意颗树转换成二叉树，右孩子为空的数目为原树非叶结点+1。如果是若干个树转二叉树，这若干个树最右边的那个树，是没有右孩子的。10月算法在线班20/73Trie树应用举例 给定一颗边的权值都是正整数的树，求某两个结点间的路径S，使得该路径所包含的所有边权的异或值最大。A-B-C 34=7(最优解)A-B-D 36=5 C-B-D 46=210月算法在线班21/73算法分析 朴素解法枚举所有结点对，求得所有路径异或权。时间复杂度O(n2)问题分析异或的性质：ab=(ac)(bc)求出从根节点

8、到每个节点的异或值Xi，这样任意两个点(i,j)做异或XiXj即是他们之间的异或权(相同部分异或抵消)从根节点到每个节点的异或值可以通过一次深度优先搜索解决，时间复杂度O(n)问题转化为求n个数中异或值最大的两个数字10月算法在线班22/73利用Trie树 将数字看成二进制的0/1串，先将所有数字从最高位起放入一个二叉Trie树中；枚举每个数字a，从最高位开始，寻找尽量与a对应位不同的数字；时间复杂度O(len)；总体时间复杂度O(N*len)10月算法在线班23/73空间复杂度的简化 Trie树的状态转移函数：g(s,c)=t s表示当前状态，c表示转移条件，t表示下一个可接受状态：(DFA

9、的状态转移)base数组中的每一个元素相当于Trie树的一个节点，其值做状态转移的基值，check数组相当于校验值，用于检查该状态是否存在。bases+c=t checkt=s10月算法在线班24/73Trie树的双数组表示法10月算法在线班25/73Trie树逻辑结构10月算法在线班26/73Trie树的资源号修改10月算法在线班27/73资源号修改伪代码10月算法在线班28/73字符串的插入 记待插入字符串为a1a2ah-1ahah+1an，其中，在当前Trie树中找到了前缀a1a2ah-1，而ah是第一个未找到的字符，记Trie树中字符ah-1转移得到的结点为sr。算法：以sr为根，插入

10、新结点st：st由ah转移得到将st指向尾后缀ah+1an 这里，将后缀串ah+1an直接加入后缀池，减少不必要的分支，进一步降低空间复杂度。由于后缀池的引入，如果插入的字符串最后查找成功的字符没有分支，而是在后缀池中，如何操作？10月算法在线班29/73字符串的插入 记待插入字符串为a1a2ah-1ahah+k-1ah+kan，其中，在当前Trie树中找到了前缀a1a2ah-1，而ahah+k-1b1bm是在后缀池中，记Trie树中最后一个分支结点为sr，即字符ah-1转移得到sr。算法：以sr为根，插入新结点st：st由ahah+k-1转移得到以st为根，插入新结点su：su由b1转移得到

11、将su指向后缀池中的b2bm以st为根，插入新结点sv：sv由ah+k转移得到将sv指向后缀池中的ah+k+1an10月算法在线班30/73双数组Trie树结构总结 Trie树逻辑结构清晰简练，优雅自然，在海量数据中查找某数据，和海量数据规模无关，只和待查找数据长度本身有关，时间复杂度为O(len)，常常可以认为是O(1)。可以看做是以数据元素为关键字的多Hash结构；海量数据的复杂度分析未考虑内存调度等问题。双数组的存储结构晦涩难懂，增删困难。实践中，往往离线将海量数据建立Trie树双数组结构，少量删除时可以继续使用。若大量删除，则离线建立新的Trie树双数组结构，适时替换。10月算法在线班

12、31/73围棋中的正方形 围棋棋盘由横纵19*19条线组成，请问这些线共组成多少个正方形？假定只考虑横纵方向，忽略倾斜方向。10月算法在线班32/73算法分析 以(i,j)为右下角的正方形数目f(i,j)jijifjif,1,jijifjif,1,jijifjifjif,1,1max,10月算法在线班33/73算法分析jijifjif,1,1,10月算法在线班34/73算法结论 综上，得出递推关系：显然有初始关系：jijifjijifjifjif,1,1,1,1max,0,000,jfif10月算法在线班35/73Code10月算法在线班36/73思考 本题的关键是如何将问题分解成更小规模的问

13、题，从而解决问题。这个思想比题目本身更重要。事实上，jijif,min,jijifjijifjifjif,1,1,1,1max,10月算法在线班37/73Code210月算法在线班38/73如果手头没有编译器呢？如果数一下边长是1、2、318的正方形各有多少个，能够很快得到结论。21096371918182122210月算法在线班39/73字符串的交替连接 输入三个字符串s1、s2和s3，判断第三个字符串s3是否由前两个字符串s1和s2交错而成，即不改变s1和s2中各个字符原有的相对顺序，例如当s1=“aabcc”，s2=“dbbca”，s3=“aadbbcbcac”时，则输出true，但如果

14、s3=“accabdbbca”，则输出false。换个表述：s1和s2是s3的子序列，且s1s2=s310月算法在线班40/73问题说明 若s1和s2没有字符重复：遍历s3的同时，考察是否是s1和s2的字符即可；若字符重复：可以用压栈的方式解决；此外，还能用动态规划，代码更为简洁。10月算法在线班41/73状态转移函数 为算法表述方便，从1开始数：令dpi,j表示s31.i+j是否由s11.i和s21.j的字符组成：即dpi,j取值范围为true/false s1i=s3i+j且dpi-1,j为真，则dpij为真；s2j=s3i+j且dpi,j-1为真，则dpij为真；其它情况，dpij为假。

15、可以使用滚动数组降低空间复杂度。10月算法在线班42/73Code10月算法在线班43/73Code210月算法在线班44/73聪明的博弈 现有N个人，每人都从1到100按照自己的判断选一个整数，根据这N个数求均值E。规定选择最接近的那个人是获胜者。聪明的你作为参与者之一，你会选择哪个数呢？E32E3210月算法在线班45/73问题分析 如果每个人都随机选择，则N个数的期望收敛于50。因此，选择50*2/3=33.3的人将获胜。如果所有人都如此思考，则大家都会选择33.3，从而获胜的人应该是选择33.3*2/3=22.2，继续塌缩，最终所有人都选择最小数1，从而期望是0.66，大家全获胜。问题

16、是：不是所有人都足够聪明；总有“更”聪明的人选择对自己更有利的数；总有不打算胜利的人搅局：随机选数甚至选100等；10月算法在线班46/73将人群分成若干类别最直接想法的人什么都不想，随便从1-100中选一个，碰运气：假定占比是25%稍微思考的人稍作思考发现：如果所有人都随机选择，那么平均是应该是50。所以，将50的2/3，即33.33作为我的选择：假定占比25%继续思考的人如果所有人都选33.33，则平均数为33.33，那么，33.33的2/3，即22.22是胜利者。既然我会这么想，别人也会这么想，那么，如果大家都选22.22，则22.22的2/3，即14.8133是胜利者。继续塌缩下去，大

17、家会选择1。所以，我应该选择最小的数1：假定占比30%注意：由于是从1-100选数，是不能选0的。10月算法在线班47/73将人群分成若干类别 再思考的人不是所有人都会进行理性思考，从而不是所有人都选择1。因此，这个数字应该很小，但由于前面三类人的存在，大体应该是10左右。所以，我选择10假定这部分人的占比是19%最聪明的人：建立了“后验”模型，能够预知未来，他们能够直接判断出包括自己在内的N个数的平均值；假定这部分人的占比是1%不打算胜利的搅局人：随机选数或者直接选100等假定以上5类人中，以1%的概率随机产生10月算法在线班48/73六类人的总结人群分类A.最直接想法的人：25%B.稍微思

18、考的人：25%C.继续思考的人：30%D.再思考的人：19%E.最聪明的人：1%F.搅局的人：低概率随机产生若选中A类的人，则均匀分布随机产生1-100的值；若选中B/C/D类，则产生均值为33.3/1/10的高斯分布的值，方差影响可以忽略，假定B/C/D的标准差分别为10/3/3；由于E类绝顶聪明，他们的值和答案非常接近，则E类的均值和答案相同。所以，选中E类，则样本不累加，直接丢弃即可；搅局者可能异常聪明或愚钝，无关智商，因此在上述五类人群中以2%的概率随机产生搅局者。1万/10万/100万个样本的均值模拟为：25.84/25.25/25.18 如果在大量现实人群大量现实人群中，推荐选择2

19、5。10月算法在线班49/73Code10月算法在线班50/73任务安排 给定一台有m个储存空间的单进程机器；现有n个请求：第i个请求计算时需要占用Ri个空间，计算完成后，储存计算结果需要占用Oi个空间(其中OiRi)。问如何安排这n个请求的顺序，使得所有请求都能完成。如：m=14，n=2，R1,2=10,8，O1,2=5,6。可以先运行第一个任务，计算时占用10个空间，计算完成后占用5个空间，剩余9个空间执行第二个任务；但如果先运行第二个任务，则计算完成后仅剩余8个空间，第一个任务的计算空间就不够了。10月算法在线班51/73算法分析 第k个任务的计算占用空间加上前面k-1个任务的空间占用量

20、之和，越小越好。从而：得：将任务按照Ri-Oi降序排列即可。jjkkjkkjjkkkkjORORROROROOOOROOOO12112110月算法在线班52/73Code10月算法在线班53/73Palindrome Partitioning II 给定一个字符串str，将str划分成若干子串，使得每一个子串都是回文串。在所有可能的划分中，子串数目最少是多少？s=“aab”，最少子串数目为2“aa”，“b”“abacdccdaa”：最少子串数目为4“aba”、“c”、“dccd”、“aa”10月算法在线班54/73贪心法是不对的 贪心法：计算字符串S的最长回文子串，假定为A，则将S切分成B|A

21、|C三部分，对B和C分别递归计算最长回文子串。反例：ADACDCAEA 贪心划分：A|D|ACDCA|E|A 最少回文划分：ADA|CDC|AEA 10月算法在线班55/73Palindrome Partitioning 假设当前已经计算完成前缀串str0i-1的最少划分数目d0i-1，其中dj表示前缀串str0j的最少划分数目；则：要划分前缀串str0i，假定划分方案的最后一个子串为strj+1i，显然，根据题意strj+1i为回文串，并且str0j一定是最少划分，即：di=mindj+1|sj+1i是回文串，i-1j0 注意：strji是否为回文串，本身是个小的动态规划 若已知strj+1

22、i-1 是回文串，则只需判断strj=stri；上述整个过程从后向前分析仍然可以得到类似的结论；10月算法在线班56/73复习：题中题 在计算stri,i+1j是否是回文串这一子问题中，暴力也是无可厚非的。线性探索：j从i到n-1遍历即可。事实上，可以事先缓存所有的stri,i+1.j是回文串的那些记录：用二维布尔数组pnn就够了：pij的true/false表示了stri,i+1.j是否是回文串；它本身是个小的动态规划：如果已知stri+1.j-1是回文串，那么，判断stri,i+1.j是否是回文串，只需要判断stri=strj就可以。10月算法在线班57/73Code110月算法在线班58

23、/73思考 如果不止计算最小回文划分的切分数目，还要求最小回文划分本身，如何处理？记录前驱：每一个前缀串最小回文划分的前驱10月算法在线班59/73Code210月算法在线班60/73迷离傍地走 为庆祝强汉文武盛世暨废除和亲七百周年，武后决定拜孙武和王翦对春夏秋冬四官细君、昭君、探春、文成做军事训练。孙武和王翦分别负责四官的站军姿和踢正步科目。根据军训要求，只有在学会站军姿之后才能进行踢正步训练。由于四官天资差别，学习时间如下表。问：应该如何安排四官的学习时间，能够使得所有人学会这两项技能的时间最短？10月算法在线班61/73分析事件 若一个事件位于第一阶段且耗时较长，则不能将其放在第一个执行

24、，因为这将导致其他所有事件都需等待。如果一个事件位于第二阶段且耗时较长，则不能将其放在最后一个执行，因为这将延缓全部完成的时间。策略：所有事件中的最短时间是昭君踢正步(1小时)，由于该事件是第二阶段，则将其最后执行；此短时间是探春站军姿(2小时)，由于该事件是第一阶段，则将其优先执行；以此类推。10月算法在线班62/73Code10月算法在线班63/73三字母字符串组合 仅由三个字符A、B、C构成字符串，且字符串任意三个相邻元素不能完全相同。如“ACCCAB”不合法，“ABBCBCA”合法。求满足条件的长度为n的字符串个数。假定不考虑整数溢出 要求时间和空间复杂度不高于O(N)。10月算法在线

25、班64/73问题分析 若当前已经有了所有长度为n-1的合法字符串，如何在末端增加一个字符，形成长度为n的字符串呢？将长度为n-1字符串分成“末尾两个字符不相等”和“末尾两个字符相等”两种情况，各自数目记做dpn-10,dpn-11：10月算法在线班65/73dpn0结尾不相等/dpn1结尾相等 /dpn0=2*dpn-10+2*dpn-11，dpn1=dpn-10 初始条件dp10=3dp11=010月算法在线班66/73状态转移方程总结与改进 状态转移方程：滚动数组：使用滚动数组，将空间复杂度由O(N)降到O(1)01 1 11*201*20ndpndpndpndpndp0 1 1*20*2

26、0dpdpdpdpdp10月算法在线班67/73Code0 1 1*20*20dpdpdpdpdp10月算法在线班68/73矩阵表示与O(logN)时间复杂度 由状态转移方程：得矩阵形式：从而：0 1 1*20*20dpdpdpdpdp0212 1 0 1 0oldnewdpdpdpdp1113210212030212 1 0021202120212 1 002120212 1 00212 1 0 1 0nnnnnndpdpdpdpdpdpdpdpdpdp10月算法在线班69/73Code210月算法在线班70/73算法 所学并非无用，而是知识体系尚未达到能够用它的程度。思想恒久远，算法永流传

27、 据传，三国时期诸葛亮实施空城计。傅作义偷袭西柏坡，毛主席重演空城计。三千年前欧几里德发明辗转相除法，迄今仍被广大程序员所使用。10月算法在线班71/73结束语 知识的掌握是1,2,4,8,16的速度；每天递增0.01：1.01365=?设置适合自己的“学习率”。掌握算法的根本途径是多练习代码。书读百遍，其义自见。算法远远没有到此为止下列属于算法范畴吗？网站开发/OA工作流操作系统资源调度/编译原理词法、语法、语义分析/数据库设计/计算机网络协议包解析机器学习/数据挖掘/计算机视觉10月算法在线班72/73我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班73/73感谢大家恳请大家批评指正！