定义和特点

• 栈是一种线性数据结构，具有后进先出（LIFO）的特性。
• 可以类比为一叠盘子，只能从顶部放入和取出元素。
• 可以使用数组的push()和pop()方法来实现。

分类

「顺序栈」：即堆栈的顺序存储结构。利用一组地址连续的存储单元依次存放自栈底到栈顶的元素，同时使用指针 𝑡𝑜𝑝 指示栈顶元素在顺序栈中的位置。

「链式栈」：即堆栈的链式存储结构。利用单链表的方式来实现堆栈。栈中元素按照插入顺序依次插入到链表的第一个节点之前，并使用栈顶指针 𝑡𝑜𝑝 指示栈顶元素，𝑡𝑜𝑝 永远指向链表的头节点位置。

定义和特点

队列（Queue）：一种线性表数据结构，是一种只允许在表的一端进行插入操作，而在表的另一端进行删除操作的线性表。

• 队列是一种线性数据结构，具有先进先出（FIFO）的特性。
• 可以类比为排队买票，先来的人先被服务。
• 可以使用数组的push()和shift()方法来实现。

基本操作

• 入队（Enqueue）：将元素放入队列的末尾。
• 出队（Dequeue）：从队列的头部移除元素，并返回移除的元素。
• 获取队头元素（Front）：返回队列头部的元素，并不移除该元素。
• 判断队列是否为空（isEmpty）：检查队列是否为空。

动态规划（Dynamic Programming）：简称 DP，是一种求解多阶段决策过程最优化问题的方法。在动态规划中，通过把原问题分解为相对简单的子问题，先求解子问题，再由子问题的解而得到原问题的解。

思想

动态规划的核心思想：

1. 把「原问题」分解为「若干个重叠的子问题」，每个子问题的求解过程都构成一个 「阶段」。在完成一个阶段的计算之后，动态规划方法才会执行下一个阶段的计算。
2. 在求解子问题的过程中，按照「自顶向下的记忆化搜索方法」或者「自底向上的递推方法」求解出「子问题的解」，把结果存储在表格中，当需要再次求解此子问题时，直接从表格中查询该子问题的解，从而避免了大量的重复计算。

进制转换方法

在JavaScript中，进行进制转换的方法主要有两种：parseInt() 和 toString()。

方法	描述
parseInt(string, radix)	将字符串按照指定的进制解析为整数。 radix 是可选参数，表示字符串的进制，范围在2到36之间。如果省略radix，或者其值为0，则数字将以10为基础来解析。 如果字符串以 "0x" 或 "0X" 开头，则将以16为基数。如果radix小于2或大于36，parseInt() 将返回 NaN。
toString(radix)	这个方法返回一个表示该对象的字符串 radix是一个介于2到36之间的整数，表示要使用的基数。 如果省略该参数，则默认返回十进制字符串。

枚举算法（也称为穷举算法）是一种通过列举问题所有可能的解来求解问题的算法。这种算法会一一考察问题所有可能的解，并判断每一种可能是否满足问题的全部条件。如果满足全部条件，则找到了问题的解；否则，继续考察下一种可能。

枚举算法的解题思路主要包括以下几个步骤：

1. 确定问题的解空间：首先，需要明确问题的所有可能解，即解空间。这通常涉及对问题的深入理解，以便能够列举出所有可能的情况。
2. 列举所有可能解：在确定了解空间之后，接下来就需要通过循环或递归等方式，将解空间中的所有可能解一一列举出来。
3. 验证解的合法性：对于每一个可能的解，都需要通过某种方式验证其是否满足问题的条件。这通常涉及将解代入到问题的条件中进行检验。
4. 输出结果：如果找到了满足条件的解，就将其输出。如果没有找到满足条件的解，则可能需要调整搜索策略或重新审视问题的定义。

分类

基础概念

数据结构

• 根据数据结构，可以分为线性表、字符串、树、图。

线性表

字符串

树结构

图结构

时间复杂度

• 一个算法的时间复杂度反映了程序运行从开始到结束所需要的时间。

• 把算法中基本操作重复执行的次数（频度）作为算法的时间复杂度。

  • 没有循环语句，记作O(1)，也称为常数阶。
  • 只有一重循环，则算法的基本操作的执行频度与问题规模n呈线性增大关系，记作O（n），也叫线性阶。

