July_algorithm 1.链表栈队列.pdf

《July_algorithm 1.链表栈队列.pdf》由会员分享，可在线阅读，更多相关《July_algorithm 1.链表栈队列.pdf（69页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、链表、栈与队列七月算法邹博2015年10月17日10月算法在线班2/总论 算法包罗万象 推理、逻辑、“机智”演绎、归纳、类比 严格归纳 算法是脑力的游戏 合理运用算法，能够获得更高的效率 时间复杂度优先 空间复杂度优先 时间复杂度和空间复杂度的折中10月算法在线班3/系统的“数数”围棋棋盘由横纵19*19条线组成，这些线共组成多少个正方形？思路：边长为1的正方形多少个？边长为2的呢？边长为3、4的呢？以某点为右下角的正方形有多少个？把所有点的正方形相加。系统的遍历不漏不重：深度优先搜索、广度优先搜索前序遍历、中序遍历、后序遍历思考：给定N个数和某定值sum，从N个数中取若干个数，要求它们的和是

2、sum，输出所有的取法。子集和数问题10月算法在线班4/机智：“战平即可出线”足球比赛，一个小组有8支球队进行单循环赛，胜者得3分，平得1分，负不得分，积分最高的4支出线，则出线至少需要_分，未出线最多可能有_分。10月算法在线班5/战况分析 8支球队中，3支强队各自战胜其他5支弱队，而5支弱队之间比赛全部战平。则5支弱队中积分全部是4分，可以采用净胜球或抽签选5支弱队中的1支作为第4名出线。8支球队中，5支强队假定为甲、乙、丙、丁、戊，他们各自战胜其他3支弱队，同时，5支强队之间的战况为：甲战胜乙丙，乙战胜丙丁，丙战胜丁戊，丁战胜戊甲，戊战胜甲乙，则这5支强队同时胜5场，输2场，同积15分。

3、可以采用净胜球或抽签选5支强队中的1支作为第5名而被淘汰。10月算法在线班6/逻辑推理：完形填空 皇帝不是穷人，在守财奴之中也有穷人，所以，有一些_并不是_。10月算法在线班7/使用离散数学分析该题目 p：这个人是皇帝 q：这个人是穷人 r：这个人是守财奴 皇帝不是穷人：pq 在守财奴之中也有穷人：x(xr xq)10月算法在线班8/分析过程 r：这个人是守财奴 p：这个人是皇帝 有一些 守财奴 并不是 皇帝。本题的思想，在分支限界中将再次遇到。10月算法在线班9/系统：字符串表达式的计算 a+b*(c-d)+e 朴素算法 逆波兰表达式 栈的典型应用10月算法在线班10/天平与假币 现在有16

4、枚外形相同的硬币，其中一枚是假币，且已知假币比真币重量轻。先给定一架没有砝码的天平，问至少需要多少次称量才能找到这枚假币？思考：给出一种称量方案容易，但如何证明这种方案用到的称量次数最少呢？10月算法在线班11/解析 将16枚硬币分成A:5枚、B:5枚、C:6枚3堆。先用天平称量A和B，若A(或者B)轻，则可以通过两次称量找出5枚中的轻者；若A、B平衡，仍然可以通过两次称量找出C:6枚中的轻者。找5枚或者6枚中的1枚轻者，可以任选4枚，天平两端各放两枚，无论平或者不平，都能够再用1次称量找到轻者。10月算法在线班12/理论下界 既然一次天平称量能得到左倾、右倾、平衡3种情况，则把一次称量当成一

5、位编码，该编码是3进制的。问题转换为：需要多少位编码，能够表示16呢？答：假定需要n位，则：3n16 取对数后计算得到n2.52，这表示至少3次才能找到该轻质的假币。思考：快速排序的Partition过程。10月算法在线班13/本次主要内容链表链表相加链表部分翻转链表划分链表去重堆栈括号匹配最长括号匹配计算逆波兰表达式队列最短路径条数拓扑排序思考题：直方图矩形面积/收集雨水问题10月算法在线班14/链表相加 给定两个链表，分别表示两个非负整数。它们的数字逆序存储在链表中，且每个结点只存储一个数字，计算两个数的和，并且返回和的链表头指针。如：输入：243、564，输出：70810月算法在线班15

