• 前端面试练习24.3.11

    常见开发模式

    1. 瀑布模型（Waterfall Model）：瀑布模型是一种线性的软件开发过程，包括需求分析、系统设计、实现、测试、部署和维护等阶段，每个阶段依次执行，前一个阶段完成后才能进行下一个阶段。瀑布模型适用于需求变更较少且项目范围明确的情况。

    2. 迭代开发模型（Iterative Development Model）：迭代开发模型将软件开发过程分解为多个迭代周期，每个迭代周期都包括需求分析、设计、编码、测试和部署等阶段，每个迭代周期都会交付一部分功能。迭代开发模型适用于需求不断变化或者需要快速响应市场变化的情况。

    3. 增量开发模型（Incremental Development Model）：增量开发模型是在已有的软件基础上逐步添加新的功能和特性，每次增加一个小的模块或者部分功能，逐步完善软件系统。增量开发模型适用于大型软件系统的开发，可以减少风险并提高可控性。

    4. 螺旋模型（Spiral Model）：螺旋模型将软件开发过程分解为多个迭代的螺旋，每个螺旋代表一个迭代周期，包括计划、风险分析、开发和评审等阶段。螺旋模型适用于需要重点关注风险管理的项目，可以在迭代过程中及时发现和解决问题。

    5. 敏捷开发（Agile Development）：敏捷开发是一种基于价值交付和持续反馈的软件开发方法，强调团队协作、自组织、快速迭代和灵活响应需求变化。常见的敏捷方法包括Scrum、Kanban、XP等。

    6. DevOps：DevOps 是一种软件开发和运维的文化、实践和自动化工具的结合，旨在缩短软件开发周期、提高软件交付速度和质量、增强团队协作和沟通效率。

     数据结构与算法知识

    1.常见数据结构

    数组（Array）

    数组是一种线性数据结构，它由一组连续的内存空间组成，用来存储相同类型的数据。数组可以通过索引来访问元素，索引从0开始计数。

    基本操作：
    • 访问元素：通过索引访问数组中的元素。
    • 插入元素：向数组中插入一个元素，通常需要移动后面的元素以腾出空间。
    • 删除元素：从数组中删除一个元素，通常需要移动后面的元素以填补空缺。
    • 更新元素：修改数组中指定索引的元素的值。
    1. // 创建一个数组
    2. let arr = [1, 2, 3, 4, 5];
    3.  
    4. // 访问元素
    5. console.log(arr[0]); // 输出：1
    6.  
    7. // 插入元素
    8. arr.push(6); // 在数组末尾插入元素 6
    9. console.log(arr); // 输出：[1, 2, 3, 4, 5, 6]
    10.  
    11. // 删除元素
    12. arr.pop(); // 删除数组末尾的元素
    13. console.log(arr); // 输出：[1, 2, 3, 4, 5]
    14.  
    15. // 更新元素
    16. arr[0] = 10;
    17. console.log(arr); // 输出：[10, 2, 3, 4, 5]

    链表（Linked List）

    链表是一种线性数据结构，它由一组节点（Node）组成，每个节点包含两部分：数据域（存储数据）和指针域（指向下一个节点）。链表中的节点通过指针相连，形成一条链式结构。

    链表相对于数组来说，插入和删除节点的操作效率更高，但是查找节点的效率较低。链表适合频繁插入和删除操作的场景。

    基本操作：
    • 插入节点：在链表的任意位置插入一个新节点。
    • 删除节点：从链表中删除指定位置的节点。
    • 查找节点：在链表中查找指定值的节点。
    • 遍历链表：遍历整个链表，访问每个节点。
    1. // 定义链表节点类
    2. class ListNode {
    3.     constructor(val) {
    4.         this.val = val; // 节点的值
    5.         this.next = null; // 指向下一个节点的指针
    6.     }
    7. }
    8.  
    9. // 定义链表类
    10. class LinkedList {
    11.     constructor() {
    12.         this.head = null; // 链表头节点
    13.     }
    14.  
    15.     // 插入节点
    16.     insert(val) {
    17.         const newNode = new ListNode(val);
    18.         if (!this.head) {
    19.             this.head = newNode;
    20.         } else {
    21.             let current = this.head;
    22.             while (current.next) {
    23.                 current = current.next;
    24.             }
    25.             current.next = newNode;
    26.         }
    27.     }
    28.  
    29.     // 删除节点
    30.     delete(val) {
    31.         if (!this.head) return;
    32.         if (this.head.val === val) {
    33.             this.head = this.head.next;
    34.             return;
    35.         }
    36.         let prev = this.head;
    37.         let current = this.head.next;
    38.         while (current) {
    39.             if (current.val === val) {
    40.                 prev.next = current.next;
    41.                 return;
    42.             }
    43.             prev = current;
    44.             current = current.next;
    45.         }
    46.     }
    47.  
    48.     // 查找节点
    49.     find(val) {
    50.         let current = this.head;
    51.         while (current) {
    52.             if (current.val === val) {
    53.                 return current;
    54.             }
    55.             current = current.next;
    56.         }
    57.         return null;
    58.     }
    59.  
    60.     // 遍历链表
    61.     display() {
    62.         let current = this.head;
    63.         while (current) {
    64.             console.log(current.val);
    65.             current = current.next;
    66.         }
    67.     }
    68. }
    69.  
    70. // 创建一个链表
    71. const linkedList = new LinkedList();
    72. linkedList.insert(1);
    73. linkedList.insert(2);
    74. linkedList.insert(3);
    75.  
    76. // 遍历链表并输出节点值
    77. linkedList.display(); // 输出：1 2 3
    78.  
    79. // 删除节点值为 2 的节点
    80. linkedList.delete(2);
    81.  
    82. // 再次遍历链表并输出节点值
    83. linkedList.display(); // 输出：1 3

    栈（Stack）

    栈是一种具有特定操作规则的线性数据结构，它的特点是后进先出（LIFO，Last In First Out）。栈可以用数组或链表实现。

    栈常用于需要临时存储和回溯的场景，例如浏览器的前进和后退功能、表达式求值、函数调用等。

    基本操作：
    • 入栈：将元素压入栈顶。
    • 出栈：从栈顶弹出元素。
    • 查看栈顶元素：获取栈顶元素但不移除。
    • 判断栈是否为空：判断栈中是否有元素。
    • 获取栈的大小：获取栈中元素的数量。
    数组实现栈
    1. class Stack {
    2.     constructor() {
    3.         this.items = [];
    4.     }
    5.     // 入栈
    6.     push(element) {
    7.         this.items.push(element);
    8.     }
    9.     // 出栈
    10.     pop() {
    11.         if (this.isEmpty()) return null;
    12.         return this.items.pop();
    13.     }
    14.     // 查看栈顶元素
    15.     peek() {
    16.         if (this.isEmpty()) return null;
    17.         return this.items[this.items.length - 1];
    18.     }
    19.     // 判断栈是否为空
    20.     isEmpty() {
    21.         return this.items.length === 0;
    22.     }
    23.     // 获取栈的大小
    24.     size() {
    25.         return this.items.length;
    26.     }
    27. }
    28.  
    29. // 创建一个栈实例
    30. const stack = new Stack();
    31.  
    32. // 入栈
    33. stack.push(1);
    34. stack.push(2);
    35. stack.push(3);
    36.  
    37. // 出栈
    38. console.log(stack.pop()); // 输出：3
    39. // 查看栈顶元素
    40. console.log(stack.peek()); // 输出：2
    41. // 获取栈的大小
    42. console.log(stack.size()); // 输出：2
    43. // 判断栈是否为空
    44. console.log(stack.isEmpty()); // 输出：false
    链表实现栈
    1. class ListNode {
    2.     constructor(val) {
    3.         this.val = val;
    4.         this.next = null;
    5.     }
    6. }
    7.  
    8. class Stack {
    9.     constructor() {
    10.         this.top = null; // 栈顶节点
    11.         this.size = 0; // 栈的大小
    12.     }
    13.     // 入栈
    14.     push(val) {
    15.         const newNode = new ListNode(val);
    16.         if (!this.top) {
    17.             this.top = newNode;
    18.         } else {
    19.             newNode.next = this.top;
    20.             this.top = newNode;
    21.         }
    22.         this.size++;
    23.     }
    24.     // 出栈
    25.     pop() {
    26.         if (this.isEmpty()) return null;
    27.         const popped = this.top;
    28.         this.top = this.top.next;
    29.         popped.next = null;
    30.         this.size--;
    31.         return popped.val;
    32.     }
    33.     // 查看栈顶元素
    34.     peek() {
    35.         if (this.isEmpty()) return null;
    36.         return this.top.val;
    37.     }
    38.     // 判断栈是否为空
    39.     isEmpty() {
    40.         return this.size === 0;
    41.     }
    42.     // 获取栈的大小
    43.     getSize() {
    44.         return this.size;
    45.     }
    46. }
    47.  
    48. // 创建一个栈实例
    49. const stack = new Stack();
    50.  
    51. // 入栈
    52. stack.push(1);
    53. stack.push(2);
    54. stack.push(3);
    55.  
    56. // 出栈
    57. console.log(stack.pop()); // 输出：3
    58. // 查看栈顶元素
    59. console.log(stack.peek()); // 输出：2
    60. // 获取栈的大小
    61. console.log(stack.getSize()); // 输出：2
    62. // 判断栈是否为空
    63. console.log(stack.isEmpty()); // 输出：false

    队列（Queue）

    队列是一种具有特定操作规则的线性数据结构，它的特点是先进先出（FIFO，First In First Out）。队列可以用数组或链表实现。

    队列常用于需要按顺序处理任务的场景，例如消息队列、广度优先搜索等。

    基本操作：
    • 入队：将元素加入队列尾部。
    • 出队：从队列头部移除元素。
    • 查看队首元素：获取队列头部的元素但不移除。
    • 判断队列是否为空：判断队列中是否有元素。
    • 获取队列的大小：获取队列中元素的数量。
    1. class ListNode {
    2.     constructor(val) {
    3.         this.val = val;
    4.         this.next = null;
    5.     }
    6. }
    7.  
    8. class Queue {
    9.     constructor() {
    10.         this.front = null; // 队头节点
    11.         this.rear = null; // 队尾节点
    12.         this.size = 0; // 队列的大小
    13.     }
    14.     // 入队
    15.     enqueue(val) {
    16.         const newNode = new ListNode(val);
    17.         if (!this.rear) {
    18.             this.front = newNode;
    19.             this.rear = newNode;
    20.         } else {
    21.             this.rear.next = newNode;
    22.             this.rear = newNode;
    23.         }
    24.         this.size++;
    25.     }
    26.     // 出队
    27.     dequeue() {
    28.         if (this.isEmpty()) return null;
    29.         const dequeued = this.front;
    30.         this.front = this.front.next;
    31.         dequeued.next = null;
    32.         this.size--;
    33.         // 如果出队后队列为空，更新 rear 指针
    34.         if (!this.front) {
    35.             this.rear = null;
    36.         }
    37.         return dequeued.val;
    38.     }
    39.     // 查看队首元素
    40.     peek() {
    41.         if (this.isEmpty()) return null;
    42.         return this.front.val;
    43.     }
    44.     // 判断队列是否为空
    45.     isEmpty() {
    46.         return this.size === 0;
    47.     }
    48.     // 获取队列的大小
    49.     getSize() {
    50.         return this.size;
    51.     }
    52. }
    53.  
    54. // 创建一个队列实例
    55. const queue = new Queue();
    56.  
    57. // 入队
    58. queue.enqueue(1);
    59. queue.enqueue(2);
    60. queue.enqueue(3);
    61.  
    62. // 出队
    63. console.log(queue.dequeue()); // 输出：1
    64. // 查看队首元素
    65. console.log(queue.peek()); // 输出：2
    66. // 获取队列的大小
    67. console.log(queue.getSize()); // 输出：2
    68. // 判断队列是否为空
    69. console.log(queue.isEmpty()); // 输出：false

    树（Tree）：

    二叉树、二叉搜索树、AVL 树、红黑树等

    树是一种非线性数据结构，它由一组节点组成，节点之间通过边连接，形成层次关系。树中有一个特殊的节点称为根节点，除了根节点之外，每个节点都有一个父节点和零个或多个子节点。

    树是一种非常重要的数据结构，常用于模拟层次结构的问题，例如文件系统、组织架构、HTML 文档等。二叉树是树的一种特殊形式，在算法和数据结构中应用广泛。

    基本概念：
    • 根节点：树的顶端节点，没有父节点。
    • 父节点：每个节点都有一个父节点，除了根节点。
    • 子节点：每个节点可以有零个或多个子节点。
    • 叶子节点：没有子节点的节点称为叶子节点。
    • 深度：从根节点到当前节点的唯一路径的长度称为节点的深度。
    • 高度：从当前节点到最远叶子节点的路径的长度称为节点的高度。
    常见类型：
    • 二叉树（Binary Tree）：每个节点最多有两个子节点的树。
    • 二叉搜索树（Binary Search Tree，BST）：一种特殊的二叉树，左子树上的所有节点的值都小于根节点的值，右子树上的所有节点的值都大于根节点的值。
    1. class TreeNode {
    2.     constructor(val) {
    3.         this.val = val;
    4.         this.left = null;
    5.         this.right = null;
    6.     }
    7. }
    8.  
    9. // 创建一个二叉树
    10. const root = new TreeNode(1);
    11. root.left = new TreeNode(2);
    12. root.right = new TreeNode(3);
    13. root.left.left = new TreeNode(4);
    14. root.left.right = new TreeNode(5);
    15.  
    16. // 中序遍历二叉树（左-根-右）
    17. function inOrderTraversal(node) {
    18.     if (!node) return;
    19.     inOrderTraversal(node.left);
    20.     console.log(node.val);
    21.     inOrderTraversal(node.right);
    22. }
    23.  
    24. console.log("Inorder traversal:");
    25. inOrderTraversal(root);

    堆（Heap）

    堆是一种特殊的树形数据结构，通常实现为数组，并满足堆属性：对于堆中任意节点 i，其父节点的值小于或等于其子节点的值（最小堆），或者父节点的值大于或等于其子节点的值（最大堆）。

    堆是一种非常重要的数据结构，它在各种算法和应用中都有广泛的应用，比如堆排序、优先队列、调度算法等。

    基本概念：
    • 最小堆（Min Heap）：每个父节点的值都小于或等于其子节点的值。
    • 最大堆（Max Heap）：每个父节点的值都大于或等于其子节点的值。
    • 堆的形状性质：堆是一个完全二叉树，即除了最后一层之外，每一层都是满的，且最后一层的节点都尽可能地靠左排列。
    • 堆的堆序性质：堆中的每个节点都必须满足堆属性。
    常见操作：
    • 插入（Insertion）：向堆中插入一个新元素。
    • 删除最值（Extract-Min/Max）：删除并返回最小（最大）值。
    • 查找最值（Find-Min/Max）：查找并返回最小（最大）值。
    • 堆化（Heapify）：将无序数组转换为堆结构。
    • 堆排序（Heap Sort）：利用堆实现的一种排序算法。
    1. class MinHeap {
    2.     constructor() {
    3.         this.heap = [];
    4.     }
    5.  
    6.     // 获取父节点索引
    7.     getParentIndex(index) {
    8.         return Math.floor((index - 1) / 2);
    9.     }
    10.  
    11.     // 获取左子节点索引
    12.     getLeftChildIndex(index) {
    13.         return index * 2 + 1;
    14.     }
    15.  
    16.     // 获取右子节点索引
    17.     getRightChildIndex(index) {
    18.         return index * 2 + 2;
    19.     }
    20.  
    21.     // 上移操作（向上调整）
    22.     siftUp(index) {
    23.         let parentIndex = this.getParentIndex(index);
    24.         while (index > 0 && this.heap[parentIndex] > this.heap[index]) {
    25.             [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
    26.             index = parentIndex;
    27.             parentIndex = this.getParentIndex(index);
    28.         }
    29.     }
    30.  
    31.     // 下移操作（向下调整）
    32.     siftDown(index) {
    33.         let minIndex = index;
    34.         const leftChildIndex = this.getLeftChildIndex(index);
    35.         const rightChildIndex = this.getRightChildIndex(index);
    36.         if (leftChildIndex < this.heap.length && this.heap[leftChildIndex] < this.heap[minIndex]) {
    37.             minIndex = leftChildIndex;
    38.         }
    39.         if (rightChildIndex < this.heap.length && this.heap[rightChildIndex] < this.heap[minIndex]) {
    40.             minIndex = rightChildIndex;
    41.         }
    42.         if (minIndex !== index) {
    43.             [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
    44.             this.siftDown(minIndex);
    45.         }
    46.     }
    47.  
    48.     // 插入新元素
    49.     insert(value) {
    50.         this.heap.push(value);
    51.         this.siftUp(this.heap.length - 1);
    52.     }
    53.  
    54.     // 删除并返回最小值
    55.     extractMin() {
    56.         if (this.heap.length === 0) return null;
    57.         if (this.heap.length === 1) return this.heap.pop();
    58.         const min = this.heap[0];
    59.         this.heap[0] = this.heap.pop();
    60.         this.siftDown(0);
    61.         return min;
    62.     }
    63.  
    64.     // 获取最小值
    65.     peek() {
    66.         return this.heap.length > 0 ? this.heap[0] : null;
    67.     }
    68.  
    69.     // 获取堆的大小
    70.     size() {
    71.         return this.heap.length;
    72.     }
    73.  
    74.     // 判断堆是否为空
    75.     isEmpty() {
    76.         return this.heap.length === 0;
    77.     }
    78. }
    79.  
    80. // 创建一个最小堆实例
    81. const minHeap = new MinHeap();
    82.  
    83. // 插入元素
    84. minHeap.insert(3);
    85. minHeap.insert(2);
    86. minHeap.insert(1);
    87.  
    88. // 获取最小值
    89. console.log(minHeap.peek()); // 输出：1
    90.  
    91. // 删除并返回最小值
    92. console.log(minHeap.extractMin()); // 输出：1

    图（Graph）：

    有向图、无向图、加权图等

    图是一种非线性数据结构，由一组节点（顶点）和一组边组成。图中的节点可以是任意对象，边则是连接节点的线段。图可以用来表示各种实体之间的关系，比如社交网络中的用户和好友关系、地图中的城市和道路关系等。

    图是非常灵活和强大的数据结构，它在各种领域都有广泛的应用，例如网络路由、社交网络分析、推荐系统等。理解图的基本概念和常见算法对于解决与图相关的问题非常重要。

    基本概念：
    • 顶点（Vertex）：图中的节点。
    • 边（Edge）：连接两个顶点的线段，可以是有向或无向的。
    • 有向图（Directed Graph）：图中的边有方向，即从一个顶点到另一个顶点有一个确定的方向。
    • 无向图（Undirected Graph）：图中的边没有方向，即从一个顶点到另一个顶点没有确定的方向。
    • 权重（Weight）：边上的值，用来表示连接两个顶点之间的距离、代价等信息。
    • 路径（Path）：顶点序列，按照边的连接顺序排列。
    • 环（Cycle）：至少有一个边的起始顶点和终止顶点相同的路径。
    常见类型：
    • 有向图：图中的边有方向。
    • 无向图：图中的边没有方向。
    • 加权图（Weighted Graph）：图中的边带有权重。
    • 稀疏图（Sparse Graph）：图中的边相对较少。
    • 稠密图（Dense Graph）：图中的边相对较多。
    1. class Graph {
    2.     constructor() {
    3.         this.vertices = []; // 顶点集合
    4.         this.adjacencyList = new Map(); // 邻接表，用于存储顶点及其相邻顶点
    5.     }
    6.  
    7.     // 添加顶点
    8.     addVertex(vertex) {
    9.         this.vertices.push(vertex);
    10.         this.adjacencyList.set(vertex, []);
    11.     }
    12.  
    13.     // 添加边（无向图）
    14.     addEdge(v1, v2) {
    15.         this.adjacencyList.get(v1).push(v2);
    16.         this.adjacencyList.get(v2).push(v1);
    17.     }
    18.  
    19.     // 添加边（有向图）
    20.     addDirectedEdge(v1, v2) {
    21.         this.adjacencyList.get(v1).push(v2);
    22.     }
    23.  
    24.     // 获取相邻顶点列表
    25.     getAdjacentVertices(vertex) {
    26.         return this.adjacencyList.get(vertex);
    27.     }
    28.  
    29.     // 打印图的邻接表
    30.     printGraph() {
    31.         for (let [vertex, neighbors] of this.adjacencyList) {
    32.             console.log(`${vertex} -> ${neighbors.join(", ")}`);
    33.         }
    34.     }
    35. }
    36.  
    37. // 创建一个无向图实例
    38. const graph = new Graph();
    39. graph.addVertex("A");
    40. graph.addVertex("B");
    41. graph.addVertex("C");
    42. graph.addEdge("A", "B");
    43. graph.addEdge("B", "C");
    44.  
    45. // 打印图的邻接表
    46. console.log("Graph adjacency list:");
    47. graph.printGraph();

    哈希表（Hash Table）

    哈希表是一种高效的数据结构，它通过哈希函数将键（key）映射到存储桶（bucket）中的索引，从而实现快速的查找、插入和删除操作。哈希表通常基于数组实现，每个存储桶可以存储一个或多个键值对。

    哈希表是一种高效的数据结构，它在平均情况下具有常数时间复杂度的插入、查找和删除操作。哈希表被广泛应用于各种计算机科学领域，如数据库索引、缓存实现、编译器和解释器等。

    基本概念：
    • 哈希函数：将键映射到存储桶索引的函数。
    • 存储桶：存储哈希表中的键值对的容器。
    • 碰撞（Collision）：当两个不同的键经过哈希函数映射到相同的存储桶时发生碰撞。
    • 负载因子（Load Factor）：哈希表中元素数量与存储桶数量的比值。
    • 哈希冲突解决方法：开放定址法、链表法、再哈希法、建立公共溢出区等。
    常见操作：
    • 插入（Insertion）：将键值对插入哈希表中。
    • 查找（Lookup）：根据键查找对应的值。
    • 删除（Deletion）：根据键删除键值对。
    • 调整大小（Resizing）：根据负载因子动态调整哈希表的大小。
    1. class HashTable {
    2.     constructor(size = 11) {
    3.         this.size = size; // 哈希表的大小
    4.         this.buckets = new Array(size).fill(null).map(() => []);
    5.     }
    6.  
    7.     // 哈希函数：将键映射到存储桶索引
    8.     hash(key) {
    9.         let hash = 0;
    10.         for (let i = 0; i < key.length; i++) {
    11.             hash = (hash << 5) + key.charCodeAt(i);
    12.         }
    13.         return hash % this.size;
    14.     }
    15.  
    16.     // 插入键值对
    17.     set(key, value) {
    18.         const index = this.hash(key);
    19.         const bucket = this.buckets[index];
    20.         for (let i = 0; i < bucket.length; i++) {
    21.             if (bucket[i][0] === key) {
    22.                 // 如果键已经存在，则更新值
    23.                 bucket[i][1] = value;
    24.                 return;
    25.             }
    26.         }
    27.         bucket.push([key, value]);
    28.     }
    29.  
    30.     // 获取键对应的值
    31.     get(key) {
    32.         const index = this.hash(key);
    33.         const bucket = this.buckets[index];
    34.         for (let i = 0; i < bucket.length; i++) {
    35.             if (bucket[i][0] === key) {
    36.                 return bucket[i][1];
    37.             }
    38.         }
    39.         return undefined; // 键不存在
    40.     }
    41.  
    42.     // 删除键值对
    43.     delete(key) {
    44.         const index = this.hash(key);
    45.         const bucket = this.buckets[index];
    46.         for (let i = 0; i < bucket.length; i++) {
    47.             if (bucket[i][0] === key) {
    48.                 return bucket.splice(i, 1)[0][1];
    49.             }
    50.         }
    51.         return undefined; // 键不存在
    52.     }
    53. }
    54.  
    55. // 创建一个哈希表实例
    56. const hashTable = new HashTable();
    57.  
    58. // 插入键值对
    59. hashTable.set("apple", 10);
    60. hashTable.set("banana", 20);
    61. hashTable.set("orange", 30);
    62.  
    63. // 获取键对应的值
    64. console.log(hashTable.get("apple")); // 输出：10
    65.  
    66. // 删除键值对
    67. console.log(hashTable.delete("banana")); // 输出：20
    68.  
    69. // 再次获取键对应的值
    70. console.log(hashTable.get("banana")); // 输出：undefined

    优先队列（Priority Queue）

    优先队列是一种特殊的队列，每个元素都关联有一个优先级。具有高优先级的元素会先被取出。优先队列的实现可以基于各种数据结构，例如堆、有序数组等。

    基本概念：
    • 优先级：用于确定元素被取出的顺序，通常是一个可以比较的值。
    • 插入：按照元素的优先级将元素插入队列中。
    • 取出：从队列中移除并返回具有最高优先级的元素。
    常见操作：
    • 插入（Insertion）：将元素插入队列中，并根据优先级进行调整。
    • 取出最高优先级元素（Extract-Max/Min）：从队列中移除并返回具有最高优先级的元素。
    • 查看最高优先级元素（Peek-Max/Min）：查看队列中具有最高优先级的元素，但不移除。
    1. // 使用最小堆实现优先队列
    2. class PriorityQueue {
    3.     constructor() {
    4.         this.heap = [];
    5.     }
    6.  
    7.     // 插入元素
    8.     insert(element, priority) {
    9.         const node = { element, priority };
    10.         this.heap.push(node);
    11.         this.siftUp(this.heap.length - 1);
    12.     }
    13.  
    14.     // 取出最高优先级元素
    15.     extractMin() {
    16.         if (this.heap.length === 0) return null;
    17.         if (this.heap.length === 1) return this.heap.pop().element;
    18.         const min = this.heap[0].element;
    19.         this.heap[0] = this.heap.pop();
    20.         this.siftDown(0);
    21.         return min;
    22.     }
    23.  
    24.     // 查看最高优先级元素
    25.     peek() {
    26.         return this.heap.length > 0 ? this.heap[0].element : null;
    27.     }
    28.  
    29.     // 上移操作（向上调整）
    30.     siftUp(index) {
    31.         let parentIndex = Math.floor((index - 1) / 2);
    32.         while (index > 0 && this.heap[parentIndex].priority > this.heap[index].priority) {
    33.             [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
    34.             index = parentIndex;
    35.             parentIndex = Math.floor((index - 1) / 2);
    36.         }
    37.     }
    38.  
    39.     // 下移操作（向下调整）
    40.     siftDown(index) {
    41.         let minIndex = index;
    42.         const leftChildIndex = index * 2 + 1;
    43.         const rightChildIndex = index * 2 + 2;
    44.         if (leftChildIndex < this.heap.length && this.heap[leftChildIndex].priority < this.heap[minIndex].priority) {
    45.             minIndex = leftChildIndex;
    46.         }
    47.         if (rightChildIndex < this.heap.length && this.heap[rightChildIndex].priority < this.heap[minIndex].priority) {
    48.             minIndex = rightChildIndex;
    49.         }
    50.         if (minIndex !== index) {
    51.             [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
    52.             this.siftDown(minIndex);
    53.         }
    54.     }
    55. }
    56.  
    57. // 创建一个优先队列实例
    58. const priorityQueue = new PriorityQueue();
    59.  
    60. // 插入元素
    61. priorityQueue.insert("Task 1", 3);
    62. priorityQueue.insert("Task 2", 2);
    63. priorityQueue.insert("Task 3", 1);
    64.  
    65. // 取出最高优先级元素
    66. console.log(priorityQueue.extractMin()); // 输出：Task 3

    字典树（Trie）

    字典树（Trie）是一种树形数据结构，用于高效地存储和检索字符串集合。字典树的每个节点代表一个字符串的字符，从根节点到叶子节点的路径构成一个字符串。字典树常用于搜索引擎、拼写检查和字典等应用中。

    字典树是一种非常高效的数据结构，特别适用于字符串的存储和检索。它的插入、搜索和删除操作的时间复杂度都是 O(m)，其中 m 是字符串的长度。

    基本概念：
    • 根节点（Root）：树的顶端节点，不包含任何字符，但是作为整个树的起点。
    • 节点（Node）：包含一个字符以及指向其子节点的指针的数据结构。
    • 子节点（Child Node）：一个节点的直接后继节点。
    • 叶子节点（Leaf Node）：没有子节点的节点，表示一个完整的字符串。
    • 路径（Path）：从根节点到任意节点的序列，表示一个字符串。
    • 字符串集合：所有从根节点到叶子节点的路径所表示的字符串的集合。
    基本操作：
    • 插入（Insertion）：将字符串插入字典树中。
    • 搜索（Search）：搜索字典树中是否存在某个字符串。
    • 删除（Deletion）：从字典树中删除某个字符串。
    1. class TrieNode {
    2.     constructor() {
    3.         this.children = new Map(); // 使用 Map 存储子节点，键为字符，值为子节点
    4.         this.isEndOfWord = false; // 标记是否是字符串的结束节点
    5.     }
    6. }
    7.  
    8. class Trie {
    9.     constructor() {
    10.         this.root = new TrieNode(); // 根节点
    11.     }
    12.  
    13.     // 插入字符串
    14.     insert(word) {
    15.         let node = this.root;
    16.         for (const char of word) {
    17.             if (!node.children.has(char)) {
    18.                 node.children.set(char, new TrieNode());
    19.             }
    20.             node = node.children.get(char);
    21.         }
    22.         node.isEndOfWord = true; // 将最后一个节点标记为单词的结束节点
    23.     }
    24.  
    25.     // 搜索字符串
    26.     search(word) {
    27.         let node = this.root;
    28.         for (const char of word) {
    29.             if (!node.children.has(char)) {
    30.                 return false; // 字符串不存在
    31.             }
    32.             node = node.children.get(char);
    33.         }
    34.         return node.isEndOfWord; // 判断最后一个节点是否是单词的结束节点
    35.     }
    36.  
    37.     // 删除字符串
    38.     delete(word) {
    39.         this.deleteRecursive(this.root, word, 0);
    40.     }
    41.  
    42.     // 递归删除字符串
    43.     deleteRecursive(node, word, index) {
    44.         if (index === word.length) {
    45.             // 当 index 等于字符串长度时，表示找到了要删除的字符串
    46.             if (!node.isEndOfWord) {
    47.                 return false; // 字符串不存在
    48.             }
    49.             node.isEndOfWord = false; // 取消最后一个节点的结束标记
    50.             return node.children.size === 0; // 返回当前节点是否可以被删除
    51.         }
    52.  
    53.         const char = word[index];
    54.         if (!node.children.has(char)) {
    55.             return false; // 字符串不存在
    56.         }
    57.         const shouldDeleteCurrentNode = this.deleteRecursive(node.children.get(char), word, index + 1);
    58.  
    59.         if (shouldDeleteCurrentNode) {
    60.             node.children.delete(char); // 删除当前节点的子节点
    61.             return node.children.size === 0; // 返回当前节点是否可以被删除
    62.         }
    63.  
    64.         return false;
    65.     }
    66. }
    67.  
    68. // 创建一个 Trie 实例
    69. const trie = new Trie();
    70.  
    71. // 插入字符串
    72. trie.insert("apple");
    73. trie.insert("banana");
    74.  
    75. // 搜索字符串
    76. console.log(trie.search("apple")); // 输出：true
    77. console.log(trie.search("banana")); // 输出：true
    78. console.log(trie.search("orange")); // 输出：false
    79.  
    80. // 删除字符串
    81. trie.delete("banana");
    82. console.log(trie.search("banana")); // 输出：false

    并查集（Disjoint Set）

    并查集（Disjoint Set）是一种数据结构，用于管理元素的分组以及在不相交的集合之间进行合并和查询。它通常用于解决一些集合的合并与查询问题，比如判断图中的连通分量、快速查找两个元素是否属于同一集合等。

    基本概念：
    • 集合（Set）：由若干元素组成的集合。
    • 并查集（Disjoint Set）：由若干不相交的集合组成的数据结构，每个集合被称为一个组或者一个集合。
    • 元素（Element）：并查集中的每个对象，每个元素都属于一个集合。
    • 代表元（Representative Element）：每个集合中的一个元素被选为代表元，通常是集合中的某个元素。
    • 合并（Union）：将两个集合合并成一个集合。
    • 查找（Find）：确定一个元素属于哪个集合，通常找到其代表元。
    基本操作：
    • 初始化（MakeSet）：将每个元素初始化为一个独立的集合。
    • 查找（Find）：找到元素所在的集合的代表元素。
    • 合并（Union）：将两个元素所在的集合合并成一个集合。
    实现方式：

    并查集的实现方式有多种，其中较为常见的是基于数组和基于树的实现方式。基于树的实现方式包括基于树的深度优化（按秩合并）和基于路径的优化（路径压缩）。

    1. class DisjointSet {
    2.     constructor(size) {
    3.         this.parent = new Array(size); // 记录每个元素的父节点
    4.         this.rank = new Array(size).fill(0); // 记录每个集合的秩（树的高度）
    5.         for (let i = 0; i < size; i++) {
    6.             this.parent[i] = i; // 初始化时，每个元素的父节点为自身
    7.         }
    8.     }
    9.  
    10.     // 查找元素所在集合的代表元素（根节点）
    11.     find(x) {
    12.         if (this.parent[x] !== x) {
    13.             this.parent[x] = this.find(this.parent[x]); // 路径压缩，将 x 的父节点设为根节点
    14.         }
    15.         return this.parent[x];
    16.     }
    17.  
    18.     // 合并两个元素所在的集合
    19.     union(x, y) {
    20.         const rootX = this.find(x);
    21.         const rootY = this.find(y);
    22.         if (rootX !== rootY) {
    23.             // 按秩合并，将秩较小的树合并到秩较大的树上
    24.             if (this.rank[rootX] < this.rank[rootY]) {
    25.                 this.parent[rootX] = rootY;
    26.             } else if (this.rank[rootX] > this.rank[rootY]) {
    27.                 this.parent[rootY] = rootX;
    28.             } else {
    29.                 this.parent[rootY] = rootX;
    30.                 this.rank[rootX]++; // 若两棵树的秩相同，则合并后新树的秩加一
    31.             }
    32.         }
    33.     }
    34. }
    35.  
    36. // 创建一个并查集实例
    37. const disjointSet = new DisjointSet(5);
    38.  
    39. // 合并集合
    40. disjointSet.union(0, 1);
    41. disjointSet.union(2, 3);
    42. disjointSet.union(0, 4);
    43.  
    44. // 查找元素所在集合的代表元素
    45. console.log(disjointSet.find(1)); // 输出：0
    46. console.log(disjointSet.find(2)); // 输出：2
    47. console.log(disjointSet.find(3)); // 输出：2
    48. console.log(disjointSet.find(4)); // 输出：0

    AVL 树、红黑树:

    AVL树和红黑树都是自平衡二叉搜索树，它们都能够在插入和删除操作后通过旋转等操作来保持树的平衡，从而保证了树的搜索、插入和删除等操作的时间复杂度都为 O(log n)，其中 n 是树中节点的数量。

    AVL树（Adelson-Velsky and Landis Tree）

    AVL树是由两位苏联计算机科学家G.M. Adelson-Velsky和E.M. Landis于1962年提出的一种自平衡二叉搜索树。在AVL树中，任意节点的左右子树的高度差不超过1。

    特点：
    • AVL树是严格平衡的，任意节点的左右子树高度差不超过1。
    • 插入和删除节点时，可能需要进行单旋转或双旋转等操作来保持树的平衡。
    • AVL树的平衡性更强，适用于对搜索性能有严格要求的场景。
    红黑树（Red-Black Tree）

    红黑树是由Rudolf Bayer于1972年发明的，由Leo J. Guibas和Robert Sedgewick在1978年改进后广泛应用于计算机科学中。红黑树是一种近似平衡的二叉搜索树，它通过一些特定规则来保持树的大致平衡。

    特点：
    • 红黑树是近似平衡的，不像AVL树那样严格保持平衡。
    • 每个节点要么是红色，要么是黑色。
    • 根节点是黑色的，叶子节点（NIL节点，空节点）是黑色的。
    • 如果一个节点是红色的，则它的子节点都是黑色的（红黑树的第4条性质）。
    • 从根节点到叶子节点的每条路径上，黑色节点的数量是相同的。
    • 插入和删除节点时，通过颜色变换和旋转等操作来保持树的平衡。
    应用场景：
    • 红黑树的平衡性相对AVL树更弱一些，但是它在插入和删除操作上比AVL树更高效一些，因此在实际应用中更为常见。
    • Java中的TreeMap和TreeSet、C++中的map和set等STL容器的底层实现就是红黑树。

    总的来说，AVL树和红黑树都是非常重要的数据结构，在工程中应用广泛，根据具体场景的需求选择合适的树来使用

    2.基本算法

    • 排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、堆排序等

    链接：基本排序算法-CSDN博客

    • 线性搜索、二分搜索

    链接：基本搜索/查找算法-CSDN博客

    • 递归和回溯算法

    链接：递归和回溯算法使用-CSDN博客

    • 动态规划算法

    链接：动态规划问题-CSDN博客

    • 贪心算法

    链接：贪心算法相关-CSDN博客

    • 分治算法

    链接：分治算法相关-CSDN博客

    • 深度优先搜索（DFS）和广度优先搜索（BFS）

    链接：基本搜索/查找算法-CSDN博客

    3.高阶数据结构与算法(难！！！！)

    • 平衡树：AVL 树、红黑树、B 树、B+ 树

    链接：平衡树：AVL 树、红黑树、B 树、B+ 树-CSDN博客

    • 图的搜索算法：Dijkstra 算法、Bellman-Ford 算法、Floyd-Warshall 算法
    • 最短路径算法：Dijkstra 算法、Bellman-Ford 算法、Floyd-Warshall 算法

    链接：图的搜索算法：Dijkstra 算法、Bellman-Ford 算法、Floyd-Warshall 算法-CSDN博客

    • 字符串匹配算法：暴力匹配、KMP 算法、Boyer-Moore 算法、Rabin-Karp 算法

    链接：字符串匹配算法

    • 最小生成树算法：Prim 算法、Kruskal 算法

    链接：最小生成树算法：Prim 算法、Kruskal 算法-CSDN博客

    • 负载均衡算法：轮询、加权轮询、哈希、最小连接数等
  • 相关阅读:
    Java--日志管理
    奇妙的跨域错误-Access-Control-Request-Private-Network
    含文档+PPT+源码等]精品基于Nodejs实现的商品|物品交互|互换平台[包运行成功]
    【input系统】MotionEvent的分解
    Echarts tree树图按层级自定义容器宽高及显示隐藏层级后重新渲染树图宽高
    解决类重复的问题
    电脑技巧：低配置的旧电脑也可以使用Win11系统了
    base64.c
    【算法每日一练]-旅行商（保姆级教程 篇1）
    具体项目下解决Echarts多端同步开发和维护的问题
  • 原文地址：https://blog.csdn.net/xhc6666/article/details/136616141