算法总结
type
status
date
slug
summary
tags
category
icon
password
Blocking
Blocked by
top
URL
Sub-item
Parent item
时间复杂度
时间复杂度就是一个函数，用大 O 表示，比如 O(1)、O(n)、O(logN)... 定性描述该算法的运行时间
- O(1) 复杂度
因为每次执行代码文件，永远只会执行一次
- O(n)
- O(n^2)
- O(logN)
空间复杂度
一个函数，用大 O 表示，比如 O(1) O(n) O(n^2) ... 算法在与运行过程中临时占用存储空间大小的量度
- O(1)
- O(n)
- O(n^2)
数据结构
常见的数据结构：数组、链表、栈、队列、哈希表、树、堆、图。
数组
[数组 array]是一种线性数据结构，其将元素存储在连续的内存空间中。
优点
数组存储在连续的内存空间内，且元素类型相同。这种做法包含丰富的先验信息，系统可以利用这些信息来优化数据结构的操作效率。
- 空间效率高：数组为数据分配了连续的内存块，无须额外的结构开销。
- 支持随机访问：数组允许在 O（1） 时间内访问任何元素。
- 缓存局部性：当访问数组元素时，计算机不仅会加载它，还会缓存其周围的其他数据，从而借助高速缓存来提升后续操作的执行速度。
缺点
连续空间存储是一把双刃剑，其存在以下局限性。
- 插入与删除效率低：当数组中元素较多时，插入与删除操作需要移动大量的元素。
- 长度不可变：数组在初始化后长度就固定了，扩容数组需要将所有数据复制到新数组，开销很大。
- 空间浪费：如果数组分配的大小超过实际所需，那么多余的空间就被浪费了。
链表
「链表 linked list」元素存储不连续，通过指针连在一起。
优点
- 动态性：链表的长度可以动态地增加或减少，不需要预先指定大小。这使得链表在需要频繁地插入和删除元素时更加高效，因为它不需要像数组那样进行元素的移动和重新分配内存。
- 灵活性：链表可以轻松地实现各种数据结构，如栈、队列和双向链表。通过改变节点之间的指针关系，可以方便地进行插入、删除和反转操作。
- 内存管理：链表的节点可以在内存的不同位置分配，不需要连续的内存块。这使得链表更适合处理动态分配和释放内存的场景。
缺点
- 随机访问效率低：链表的节点不像数组那样可以通过索引直接访问，而是需要从头节点开始遍历链表，直到找到目标节点。这使得链表的随机访问效率较低，时间复杂度为 O(n)，其中 n 是链表的长度。
- 额外的空间开销：链表中每个节点都需要额外的指针来指向下一个节点，这增加了存储空间的开销。相比于数组，链表需要更多的内存空间来存储相同数量的元素。
- 不支持直接访问前一个节点：普通的单向链表只能从头节点到尾节点进行遍历，无法直接访问前一个节点。如果需要反向遍历链表或在特定位置插入或删除节点，需要使用双向链表。
常见链表类型
- 单向链表：即前面介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。我们将首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 。
- 环形链表：如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
- 双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。
链表 VS 数组
ㅤ | 数组 | 链表 |
存储方式 | 连续内存空间 | 分散内存空间 |
容量扩展 | 长度不可变 | 可灵活扩展 |
内存效率 | 元素占用内存少、但可能浪费空间 | 元素占用内存多 |
访问元素 | O(1) | O(n) |
添加元素 | O(n) | O(1) |
删除元素 | O(n) | O(1) |
- 数组：增删非首尾元素时往往需要移动元素。
- 链表：增删非首尾元素，不需要移动元素，只需要更改 next 的指向即可。
JavaScript 中可以用 Object 模拟链表
栈
「栈 stack」是一种遵循先入后出的逻辑的线性数据结构。栈遵循先入后出的原则，因此我们只能在栈顶添加或删除元素。
数组和链表都可以在任意位置添加和删除元素，因此栈可以视为一种受限制的数组或链表。
典型应用
- 软件中的撤销与反撤销
撤销（undo）和反撤销（redo）具体是如何实现的？
使用两个堆栈，栈
A 用于撤销，栈 B 用于反撤销。- 每当用户执行一个操作，将这个操作压入栈
A，并清空栈B。
- 当用户执行“撤销”时，从栈
A中弹出最近的操作，并将其压入栈B。
- 当用户执行“反撤销”时，从栈
B中弹出最近的操作，并将其压入栈A。
队列
「队列 queue」是一种遵循先入先出规则的线性数据结构。
典型应用
- 各类待办事项。任何需要实现“先来后到”功能的场景，例如排队取号，淘宝订单，出餐队列
哈希表
「哈希表 hash table」，又称「散列表」，其通过建立键 key 与值 value 之间的映射，实现高效的元素查询。
优点
- 高效的增删改查，哈希表的增删改查操作能够在O(1)时间完成。
缺点
- 冲突的处理：由于哈希函数的映射并非完全唯一，不同的键可能会映射到相同的存储桶中，这就是冲突。
- 内存消耗：为了存储哈希表的键和值，需要分配额外的内存空间。在存储大量数据时，哈希表可能占用较多的内存。
- 遍历顺序不确定：哈希表中的元素没有固定的顺序。
典型应用
- 数据存储和检索，例如数据库
- 唯一性检查。
- 缓存实现。
二叉树
[二叉树 binary tree」是一种非线性数据结构，代表“祖先”与“后代”之间的派生关系，体现了“一分为二”的分治逻辑。
二叉树的所有问题，就是让你在前中后序位置注入逻辑代码。
类型
- 完美二叉树
即所有层的节点都被完全填满。
- 完全二叉树
只有最底层的节点未被填满，且最底层节点尽量靠左填充。
- 平衡二叉树
任意节点的左子树和右子树的高度之差的绝对值不超过 1 。
优点
二叉树的数组表示主要有以下优点。
- 数组存储在连续的内存空间中，对缓存友好，访问与遍历速度较快。
- 不需要存储指针，比较节省空间。
- 允许随机访问节点。
缺点
- 数组存储需要连续内存空间，因此不适合存储数据量过大的树。
- 增删节点需要通过数组插入与删除操作实现，效率较低。
- 当二叉树中存在大量 NONE 时，数组中包含的节点数据比重较低，空间利用率较低。
堆
「堆 heap」是一种满足特定条件的完全二叉树，主要可分为两种类型:
- 「大顶堆 max heap」：任意节点的值 ≥其子节点的值。
- 「小顶堆 min heap」：任意节点的值 ≤其子节点的值。
典型应用
- 优先队列：堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为 ，而建队操作为 ，这些操作都非常高效。
- 堆排序：给定一组数据，我们可以用它们建立一个堆，然后不断地执行元素出堆操作，从而得到有序数据。然而，我们通常会使用一种更优雅的方式实现堆排序，详见“堆排序”章节。
- 获取最大的K个元素：这是一个经典的算法问题，同时也是一种典型应用，例如选择热度前 10 的新闻作为微博热搜，选取销量前 10 的商品等。
图
「图 graph」是一种非线性数据结构，图由顶点和边组成，可以表示为一组顶点和一组边构成的集合。
算法
二分查找
思路：它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。
排序
选择排序
找到队列中的最小值并 将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。
冒泡排序
开启一个循环，每轮从未排序区间首位开始比较两个相邻的项，如果第一个比第二个大，则交换它们。这样每轮循环都会找到一个最大的数在最后。
插入排序
将第一个元素视为有序序列，剩下的元素作为未排序序列。从头到尾扫描未排序序列，将当前元素插入到有序序列的合适位置。如果待插入的元素与有序序列中的某个元素相等或大于，则将待插入元素插入到相等元素的后面。重复循环，直到未排序序列为空。
这个过程类似于玩斗地主时抓牌的过程，将每张新抓的牌与手中已有的牌进行比较，找到合适的位置插入。
快速排序
采用分治的思想来进行排序。
快速排序的基本思想是选择一个基准元素，通过一趟排序将待排序的序列分割成独立的两部分，其中一部分的所有元素都小于基准元素，另一部分的所有元素都大于基准元素，然后对这两部分分别进行递归排序，最终得到一个有序序列。
归并排序
采用分治的思想来进行排序。
将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。 时间复杂度为 O(n log n)。
堆排序
- 输入数组并建立大顶堆。完成后，最大元素位于堆顶。
- 1. 从堆顶元素开始，从顶到底执行堆化操作（Sift Down）。完成堆化后，堆的性质得到修复。
二叉树
二叉树的所有问题，就是让你在前中后序位置注入逻辑代码。
使用场景
- 求根到叶子节点数字之和
- 平衡二叉树
解题思路
1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个
traverse 函数配合外部变量来实现。2、是否可以定义一个递归函数，通过子问题（子树）的答案推导出原问题的答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值。
3、无论使用哪一种思维模式，你都要明白二叉树的每一个节点需要做什么，需要在什么时候（前中后序）做
四种遍历方式
前序遍历
根结点 ---> 左节点 ---> 右节点
中序遍历
左子树---> 根结点 ---> 右子树
后序遍历
左子树 ---> 右子树 ---> 根结点
层序遍历
从上到下，从左到右访问。
前序位置的代码只能从函数参数中获取父节点传递来的数据，而后序位置的代码不仅可以获取参数数据，还可以获取到子树通过函数返回值传递回来的数据。一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
双指针
数组和链表算法主要都是使用双指针，双指针分为两类：
应用场景
- 分发饼干
- 验证回文串
- 移动零
- 合并两个有序数组
左右指针
两个指针相向而行或相背而行。
使用场景：
- 二分查找
- 两数之和
- 反转数组
- 回文判断
快慢指针
两个指针同向而行，一快一慢。
使用场景：
- 涉及到第n个
- 涉及到原地修改的，例如数组去重，数组移除元素
- 滑动窗口算法
- 二分查找
- 两数之和
深度优先搜索（DFS）、广度优先搜索（BFS）
BFS
本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径
BFS 与DFS 区别
方式：
DFS是深度遍历，通过递归，遍历所有路径才能找到。
BFS是广度遍历，通过队列，遍历当前路径。不满足条件，才会进行下一层路径遍历，所以BFS 找到的路径一定是最短的。
空间复杂度：
DFS遍历使用递归，最坏情况就是树的高度，也就是
O(logN)，空间复杂度低。BFS遍历使用队列，队列中需要存储一层的所有节点，也就是
O(N)，空间复杂度高。BFS使用场景
- 层序遍历
- 找最短路径
解题思路：
双向BFS优化
原理
传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止。按照传统 BFS 算法的策略，会把整棵树的节点都搜索一遍，最后找到
target；而双向 BFS 其实只遍历了半棵树就出现了交集，也就是找到了最短距离。局限
必须知道终点在哪里。
滑动窗口
解题思路
- 定义左右指针
- 先移动右指针，
- 每当满足收缩条件时，就移动左指针，
- 直到不满足条件后，再重新开始移动右指针。
使用场景
- 查找子串
- 长度最小的子数组
思路
动态规划
它将一个问题分解为一系列更小的子问题，并通过存储子问题的解来避免重复计算，从而大幅提升时间效率。
最典型的应用：斐波那契数列
0 1 1 2 3 5 例如第三个 等于 第一个 + 第二个 定义子问题：F(n) = F(n - 1) + F(n - 2) 反复执行：从 2 循环到 n ，执行上面的公式。
动态规划问题都是斐波那契数列的变种。
应用场景
- 爬楼梯
- 找钱
动态规划 VS 分而治之
- 分治算法递归地将原问题划分为多个相互独立的子问题，直至最小子问题，并在回溯中合并子问题的解，最终得到原问题的解。
- 动态规划也对问题进行递归分解，但与分治算法的主要区别是，动态规划中的子问题是相互依赖的，在分解过程中会出现许多重叠子问题。
- 回溯算法在尝试和回退中穷举所有可能的解，并通过剪枝避免不必要的搜索分支。原问题的解由一系列决策步骤构成，我们可以将每个决策步骤之前的子序列看作一个子问题。
实际上，动态规划常用来求解最优化问题，它们不仅包含重叠子问题，还具有另外两大特性：最优子结构、无后效性。
贪心
其基本思想是在问题的每个决策阶段，都选择当前看起来最优的选择，即贪心地做出局部最优的决策，以期获得全局最优解。
比如找零钱，你面前放着 100 张人民币，我们贪心地选择不大于且最接近它的硬币，不断循环该步骤，直至凑出目标金额为止。你只能拿十张，怎么才能拿最多的面额？显然每次选择剩下钞票中面值最大的一张，最后你的选择一定是最优的。
应用场景
- 硬币找零问题：在某些硬币组合下，贪心算法总是可以得到最优解。
- 区间调度问题：假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解。
- 分数背包问题：给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高（价值 / 重量）的物品，那么贪心算法在一些情况下可以得到最优解。
- 股票买卖问题：给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润。
分治
它将一个问题分成多个和原问题类似的小问题，递归解决小问题，再将结果合并以解决原来的问题。
包括分（划分）和治（合并）两个阶段，通常基于递归实现。
- 分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
- 治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。
使用场景
- 归并排序 分：把数组从中间一份为二。合：合并两个有序子数组。
- 快速排序 分：选基准数，分成两个数组。 合：对两个子数组进行合并。
回溯
本质就是穷举法，通过对解空间进行深度优先遍历来寻找符合条件的解。在搜索过程中，遇到满足条件的解则记录，直至找到所有解或遍历完成后结束。
回溯算法的搜索过程包括尝试与回退两个部分。它通过深度优先搜索来尝试各种选择，当遇到不满足约束条件的情况时，则撤销上一步的选择，退回到之前的状态，并继续尝试其他选择。尝试与回退是两个方向相反的操作。
回溯问题通常包含多个约束条件，它们可用于实现剪枝操作。剪枝可以提前结束不必要的搜索分支，大幅提升搜索效率。