6、/问题分析 输入：2-4-3、5-6-4，输出：7-0-8 因为两个数都是逆序存储，正好可以从头向后依次相加，完成“两个数的竖式计算”。10月算法在线班16/Code10月算法在线班17/说明 因为两个数字求和的范围是0,18，进位最大是1，从而，第i位相加不会影响到第i+2位的计算。在发现一个链表为空后，直接结束for循环。最后只需要进位和较长链表的当前结点相加，较长链表的其他结点直接拷贝到最终结果即可。没有提高时间复杂度，trick而已。10月算法在线班18/链表的部分翻转 给定一个链表，翻转该链表从m到n的位置。要求直接翻转而非申请新空间。如：给定12345，m=2，n=4，返回1432

7、5。假定给出的参数满足：1mn链表长度。10月算法在线班19/分析 空转m-1次，找到第m-1个结点，即开始翻转的第一个结点的前驱，记做head；以head为起始结点遍历n-m次，将第i次时，将找到的结点插入到head的next中即可。即头插法10月算法在线班20/Code10月算法在线班21/链表划分 给定一个链表和一个值x，将链表划分成两部分，使得划分后小于x的结点在前，大于等于x的结点在后。在这两部分中要保持原链表中的出现顺序。如：给定链表143252和x=3，返回122435。10月算法在线班22/问题分析 分别申请两个指针p1和p2，小于x的添加到p1中，大于等于x的添加到p2中；最

8、后，将p2链接到p1的末端即可。时间复杂度是O(N)，空间复杂度为O(1)；该问题其实说明：快速排序对于单链表存储结构仍然适用。注：不是所有排序都方便使用链表存储，如堆排序，将不断的查找数组的n/2和n的位置，用链表做存储结构会不太方便。10月算法在线班23/Code10月算法在线班24/排序链表中去重 给定排序的链表，删除重复元素，只保留重复元素第一次出现的结点。如：给定：233578889910 返回：2357891010月算法在线班25/问题分析 若p-next的值和p的值相等，则将p-next-next赋值给p，删除p-next；重复上述过程，直至链表尾端。10月算法在线班26/Cod

9、e10月算法在线班27/Code2 分析该代码的正确性10月算法在线班28/排序链表中去重2 若题目变成：若发现重复元素，则重复元素全部删除，代码应该怎么实现呢？如：给定：233578889910 返回：2571010月算法在线班29/Code10月算法在线班30/小结 可以发现，纯链表的题目，往往不难，但需要需要扎实的Coding基本功，在实现过程中，要特别小心next的指向，此外，删除结点时，一定要确保该结点不再需要。小心分析引用类型的指针。10月算法在线班31/stack 堆栈是一种特殊的线性表，只允许在表的顶端top进行插入或者删除操作，是一种操作受限制的线性表。栈元素服从后进先出原则

10、 LIFOLast In First Out10月算法在线班32/括号匹配 给定字符串，仅由()六个字符组成。设计算法，判断该字符串是否有效。括号必须以正确的顺序配对，如：“()”、“()”是有效的，但“()”无效。10月算法在线班33/以下算法是否可行 对于给定的字符串str0N-1，它的前缀串str0k小括号的左括号减去小括号的右括号的数目，记做p0；同理使用p1、p2记录中括号和大括号的信息 思路：将k从0到N-1遍历：对于0kN-2：p00、p10，p20 对于k=N-1，p0=0、p1=0，p2=0 则字符串括号匹配，否则，不匹配。10月算法在线班34/算法分析 在考察第i位字符c与

