图解算法小抄.pdf
《图解算法小抄.pdf》由会员分享,可在线阅读,更多相关《图解算法小抄.pdf(363页珍藏版)》请在咨信网上搜索。
1、www.coding-www.coding-序言写给前端同学的算法笔记数据结构和算法的重要性:算法被称为程序的灵魂,因为优秀的算法能在处理海量数据时保持高速计算能力。计算框架和缓存技术的核心功能就源于算法。在实际工作中,一个高效的算法可以使支持数千万在线用户的服务器程序稳定运行。数据结构和算法也是许多一线IT公司面试的重要部分。如果程序员不想永远只是编写代码,那么就需要花时间研究数据结构和算法。经典的算法面试题:有一些经典的算法问题常常出现在面试中,如字符串匹配问题、动态规划问题。这些问题涉及到的算法包括暴力匹配、KMP 算法、分治算法、回溯算法、深度优先搜索(DFS)和贪心算法。解决这些问题
2、不仅需要理解和掌握相关的算法,还需要能够灵活运用这些算法来优化程序。本笔记深入讲解数据结构和算法,内容系统完整,非常适合想要深入理解数据结构和算法的学习者。我们采用了应用场景-数据结构或算法-剖析原理-分析实现步骤-代码实现的教学步骤,力求通俗易懂。数据结构和算法的内容介绍:本课程覆盖了各种数据结构和算法,包括但不限于字符串匹配算法、分治算法、回溯算法、深度优先搜索(DFS)和贪心算法。我们会通过具体的应用场,来讲解这些数据结构和算法的原理和实现步骤。笔记代码依赖ComparatorComparatorexport default class Comparator/*www.coding-*构
3、造函数.*param function(a:*,b:*)compareFunction-可以是自定义的比较函数,该函数可以比较自定义的对象.*/constructor(compareFunction)pare=compareFunction|Comparator.defaultCompareFunction;/*默认比较函数。假设 a 和 b 是字符串或数字。*param(string|number)a*param(string|number)b*returns number*/static defaultCompareFunction(a,b)if(a=b)return 0;return a
4、 b?-1:1;/*检查两个变量是否相等。*param*a*param*b*return boolean*/equal(a,b)return pare(a,b)=0;/*检查变量 a 是否小于 b。*param*a*param*bwww.coding-*return boolean*/lessThan(a,b)return pare(a,b)0;/*检查变量 a 是否小于或等于 b。*param*a*param*b*return boolean*/lessThanOrEqual(a,b)return this.lessThan(a,b)|this.equal(a,b);/*检查变量 a 是否大
5、于或等于 b。*param*a*param*b*return boolean*/greaterThanOrEqual(a,b)return this.greaterThan(a,b)|this.equal(a,b);/*www.coding-*反转比较顺序。*/reverse()const compareOriginal=pare;pare=(a,b)=compareOriginal(b,a);关于我笔名 linwu,一枚前端开发工程师,曾入职腾讯等多家知名互联网公司,后面我会持续分享精品课程,欢迎持续关注。www.coding-目录页数据结构.9一、链表.9二、双向链表.15三、队列.27四
6、、栈.30五、优先队列.33六、哈希表.36七、图.40八、堆.63九、LRU.70十、不相交集.76十一、布隆过滤器.83十二、树.90十三、字典树.135算法.142十四、排序.142十五、搜索.189十六、链表.196十七、栈.199十八、队列.226十九、双指针.234www.coding-二十、滑动窗口.247二十一、动态规划.259二十二、贪心算法.296二十三、树.318二十四、字符串.323二十五、图.334二十六、数据统计.360一、链表www.coding-9 数据结构一、链表访问 www.coding- 阅读原文动画效果,体验更佳。在计算机科学中,链表是一种数据结构,用于
7、存储和组织元素的集合。与数组不同,链表中的元素不是按照它们在内存中的物理位置顺序存储的。相反,每个元素都包含一个指向下一个元素的引用。链表由一系列节点组成,这些节点一起表示一个序列。链表最简单的形式是每个节点包含数据和指向下一个节点的引用。这种结构允许在迭代过程中高效地在任何位置插入或删除元素。更复杂的链表变体添加了额外的链接,允许高效地插入或删除任意元素的引用。链表的一个缺点是访问元素的时间复杂度是线性的(难以进行快速随机访问),而数组具有更好的缓存局部性。链表的实现通常涉及两个主要的类:LinkedListNode(链表节点)和 LinkedList(链表)。Linked List一、链表
8、www.coding-101.链表节点(LinkedListNode)链表节点表示链表中的一个元素,它包含一个值和一个指向下一个节点的引用。它的实现可以参考下面的代码:class Node constructor(value)this.value=value;this.next=null;2.链表(LinkedList)链表是由一系列链表节点组成的数据结构。它具有一个头节点(head)和一个尾节点(tail),分别表示链表的开头和结尾。链表类提供了一系列方法来操作链表,如在开头插入节点(prepend)、在末尾插入节点(append)、在指定位置插入节点(insert)、删除节点(delete
9、)、查找节点(find)等。以下是链表类的实现代码:class LinkedList constructor()this.head=null;this.tail=null;this.length=0;/在链表尾部添加新节点append(value)const newNode=new Node(value);if(!this.head)this.head=newNode;this.tail=newNode;一、链表www.coding-11 else this.tail.next=newNode;this.tail=newNode;this.length+;/在链表指定位置插入新节点insert
10、At(value,index)if(index this.length)throw new Error(Index out of range);const newNode=new Node(value);if(index=0)newNode.next=this.head;this.head=newNode;if(!this.tail)this.tail=newNode;else if(index=this.length)this.tail.next=newNode;this.tail=newNode;else let currentNode=this.head;let prevNode=nul
11、l;let currentIndex=0;while(currentIndex www.coding-12newNode.next=currentNode;this.length+;/获取指定位置节点的值getAt(index)if(index=this.length)throw new Error(Index out of range);let currentNode=this.head;let currentIndex=0;while(currentIndex index)currentNode=currentNode.next;currentIndex+;return currentNo
12、de.value;/删除指定位置的节点removeAt(index)if(index=this.length)throw new Error(Index out of range);let currentNode=this.head;let prevNode=null;let currentIndex=0;if(index=0)this.head=currentNode.next;if(this.length=1)this.tail=null;一、链表www.coding-13 else if(index=this.length-1)while(currentIndex index)prevN
13、ode=currentNode;currentNode=currentNode.next;currentIndex+;prevNode.next=null;this.tail=prevNode;else while(currentIndex www.coding-14linkedList.append(20);linkedList.insertAt(15,1);linkedList.removeAt(0);console.log(linkedList.toArray();/输出:15,203.复杂度链表的时间复杂度如下:访问:O(n)搜索:O(n)插入:O(1)删除:O(1)链表的空间复杂度为
14、 O(n),其中 n 是链表中的节点数。4.参考资料WikipediaYouTube二、双向链表www.coding-15二、双向链表访问 www.coding- 阅读原文动画效果,体验更佳。在计算机科学中,一个 双向链表(doubly linked list)是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段,称为链接,它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点,通常是前哨节点或 null,以方便遍历列表。如果只有一个前哨节点,则列表通过前哨节点循环链接。它可以被概念化为两个由相同数据项组成的单链表,但顺
15、序相反。Doubly Linked List两个节点链接允许在任一方向上遍历列表。在双向链表中进行添加或者删除节点时,需做的链接更改要比单向链表复杂得多。这种操作在单向链表中更简单高效,因为不需要关注一个节点(除第一个和最后一个节点以外的节点)的两个链接,而只需要关注一个链接即可。二、双向链表www.coding-161.实现双向链表1)Comparatorexport default class Comparator/*构造函数.*param function(a:*,b:*)compareFunction-可以是自定义的比较函数,该函数可以比较自定义的对象.*/constructor(co
16、mpareFunction)pare=compareFunction|Comparator.defaultCompareFunction;/*默认比较函数。假设 a 和 b 是字符串或数字。*param(string|number)a*param(string|number)b*returns number*/static defaultCompareFunction(a,b)if(a=b)return 0;return a www.coding-17return pare(a,b)=0;/*检查变量 a 是否小于 b。*param*a*param*b*return boolean*/less
17、Than(a,b)return pare(a,b)0;/*检查变量 a 是否小于或等于 b。*param*a*param*b*return boolean*/lessThanOrEqual(a,b)return this.lessThan(a,b)|this.equal(a,b);/*检查变量 a 是否大于或等于 b。*param*a*param*b二、双向链表www.coding-18*return boolean*/greaterThanOrEqual(a,b)return this.greaterThan(a,b)|this.equal(a,b);/*反转比较顺序。*/reverse()
18、const compareOriginal=pare;pare=(a,b)=compareOriginal(b,a);2)DoublyLinkedListNodeexport default class DoublyLinkedListNode constructor(value,next=null,previous=null)this.value=value;this.next=next;this.previous=previous;toString(callback)return callback?callback(this.value):$this.value;3)DoublyLinke
19、dListexport default class DoublyLinkedList/*param Function comparatorFunction*/constructor(comparatorFunction)/*var DoublyLinkedListNode*/二、双向链表www.coding-19/双向链表的头节点this.head=null;/*var DoublyLinkedListNode*/双向链表的尾节点this.tail=null;/用于比较的函数pare=new Comparator(comparatorFunction);/*param*value*return
20、 DoublyLinkedList*/将新的节点插入到头部prepend(value)/创建新的节点作为头部节点const newNode=new DoublyLinkedListNode(value,this.head);/如果存在头部节点,那么它不再是头部节点了。/因此,将其前驱节点设置为新节点(新的头部节点)。/然后标记新的节点为头部节点。if(this.head)this.head.previous=newNode;this.head=newNode;/如果还没有尾部节点,那么就让新的节点成为尾部节点。if(!this.tail)this.tail=newNode;return thi
21、s;/*二、双向链表www.coding-20*param*value*return DoublyLinkedList*/将新的节点追加到尾部append(value)const newNode=new DoublyLinkedListNode(value);/如果还没有头部节点,让新的节点成为头部节点。if(!this.head)this.head=newNode;this.tail=newNode;return this;/将新的节点添加到链表的末尾。this.tail.next=newNode;/将当前尾部节点添加到新节点的前驱引用。newNode.previous=this.tail;
22、/设置新节点为链表的尾部节点。this.tail=newNode;return this;/*param*value*return DoublyLinkedListNode*/删除具有特定值的节点delete(value)if(!this.head)return null;二、双向链表www.coding-21let deletedNode=null;let currentNode=this.head;while(currentNode)if(pare.equal(currentNode.value,value)deletedNode=currentNode;if(deletedNode=th
23、is.head)/如果要删除的是头部节点./将头部节点设置为第二个节点,它将成为新的头部节点。this.head=deletedNode.next;/将新头部节点的前驱设置为 null。if(this.head)this.head.previous=null;/如果链表中的所有节点的值都和传入的参数相同/那么所有节点都会被删除,因此需要更新尾部节点。if(deletedNode=this.tail)this.tail=null;else if(deletedNode=this.tail)/如果要删除的是尾部节点./将尾部节点设置为倒数第二个节点,它将成为新的尾部节点。this.tail=del
24、etedNode.previous;this.tail.next=null;else/如果要删除的是中间节点.const previousNode=deletedNode.previous;const nextNode=deletedNode.next;previousNode.next=nextNode;nextNode.previous=previousNode;二、双向链表www.coding-22currentNode=currentNode.next;return deletedNode;/*param Object findParams*param*findParams.value
25、*param function findParams.callback*return DoublyLinkedListNode*/查找具有特定值或满足回调函数的节点find(value=undefined,callback=undefined)if(!this.head)return null;let currentNode=this.head;while(currentNode)/如果指定了回调函数,那么尝试通过回调函数找到节点。if(callback&callback(currentNode.value)return currentNode;/如果指定了值,那么尝试通过值找到节点。if(v
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图解 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【Stan****Shan】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【Stan****Shan】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。