• 常见的时间复杂度有：

  • O(1): Constant Complexity: Constant 常数复杂度：表示算法的执行时间不随输入规模的增长而变化，即执行时间是固定的。例如，访问一个数组的任意一个元素，无论数组的大小是多少，都只需要一步操作。
  • O(log n): Logarithmic Complexity: 对数复杂度：表示算法的执行时间随输入规模呈对数增长。例如，二分查找算法，在每次比较后都能将搜索范围减半，所以执行时间随着输入规模的增大而缩小。
  • O(n): Linear Complexity: 线性时间复杂度：表示算法的执行时间与输入规模成线性关系。例如，遍历一个包含n个元素的数组，需要执行n次操作。
  • O(n^2): N square Complexity 平⽅方：表示算法的执行时间随输入规模的平方增长。例如，嵌套循环遍历一个包含n个元素的数组，总共需要执行n^2次操作。
  • O(n^3): N square Complexity ⽴立⽅方：三层嵌套循环遍历一个包含n个元素的数组，总共需要执行n^2次操作。
    • 对于n层嵌套的循环，时间复杂度的计算方法与三层循环类似。我们需要分析每一层循环的执行次数，并将它们相乘。
  • O(2^n): Exponential Growth 指数
  • O(n!): Factorial 阶乘

哈希表（Hash Table）也称为散列表，是一种基于哈希函数（Hashing Function）实现的数据结构，用于存储键值对（key-value pairs）。

哈希函数将键（key）映射为索引（通常称为哈希值或散列值），然后使用该索引在数组中查找或存储值（value）。

思想

哈希表的关键思想是使用哈希函数，将键 key 映射到对应表的某个区块中。

可以将算法思想分为两个部分：

• 向哈希表中插入一个关键码值：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中。
• 在哈希表中搜索一个关键码值：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值。

图的分类

• 无向图：图中任意两个顶点之间的边都是没有方向的。

  • 无向完全图：含n个顶点无向图，边数达到最大n(n-1)/2；

• 有向图：图中任意两个顶点之间的边都是有方向的。

  • 有向完全图：含n个顶点，弧数达到最大n(n-1)；

• 加权图：图中的每条边都带有一个相关的权重。这里的权重可以是任何一种度量，比如时间，距离，尺寸等。

  • 生活中最常见的「加权图」应该就是我们的地图了。

    在下方的「图 3. 加权图的示例图」中，每条边上都标有距离，它们可以视为每个边上的权重。

完全二叉树和满二叉树

• 完全二叉树：若二叉树的深度为h，则除第h层外，其他层的结点全部达到最大值，且第h层的所有结点都集中在左子树。

• 满二叉树：满二叉树是一种特殊的的完全二叉树，所有层的结点都是最大值。

堆分类

1. 大顶堆（Max Heap）：大顶堆中，每个节点的值都大于或等于其子节点的值。堆顶元素是集合中的最大值。

2. 小顶堆（Min Heap）：小顶堆中，每个节点的值都小于或等于其子节点的值。堆顶元素是集合中的最小值。

3. 二叉堆（Binary Heap）：二叉堆是堆的一种常见实现方式，它使用完全二叉树来存储堆结构，并通过数组来表示。它可以分为大顶堆和小顶堆。

4. 斐波那契堆（Fibonacci Heap）：斐波那契堆是一种更高级的堆数据结构，它在某些操作上具有更高的效率，例如合并堆和减小关键字操作。它是由多个最小堆组成的，可以包含相同的关键字。

基础

JavaScript 字符串基础参考：JavaScript 基础 | Sewen 博客 (sewar-x.github.io)

定义

• 空串：空串指的是未存储任何字符的串，整个串的长度为 0。

• 空格串：空格串指的是由多个（＞0）空格字符组成的串结构，整个串的长度为包含空格字符的个数。

• 子串和主串：

  假设有以下两个串 A 和 B：
  
  A：shujujiegou
  B：shuju
  

  在串 A 中可以找到几个连续的字符，它们和串 B 相同。我们可以这样描述它们之间的关系：A 是 B 的主串，B 是 A 的子串。

  • 注意：子串在主串中的位置，指的是子串首个字符在主串中的位置。
    • 例如，串 A 为 "shujujiegou"，串 B 为 "jiegou"，通过观察可以判断 A、B 是主串和子串的关系，即在主串 A 中可以找到 B，B 的第一个字符 'j' 是串 A 中的第 6 个字符，因此子串 B 在主串 A 中的位置就是 6。