11、前面的括号是否匹配时：如果c为左括号，开辟缓冲区记录下来，希望c能够与后面出现的同类型最近右括号匹配。如果c为右括号，考察它能否与缓冲区中的左括号匹配。这个匹配过程，是检查缓冲区最后出现的同类型左括号即：后进先出栈10月算法在线班35/括号匹配算法流程 从前向后扫描字符串：遇到左括号x，就压栈x；遇到右括号y：如果发现栈顶元素x和该括号y匹配，则栈顶元素出栈，继续判断下一个字符。如果栈顶元素x和该括号y不匹配，字符串不匹配；如果栈为空，字符串不匹配；扫描完成后，如果栈恰好为空，则字符串匹配，否则，字符串不匹配。10月算法在线班36/Code10月算法在线班37/queue 队列是一种特殊的线性

12、表，只允许在表的前端front进行删除操作，在表的后端rear进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列元素服从先进先出原则 FIFOFirst In First Out10月算法在线班38/最短路径条数问题 给定如图所示的无向连通图，假定图中所有边的权值都为1，显然，从源点A到终点T的最短路径有多条，求不同的最短路径的数目。10月算法在线班39/算法分析 权值相同的最短路径问题，则单源点Dijkstra算法退化成BFS广度优先搜索，假定起点为0，终点为N：结点步数step0N-1初始化为0路径数目pathNum0N-1初始化

13、为0pathNum0=1 若从当前结点i扩展到邻接点j时：若stepj为0，则 stepj=stepi+1，pathNj=pathNi若stepj=stepi+1，则 pathNj+=pathNi 可考虑一旦扩展到结点N，则提前终止算法。10月算法在线班40/Code10月算法在线班41/拓扑排序 对一个有向无环图(Directed Acyclic Graph，DAG)G进行拓扑排序，是将G中所有顶点排成线性序列，使得图中任意一对顶点u和v，若边(u,v)E(G)，则u在线性序列中出现在v之前。一种可能的拓扑排序结果2-8-0-3-7-1-5-6-9-4-11-10-1210月算法在线班42/

14、拓扑排序的方法 从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它；从网中删去该顶点，并且删去从该顶点发出的全部有向边；重复上述两步，直到剩余的网中不再存在没有前趋的顶点为止。10月算法在线班43/Code10月算法在线班44/拓扑排序的进一步思考拓扑排序算法可以发现圈；其本质是不断输出入度为0的点；可以用队列(或者栈)保存入度为0的点，避免每次遍历所有点查找入度；排序列表中的点需要更新与之连接的点的入度。入度减小1之后，如果为0，放入队列(或者栈)中。拓扑排序其实是给定了结点的一组偏序关系。“拓扑”一词的本意不限于此，在GIS中，它往往指点、线、面、体之间的相互邻接关系，即“橡皮泥集合

15、”通过揉捏几何形体而不受影响的空间相互关系。存储这些关系，往往能够对某些算法带来好处。如：计算不自交的空间曲面是否能够围成三维体任意三维边都邻接两个三维曲面。10月算法在线班45/扩展：拓扑的几何含义 一种关系：如三维数据间的拓扑关系10月算法在线班46/三维拓扑重建10月算法在线班47/视角再次放大面面、面线的拓扑10月算法在线班48/最长括号匹配 给定字符串，仅包含左括号(和右括号)，它可能不是括号匹配的，设计算法，找出最长匹配的括号子串，返回该子串的长度。如：()：2()()：4()()：6()()：610月算法在线班49/算法分析记起始匹配位置start=-1；最大匹配长度ml=0：考

16、察第i位字符c：如果c为左括号，压栈；如果c为右括号，它一定与栈顶左括号匹配；如果栈为空，表示没有匹配的左括号，start=i，为下一次可能的匹配做准备如果栈不空，出栈(因为和c匹配了)；如果栈为空，i-start即为当前找到的匹配长度，检查i-start是否比ml更大，使得ml得以更新；如果栈不空，则当前栈顶元素t是上次匹配的最后位置，检查i-t是否比ml更大，使得ml得以更新。注：因为入栈的一定是左括号，显然没有必要将它们本身入栈，应该入栈的是该字符在字符串中的索引。10月算法在线班50/Code如果c为左括号，压栈；如果c为右括号，它一定与栈顶左括号匹配；如果栈为空，表示没有匹配的左括号

