图解算法小抄.pdf

www.coding-www.coding-序言写给前端同学的算法笔记数据结构和算法的重要性：算法被称为程序的灵魂，因为优秀的算法能在处理海量数据时保持高速计算能力。计算框架和缓存技术的核心功能就源于算法。在实际工作中，一个高效的算法可以使支持数千万在线用户的服务器程序稳定运行。数据结构和算法也是许多一线IT公司面试的重要部分。如果程序员不想永远只是编写代码，那么就需要花时间研究数据结构和算法。经典的算法面试题：有一些经典的算法问题常常出现在面试中，如字符串匹配问题、动态规划问题。这些问题涉及到的算法包括暴力匹配、KMP 算法、分治算法、回溯算法、深度优先搜索(DFS)和贪心算法。解决这些问题不仅需要理解和掌握相关的算法，还需要能够灵活运用这些算法来优化程序。本笔记深入讲解数据结构和算法，内容系统完整，非常适合想要深入理解数据结构和算法的学习者。我们采用了应用场景-数据结构或算法-剖析原理-分析实现步骤-代码实现的教学步骤，力求通俗易懂。数据结构和算法的内容介绍：本课程覆盖了各种数据结构和算法，包括但不限于字符串匹配算法、分治算法、回溯算法、深度优先搜索(DFS)和贪心算法。我们会通过具体的应用场，来讲解这些数据结构和算法的原理和实现步骤。笔记代码依赖ComparatorComparatorexport default class Comparator/*www.coding-*构造函数.*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 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 是否大于或等于 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四、栈.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- 阅读原文动画效果，体验更佳。在计算机科学中，链表是一种数据结构，用于存储和组织元素的集合。与数组不同，链表中的元素不是按照它们在内存中的物理位置顺序存储的。相反，每个元素都包含一个指向下一个元素的引用。链表由一系列节点组成，这些节点一起表示一个序列。链表最简单的形式是每个节点包含数据和指向下一个节点的引用。这种结构允许在迭代过程中高效地在任何位置插入或删除元素。更复杂的链表变体添加了额外的链接，允许高效地插入或删除任意元素的引用。链表的一个缺点是访问元素的时间复杂度是线性的（难以进行快速随机访问），而数组具有更好的缓存局部性。链表的实现通常涉及两个主要的类：LinkedListNode（链表节点）和 LinkedList（链表）。Linked List一、链表www.coding-101.链表节点（LinkedListNode）链表节点表示链表中的一个元素，它包含一个值和一个指向下一个节点的引用。它的实现可以参考下面的代码：class Node constructor(value)this.value=value;this.next=null;2.链表（LinkedList）链表是由一系列链表节点组成的数据结构。它具有一个头节点（head）和一个尾节点（tail），分别表示链表的开头和结尾。链表类提供了一系列方法来操作链表，如在开头插入节点（prepend）、在末尾插入节点（append）、在指定位置插入节点（insert）、删除节点（delete）、查找节点（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+;/在链表指定位置插入新节点insertAt(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=null;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 currentNode.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)prevNode=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)链表的空间复杂度为 O(n)，其中 n 是链表中的节点数。4.参考资料WikipediaYouTube二、双向链表www.coding-15二、双向链表访问 www.coding- 阅读原文动画效果，体验更佳。在计算机科学中,一个 双向链表(doubly linked list)是由一组称为节点的顺序链接记录组成的链接数据结构。每个节点包含两个字段，称为链接，它们是对节点序列中上一个节点和下一个节点的引用。开始节点和结束节点的上一个链接和下一个链接分别指向某种终止节点，通常是前哨节点或 null，以方便遍历列表。如果只有一个前哨节点，则列表通过前哨节点循环链接。它可以被概念化为两个由相同数据项组成的单链表，但顺序相反。Doubly Linked List两个节点链接允许在任一方向上遍历列表。在双向链表中进行添加或者删除节点时,需做的链接更改要比单向链表复杂得多。这种操作在单向链表中更简单高效,因为不需要关注一个节点（除第一个和最后一个节点以外的节点）的两个链接,而只需要关注一个链接即可。二、双向链表www.coding-161.实现双向链表1）Comparatorexport default class Comparator/*构造函数.*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 www.coding-17return pare(a,b)=0;/*检查变量 a 是否小于 b。*param*a*param*b*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 是否大于或等于 b。*param*a*param*b二、双向链表www.coding-18*return boolean*/greaterThanOrEqual(a,b)return this.greaterThan(a,b)|this.equal(a,b);/*反转比较顺序。*/reverse()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）DoublyLinkedListexport 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 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 this;/*二、双向链表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;/设置新节点为链表的尾部节点。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=this.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=deletedNode.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*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(value!=undefined&pare.equal(currentNode.value,value)return currentNode;currentNode=currentNode.next;二、双向链表www.coding-23return null;/*return DoublyLinkedListNode*/删除尾部节点deleteTail()if(!this.tail)/没有尾部节点可以删除return null;if(this.head=this.tail)/链表中只有一个节点const deletedTail=this.tail;this.head=null;this.tail=null;return deletedTail;/如果链表中有很多节点.const deletedTail=this.tail;this.tail=this.tail.previous;this.tail.next=null;return deletedTail;/*return DoublyLinkedListNode*/删除头部节点deleteHead()if(!this.head)二、双向链表www.coding-24return null;const deletedHead=this.head;if(this.head.next)this.head=this.head.next;this.head.previous=null;else this.head=null;this.tail=null;return deletedHead;/*return DoublyLinkedListNode*/将链表转换为数组toArray()const nodes=;let currentNode=this.head;while(currentNode)nodes.push(currentNode);currentNode=currentNode.next;return nodes;/*param*values-需要转换为链表的值的数组。*return DoublyLinkedList*/从数组创建链表二、双向链表www.coding-25fromArray(values)values.forEach(value)=this.append(value);return this;/*param function callback*return string*/将链表转换为字符串toString(callback)returnthis.toArray().map(node)=node.toString(callback).toString();/*反转链表。*returns DoublyLinkedList*/reverse()let currNode=this.head;let prevNode=null;let nextNode=null;while(currNode)/存储下一个节点。nextNode=currNode.next;prevNode=currNode.previous;/改变当前节点的下一个节点，使其链接到前一个节点。currNode.next=prevNode;currNode.previous=nextNode;/将 prevNode 和 currNode 节点向前移动一步。prevNode=currNode;currNode=nextNode;二、双向链表www.coding-26/重置头部和尾部节点。this.tail=this.head;this.head=prevNode;return this;2.复杂度时间复杂度AccessSearchInsertionDeletionO(n)O(n)O(1)O(1)空间复杂度O(n)3.参考WikipediaYouTube三、队列www.coding-27三、队列访问 www.coding- 阅读原文动画效果，体验更佳。在计算机科学中,一个 队列(queue)是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。队列基本操作有两种：入队和出队。从队列的后端位置添加实体，称为入队；从队列的前端位置移除实体，称为出队。队列中元素先进先出 FIFO(first in,first out)的示意Queue1.实现队列class Queue constructor()this.items=;/入队操作enqueue(element)this.items.push(element);三、队列www.coding-28/出队操作dequeue()if(this.isEmpty()throw new Error(Queue is empty);return this.items.shift();/返回队头元素front()if(this.isEmpty()throw new Error(Queue is empty);return this.items0;/判断队列是否为空isEmpty()return this.items.length=0;/返回队列的大小size()return this.items.length;/清空队列clear()this.items=;const queue=new Queue();queue.enqueue(10);queue.enqueue(20);queue.enqueue(30);console.log(queue.front();/输出:10console.log(queue.size();/输出:3三、队列www.coding-29console.log(queue.isEmpty();/输出:falsequeue.dequeue();console.log(queue.size();/输出:2queue.clear();console.log(queue.isEmpty();/输出:true2.参考WikipediaYouTube四、栈www.coding-30四、栈访问 www.coding- 阅读原文动画效果，体验更佳。在计算机科学中,一个 栈(stack)是一种抽象数据类型,用作表示元素的集合,具有两种主要操作:push,添加元素到栈的顶端(末尾);pop,移除栈最顶端(末尾)的元素.以上两种操作可以简单概括为“后进先出(LIFO=last in,first out)”。此外,应有一个 peek 操作用于访问栈当前顶端(末尾)的元素。栈这个名称,可类比于一组物体的堆叠(一摞书,一摞盘子之类的)。栈的 push 和 pop 操作的示意Stack四、栈www.coding-311.实现栈class Stack constructor()this.items=;/入栈操作push(element)this.items.push(element);/出栈操作pop()if(this.isEmpty()throw new Error(Stack is empty);return this.items.pop();/返回栈顶元素peek()if(this.isEmpty()throw new Error(Stack is empty);return this.itemsthis.items.length-1;/判断栈是否为空isEmpty()return this.items.length=0;/返回栈的大小size()return this.items.length;四、栈www.coding-32/清空栈clear()this.items=;const stack=new Stack();stack.push(10);stack.push(20);stack.push(30);console.log(stack.peek();/输出:30console.log(stack.size();/输出:3console.log(stack.isEmpty();/输出:falsestack.pop();console.log(stack.size();/输出:2stack.clear();console.log(stack.isEmpty();/输出:true2.参考WikipediaYouTube五、优先队列www.coding-33五、优先队列访问 www.coding- 阅读原文动画效果，体验更佳。在计算机科学中,优先级队列(priority queue)是一种抽象数据类型,它类似于常规的队列或栈,但每个元素都有与之关联的“优先级”。在优先队列中,低优先级的元素之前前面应该是高优先级的元素。如果两个元素具有相同的优先级,则根据它们在队列中的顺序是它们的出现顺序即可。优先队列虽通常用堆来实现,但它在概念上与堆不同。优先队列是一个抽象概念，就像“列表”或“图”这样的抽象概念一样;正如列表可以用链表或数组实现一样，优先队列可以用堆或各种其他方法实现,例如无序数组。class PriorityQueue constructor()this.queue=;/添加元素到优先队列中enqueue(element,priority)const item=element,priority;let inserted=false;for(let i=0;i this.queue.length;i+)if(item.priority www.coding-34if(!inserted)this.queue.push(item);/从优先队列中移除并返回具有最高优先级的元素dequeue()if(this.isEmpty()return null;return this.queue.shift().element;/返回具有最高优先级的元素，但不进行移除front()if(this.isEmpty()return null;return this.queue0.element;/检查优先队列是否为空isEmpty()return this.queue.length=0;/返回优先队列的大小size()return this.queue.length;const priorityQueue=new PriorityQueue();priorityQueue.enqueue(apple,2);priorityQueue.enqueue(banana,3);priorityQueue.enqueue(orange,1);console.log(priorityQueue.front();/输出:orangeconsole.log(priorityQueue.dequeue();/输出:orange五、优先队列www.coding-35console.log(priorityQueue.size();/输出:2console.log(priorityQueue.isEmpty();/输出:false3.参考WikipediaYouTube六、哈希表www.coding-36六、哈希表访问 www.coding- 阅读原文动画效果，体验更佳。在计算中,一个 哈希表(hash table 或 hash map)是一种实现 关联数组(associativearray)的抽象数据类型,该结构可以将 键映射到值。哈希表使用 哈希函数/散列函数 来计算一个值在数组或桶(buckets)中或槽(slots)中对应的索引,可使用该索引找到所需的值。理想情况下,散列函数将为每个键分配给一个唯一的桶(bucket),但是大多数哈希表设计采用不完美的散列函数,这可能会导致哈希冲突(hash collisions),也就是散列函数为多个键(key)生成了相同的索引,这种碰撞必须 以某种方式进行处理。Hash Table六、哈希表www.coding-37通过单独的链接解决哈希冲突Hash Collisionclass HashTable constructor()this.table=;/哈希函数hash(key)let hash=0;for(let i=0;i www.coding-38/从哈希表中获取指定键的值get(key)const index=this.hash(key);if(this.tableindex&this.tableindexkey)return this.tableindexkey;return undefined;/从哈希表中移除指定键值对remove(key)const index=this.hash(key);if(this.tableindex&this.tableindexkey)delete this.tableindexkey;if(Object.keys(this.tableindex).length=0)delete this.tableindex;return true;return false;/检查哈希表中是否存在指定键contains(key)const index=this.hash(key);return!(this.tableindex&this.tableindexkey);/返回哈希表中的所有键keys()const keys=;for(const index in this.table)for(const key in this.tableindex)keys.push(key);六、哈希表www.coding-39return keys;/返回哈希表中的所有值values()const values=;for(const index in this.table)for(const key in this.tableindex)values.push(this.tableindexkey);return values;const hashTable=new HashTable();hashTable.put(apple,10);hashTable.put(banana,20);console.log(hashTable.get(apple);/输出:10console.log(hashTable.contains(banana);/输出:trueconsole.log(hashTable.remove(banana);/输出:trueconsole.log(hashTable.contains(banana);/输出:falseconsole.log(hashTable.keys();/输出:appleconsole.log(hashTable.values();/输出:10参考WikipediaYouTube七、图www.coding-40七、图访问 www.coding- 阅读原文动画效果，体验更佳。在计算机科学中,图(graph)是一种抽象数据类型,旨在实现数学中的无向图和有向图概念，特别是图论领域。一个图数据结构是一个(由有限个或者可变数量的)顶点/节点/点和边构成的有限集。如果顶点对之间是无序的,称为无序图,否则称为有序图;如果顶点对之间的边是没有方向的,称为无向图,否则称为有向图;如果顶点对之间的边是有权重的,该图可称为加权图。Graph1.完整代码Graphexport default class Graph/*param boolean isDirected*/构造函数，参数表示图是否是有向的constructor(isDirected=false)this.vertices=;/顶点集七、图www.coding-41this.edges=;/边集this.isDirected=isDirected;/是否为有向图/*param GraphVertex newVertex*returns Graph*/添加顶点addVertex(newVertex)this.verticesnewVertex.getKey()=newVertex;return this;/*param string vertexKey*returns GraphVertex*/根据键值获取顶点getVertexByKey(vertexKey)return this.verticesvertexKey;/*param GraphVertex vertex*returns GraphVertex*/获取顶点的邻居getNeighbors(vertex)return vertex.getNeighbors();/*return GraphVertex*/获取所有的顶点七、图www.coding-42getAllVertices()return Object.values(this.vertices);/*return GraphEdge*/获取所有的边getAllEdges()return Object.values(this.edges);/*param GraphEdge edge*returns Graph*/添加边addEdge(edge)/尝试查找起始和结束顶点let startVertex=this.getVertexByKey(edge.startVertex.getKey();let endVertex=this.getVertexByKey(edge.endVertex.getKey();/如果起始顶点未插入，插入起始顶点if(!startVertex)this.addVertex(edge.startVertex);startVertex=this.getVertexByKey(edge.startVertex.getKey();/如果结束顶点未插入，插入结束顶点if(!endVertex)this.addVertex(edge.endVertex);endVertex=this.getVertexByKey(edge.endVertex.getKey();/检查边是否已经添加过if(this.edgesedge.getKey