17、，start=i，为下一次可能的匹配做准备如果栈不空，出栈(因为和c匹配了)；如果栈为空，i-start即为当前找到的匹配长度，检查i-start是否比ml更大，使得ml得以更新；如果栈不空，则当前栈顶元素t是上次匹配的最后位置，检查i-t是否比ml更大，使得ml得以更新。10月算法在线班51/观察与思考 经过分析算法得知，只有在右括号和左括号的发生匹配时，才有可能更新最终解；做记录前缀串p0i-1中左括号数目与右括号数目的差x，若x为0时，考察是否最终解得以更新即可。这个差x，其实是入栈的数目，代码中用“深度”deep表达；由于可能出现左右括号不相等尤其是左括号数目大于右括号数目，所以，再从

18、右向前扫描一次。这样完成的代码，用deep值替换了stack栈，空间复杂度由O(N)降到O(1)。10月算法在线班52/Code10月算法在线班53/half-part10月算法在线班54/p=()()10月算法在线班55/空间复杂度仅O(1)的最长括号匹配分析括号串p=()()：10月算法在线班56/逆波兰表达式RPN 逆波兰表达式Reverse Polish Notation，又叫后缀表达式。习惯上，二元运算符总是置于与之相关的两个运算对象之间，即中缀表达方法。波兰逻辑学家J.Lukasiewicz于1929年提出了运算符都置于其运算对象之后，故称为后缀表示。如：中缀表达式：a+(b-c)

19、*d 后缀表达式：abc-d*+10月算法在线班57/运算与二叉树 事实上，二元运算的前提下，中缀表达式可以对应一颗二叉树；逆波兰表达式即该二叉树后序遍历的结果。中缀表达式：a+(b-c)*d 后缀表达式：abc-d*+该结论对多元运算也成立，如“非运算”等10月算法在线班58/计算逆波兰表达式 计算给定的逆波兰表达式的值。有效操作只有+-*/，每个操作数都是整数。如：2,1,+,3,*：9(2+1)*3 4,13,5,/,+：64+(13/5)10月算法在线班59/逆波兰表达式的计算方法 abc-d*+若当前字符是操作数，则压栈 若当前字符是操作符，则弹出栈中的两个操作数，计算后仍然压入栈中

20、 若某次操作，栈内无法弹出两个操作数，则表达式有误。10月算法在线班60/Code10月算法在线班61/逆波兰表达式 计算数学表达式的最常用方法；在实践中，往往给出的不是立即数，而是变量名称；若经常计算且表达式本身不变，可以事先将中缀表达式转换成逆波兰表达式存储。10月算法在线班62/计算器 将中缀表达式转换成逆波兰表达式，然后正常计算。10月算法在线班63/逆波兰表达式的用途10月算法在线班64/省级行政区中哪几个最接近圆形？10月算法在线班65/思考题：直方图矩形面积 给定n个非负整数，表示直方图的方柱的高度，同时，每个方柱的宽度假定都为1；试找出直方图中最大的矩形面积。如：给定高度为：2

21、,1,5,6,2,3，最大面积为10。10月算法在线班66/思考题：收集雨水问题 给定n个非负整数，表示直方图的方柱的高度，同时，每个方柱的宽度假定都为1。若使用这样形状的容器收集雨水，可以盛多少水量？如输入：0,1,0,2,1,0,1,3,2,1,2,1；返回6。10月算法在线班67/小结 一般而言，栈的重要度大于队列。栈的用途非常广泛，除了表达式求值，在深度优先遍历、保存现场等问题中常常出现。关于栈的话题不限于此。树、图的章节将继续讨论栈的内容。思考：一个栈(无穷大)的进栈序列为1,2,3,.n,共多少种不同的出栈序列？该问题将在动态规划中继续讨论。10月算法在线班68/我们在这里http:/ 七月题库APP：Android/iOShttp:/ 微信公众号julyedu10月算法在线班69/感谢大家恳请大家批评指正！