AI summary
type
status
date
Dec 22, 2023 01:52 AM
slug
summary
tags
category
icon
password
靈、Author前传
一、数据结构
数组 & 链表
应用场景 - 数组
数组是一种基础且常见的数据结构，既频繁应用在各类算法之中，也可用于实现各种复杂数据结构。
- 随机访问:如果我们想要随机抽取一些样本，那么可以用数组存储，并生成一个随机序列，根据索引实 现样本的随机抽取。
- 排序和搜索:数组是排序和搜索算法最常用的数据结构。快速排序、归并排序、二分查找等都主要在数 组上进行。
- 查找表:当我们需要快速查找一个元素或者需要查找一个元素的对应关系时，可以使用数组作为查找 表。假如我们想要实现字符到 ASCII 码的映射，则可以将字符的 ASCII 码值作为索引，对应的元素存 放在数组中的对应位置。
- 机器学习:神经网络中大量使用了向量、矩阵、张量之间的线性代数运算，这些数据都是以数组的形式 构建的。数组是神经网络编程中最常使用的数据结构。
- 数据结构实现:数组可以用于实现栈、队列、哈希表、堆、图等数据结构。例如，图的邻接矩阵表示实 际上是一个二维数组。
应用场景 - 链表
单向链表通常用于实现栈、队列、哈希表和图等数据结构。
- 栈与队列:当插入和删除操作都在链表的一端进行时，它表现出先进后出的的特性，对应栈;当插入操 作在链表的一端进行，删除操作在链表的另一端进行，它表现出先进先出的特性，对应队列。
- 哈希表:链地址法是解决哈希冲突的主流方案之一，在该方案中，所有冲突的元素都会被放到一个链表 中。
- 图:邻接表是表示图的一种常用方式，在其中，图的每个顶点都与一个链表相关联，链表中的每个元素 都代表与该顶点相连的其他顶点。
双向链表常被用于需要快速查找前一个和下一个元素的场景。
- 高级数据结构:比如在红黑树、B 树中，我们需要访问节点的父节点，这可以通过在节点中保存一个指 向父节点的引用来实现，类似于双向链表。
- 浏览器历史:在网页浏览器中，当用户点击前进或后退按钮时，浏览器需要知道用户访问过的前一个和 后一个网页。双向链表的特性使得这种操作变得简单。
- LRU 算法:在缓存淘汰算法(LRU)中，我们需要快速找到最近最少使用的数据，以及支持快速地添 加和删除节点。这时候使用双向链表就非常合适。
循环链表常被用于需要周期性操作的场景，比如操作系统的资源调度。
- 时间片轮转调度算法:在操作系统中，时间片轮转调度算法是一种常见的 CPU 调度算法，它需要对一 组进程进行循环。每个进程被赋予一个时间片，当时间片用完时，CPU 将切换到下一个进程。这种循 环的操作就可以通过循环链表来实现。
- 数据缓冲区:在某些数据缓冲区的实现中，也可能会使用到循环链表。比如在音频、视频播放器中，数 据流可能会被分成多个缓冲块并放入一个循环链表，以便实现无缝播放。
总结
- 链表通过更改引用(指针)实现高效的节点插入与删除，且可以灵活调整长度;但节点访问效率低、占
用内存较多。
C++ STL 里面的 std::list 已经实现了双向链表，但好像一些算法的书上都不怎么直接用这 个，是不是有什么局限性呢? 一方面，我们往往更青睐使用数组实现算法，而只有在必要时才使用链表，主要有两个原因。‧ 空间开销:由于每个元素需要两个额外的指针(一个用于前一个元素，一个用于后一个 元素)，所以 std::list 通常比 更占用空间。‧ 缓存不友好:由于数据不是连续存放的， 对缓存的利用率较低。一般情况下， std::vector 的性能会更好。另一方面，必要使用链表的情况主要是二叉树和图。栈和队列往往会使用编程语言提供的 stack 和 queue ，而非链表。
初始化列表 res = [0] * self.size() 操作，会导致 res 的每个元素引用相同的地址吗? 不会。但二维数组会有这个问题，例如初始化二维列表 res = [[0] * self.size()] ，则多次 引用了同一个列表 [0] 。
栈 & 队列
应用场景 - 栈
- 浏览器中的后退与前进、软件中的撤销与反撤销。每当我们打开新的网页，浏览器就会将上一个网页执 行入栈，这样我们就可以通过后退操作回到上一页面。后退操作实际上是在执行出栈。如果要同时支持 后退和前进，那么需要两个栈来配合实现。
- 程序内存管理。每次调用函数时，系统都会在栈顶添加一个栈帧，用于记录函数的上下文信息。在递归 函数中，向下递推阶段会不断执行入栈操作，而向上回溯阶段则会执行出栈操作。
应用场景 - 队列
- 淘宝订单。购物者下单后，订单将加入队列中，系统随后会根据顺序依次处理队列中的订单。在双十一 期间，短时间内会产生海量订单，高并发成为工程师们需要重点攻克的问题。
- 各类待办事项。任何需要实现“先来后到”功能的场景，例如打印机的任务队列、餐厅的出餐队列等。 队列在这些场景中可以有效地维护处理顺序。
* 应用场景 - 双向队列
双向队列兼具栈与队列的逻辑，因此它可以实现这两者的所有应用场景，同时提供更高的自由度。
我们知道，软件的“撤销”功能通常使用栈来实现:系统将每次更改操作 push 到栈中，然后通过 pop 实现撤 销。然而，考虑到系统资源的限制，软件通常会限制撤销的步数(例如仅允许保存 50 步)。当栈的长度超过 50 时，软件需要在栈底(即队首)执行删除操作。但栈无法实现该功能，此时就需要使用双向队列来替代栈。 请注意，“撤销”的核心逻辑仍然遵循栈的先入后出原则，只是双向队列能够更加灵活地实现一些额外逻辑。
总结
- ‧ 栈是一种遵循先入后出原则的数据结构，可通过数组或链表来实现。
- ‧ 从时间效率角度看，栈的数组实现具有较高的平均效率，但在扩容过程中，单次入栈操作的时间复杂度
会劣化至 𝑂(𝑛) 。相比之下，基于链表实现的栈具有更为稳定的效率表现。
- ‧ 在空间效率方面，栈的数组实现可能导致一定程度的空间浪费。但需要注意的是，链表节点所占用的内
存空间比数组元素更大。
- ‧ 队列是一种遵循先入先出原则的数据结构，同样可以通过数组或链表来实现。在时间效率和空间效率的对比上，队列的结论与前述栈的结论相似。
- ‧ 双向队列是一种具有更高自由度的队列，它允许在两端进行元素的添加和删除操作。
在出栈后，是否需要释放出栈节点的内存?如果后续仍需要使用弹出节点，则不需要释放内存。若之后不需要用到，Java 和 Python 等语 言拥有自动垃圾回收机制，因此不需要手动释放内存;在 C 和 C++ 中需要手动释放内存。
撤销(undo)和反撤销(redo)具体是如何实现的?使用两个堆栈，栈 A 用于撤销，栈 B 用于反撤销。1. 每当用户执行一个操作，将这个操作压入栈A，并清空栈B。 2. 当用户执行“撤销”时，从栈A中弹出最近的操作，并将其压入栈B。 3. 当用户执行“反撤销”时，从栈B中弹出最近的操作，并将其压入栈A。
哈希表
hash 算法
近一个世纪以来，哈希算法处在不断升级与优化的过程中。一部分研究人员努力提升哈希算法的性能，另一
部分研究人员和黑客则致力于寻找哈希算法的安全性问题。表 6‐2 展示了在实际应用中常见的哈希算法。
- MD5 和 SHA‐1 已多次被成功攻击，因此它们被各类安全应用弃用。
- SHA‐2 系列中的 SHA‐256 是最安全的哈希算法之一，仍未出现成功的攻击案例，因此常被用在各类安全应用与协议中。
- SHA‐3 相较 SHA‐2 的实现开销更低、计算效率更高，但目前使用覆盖度不如 SHA‐2 系列。
数据结构中的 hash
在许多编程语言中，只有不可变对象才可作为哈希表的 key 。假如我们将列表(动态数组)作为 key ，当列
表的内容发生变化时，它的哈希值也随之改变，我们就无法在哈希表中查询到原先的 value 了。
虽然自定义对象(比如链表节点)的成员变量是可变的，但它是可哈希的。这是因为对象的哈希值通常是基
于内存地址生成的，即使对象的内容发生了变化，但它的内存地址不变，哈希值仍然是不变的。
细心的你可能发现在不同控制台中运行程序时，输出的哈希值是不同的。这是因为 Python 解释器在每次启
动时，都会为字符串哈希函数加入一个随机的盐(Salt)值。这种做法可以有效防止 HashDoS 攻击，提升
哈希算法的安全性。
总结
- 负载因子定义为哈希表中元素数量除以桶数量，反映了哈希冲突的严重程度，常用作触发哈希表扩容的条件。
- 链式地址通过将单个元素转化为链表，将所有冲突元素存储在同一个链表中。然而，链表过长会降低查询效率，可以进一步将链表转换为红黑树来提高效率。
- 开放寻址通过多次探测来处理哈希冲突。线性探测使用固定步长，缺点是不能删除元素，且容易产生聚
集。多次哈希使用多个哈希函数进行探测，相较线性探测更不易产生聚集，但多个哈希函数增加了计算量。
- 不同编程语言采取了不同的哈希表实现。例如，Java的HashMap使用链式地址，而Python的Dict采用开放寻址。
- 在哈希表中，我们希望哈希算法具有确定性、高效率和均匀分布的特点。在密码学中，哈希算法还应该 具备抗碰撞性和雪崩效应。
- 哈希算法通常采用大质数作为模数，以最大化地保证哈希值的均匀分布，减少哈希冲突。
- 常见的哈希算法包括 MD5、SHA‐1、SHA‐2 和 SHA3 等。MD5 常用于校验文件完整性，SHA‐2 常用于安全应用与协议。
- 编程语言通常会为数据类型提供内置哈希算法，用于计算哈希表中的桶索引。通常情况下，只有不可变
对象是可哈希的。
哈希表的时间复杂度为什么不是 𝑂(𝑛) ? 当哈希冲突比较严重时，哈希表的时间复杂度会退化至 𝑂(𝑛) 。当哈希函数设计的比较好、容 量设置比较合理、冲突比较平均时，时间复杂度是 𝑂(1) 。我们使用编程语言内置的哈希表时， 通常认为时间复杂度是 𝑂(1) 。
哈希表底层实现是数组、链表、二叉树，但为什么效率可以比他们更高呢?首先，哈希表的时间效率变高，但空间效率变低了。哈希表有相当一部分的内存是未使用的， 其次，只是在特定使用场景下时间效率变高了。如果一个功能能够在相同的时间复杂度下使 用数组或链表实现，那么通常比哈希表更快。这是因为哈希函数计算需要开销，时间复杂度的 常数项更大。 最后，哈希表的时间复杂度可能发生劣化。例如在链式地址中，我们采取在链表或红黑树中执 行查找操作，仍然有退化至 𝑂(𝑛) 时间的风险。
为什么哈希表同时包含线性数据结构和非线性数据结构?哈希表底层是数组，而为了解决哈希冲突，我们可能会使用“链式地址”(后续哈希表章节会 讲):数组中每个桶指向一个链表，当链表长度超过一定阈值时，又可能被转化为树(通常为红 黑树)。从存储的角度来看，哈希表的底层是数组，其中每一个桶槽位可能包含一个值，也可能 包含一个链表或树。因此，哈希表可能同时包含线性(数组、链表)和非线性(树)数据结构。
多次哈希有不能直接删除元素的缺陷吗?对于标记已删除的空间，这个空间还能再次使用吗? 多次哈希是开放寻址的一种，开放寻址法都有不能直接删除元素的缺陷，需要通过标记删除。 被标记为已删除的空间是可以再次被使用的。当将新元素插入哈希表，并且通过哈希函数找 到了被标记为已删除的位置时，该位置可以被新的元素使用。这样做既能保持哈希表的探测 序列不变，又能保证哈希表的空间使用率。
树
AVL 树应用
- 组织和存储大型数据，适用于高频查找、低频增删的场景。
- 用于构建数据库中的索引系统（B/B+树）。
- 红黑树在许多应用中比 AVL 树更受欢迎。这是因为红黑树的平衡条件相对宽松，在红黑树中插入与删除节点所需的旋转操作相对较少，其节点增删操作的平均效率更高。
在 C++ 中，函数被划分到 private 和 public 中，这方面有什么考量吗?为什么要将 height() 函数和 updateHeight() 函数分别放在 public 和 private 中呢? (https://github.com/krahets/hello-algo/blob/main/codes/cpp/chapter_tree/avl_tree.cpp) 主要看方法的使用范围，如果方法只在类内部使用，那么就设计为 private 。例如，用户单独 调用 是没有意义的，它只是插入、删除操作中的一步。而 height() 是访问节 点高度，类似于 ，因此设置成 public 以便使用。
在 Java 中，字符串对比是否一定要用 equals() 方法? 在 Java 中，对于基本数据类型，== 用于对比两个变量的值是否相等。对于引用类型，两种符 号的工作原理是不同的。‧ == :用来比较两个变量是否指向同一个对象，即它们在内存中的位置是否相同。 ‧ equals():用来对比两个对象的值是否相等。因此如果要对比值，我们通常会用 equals() 。然而，通过 String a = "hi"; String b = "hi"; 初始化的字符串都存储在字符串常量池中，它们指向同一个对象，因此也可以用 a == b 来比 较两个字符串的内容。
堆
应用场景
- 优先队列:堆通常作为实现优先队列的首选数据结构，其入队和出队操作的时间复杂度均为 𝑂(log 𝑛) ，而建队操作为 𝑂(𝑛) ，这些操作都非常高效。
- 堆排序:给定一组数据，我们可以用它们建立一个堆，然后不断地执行元素出堆操作，从而得到有序数 据。然而，我们通常会使用一种更优雅的方式实现堆排序，详见后续的堆排序章节。
- 获取最大的 𝑘 个元素:这是一个经典的算法问题，同时也是一种典型应用，例如选择热度前 10 的新闻 作为微博热搜，选取销量前 10 的商品等。
总结
- 堆的常用操作及其对应的时间复杂度包括:元素入堆 𝑂(log 𝑛)、堆顶元素出堆 𝑂(log 𝑛) 和访问堆顶
元素 𝑂(1) 等。
- 输入 𝑛 个元素并建堆的时间复杂度可以优化至 𝑂(𝑛) ，非常高效。
- Top‐K 是一个经典算法问题，可以使用堆数据结构高效解决，时间复杂度为 𝑂(𝑛 log 𝑘) 。
图
应用场景
ㅤ | 顶点 | 边 | 图计算问题 |
社交网络 | 用户 | 好友关系 | 潜在好友推荐 |
地铁线路 | 站点 | 站点间连通性 | 最短路线计算 |
天文系统 | 星体 | 星体间引力作用 | 行星轨道计算 |
总结
- 相较于线性关系(链表)和分治关系(树)，网络关系(图)具有更高的自由度，因而更为复杂。
- 当邻接表中的链表过长时，可以将其转换为红黑树或哈希表，从而提升查询效率。
- 从算法思想角度分析，邻接矩阵体现“以空间换时间”，邻接表体现“以时间换空间”。
- 图可用于建模各类现实系统，如社交网络、地铁线路等。
- 树是图的一种特例，树的遍历也是图的遍历的一种特例。
- 图的广度优先遍历是一种由近及远、层层扩张的搜索方式，通常借助队列实现。
- 图的深度优先遍历是一种优先走到底、无路可走时再回溯的搜索方式，常基于递归来实现。
路径的定义是顶点序列还是边序列?维基百科上不同语言版本的定义不一致:英文版是“路径是一个边序列”，而中文版是“路 径是一个顶点序列”。以下是英文版原文:In graph theory, a path in a graph is a finite or infinite sequence of edges which joins a sequence of vertices. 在本文中，路径被认为是 一个边序列，而不是一个顶点序列。这是因为两个顶点之间可能存在多条边连接，此时每条边都对应一条路径。
在邻接表中，“与该顶点相连的所有顶点”的顶点顺序是否有要求? 可以是任意顺序。但在实际应用中，可能会需要按照指定规则来排序，比如按照顶点添加的次 序、或者按照顶点值大小的顺序等等，这样可以有助于快速查找“带有某种极值”的顶点。
二、算法
搜索算法
「搜索算法 searching algorithm」用于在数据结构(例如数组、链表、树或图)中搜索一个或一组满足特定条件的元素。
搜索算法可根据实现思路分为以下两类。
- 通过遍历数据结构来定位目标元素，例如数组、链表、树和图的遍历等。
- 利用数据组织结构或数据包含的先验信息，实现高效元素查找，例如二分查找、哈希查找和二叉搜索树查找等。
「自适应搜索」
1. “二分查找”利用数据的有序性实现高效查找，仅适用于数组。
2. “哈希查找”利用哈希表将搜索数据和目标数据建立为键值对映射，从而实现查询操作。
3. “树查找”在特定的树结构(例如二叉搜索树)中，基于比较节点值来快速排除节点，从而定位目标元素。
搜索算法的选择还取决于数据体量、搜索性能要求、数据查询与更新频率等。
线性搜索
- 通用性较好，无须任何数据预处理操作。假如我们仅需查询一次数据，那么其他三种方法的数据预处理 的时间比线性搜索的时间还要更长。
- 适用于体量较小的数据，此情况下时间复杂度对效率影响较小。
- 适用于数据更新频率较高的场景，因为该方法不需要对数据进行任何额外维护。
二分查找
- 适用于大数据量的情况，效率表现稳定，最差时间复杂度为𝑂(log𝑛)。
- 数据量不能过大，因为存储数组需要连续的内存空间。
- 不适用于高频增删数据的场景，因为维护有序数组的开销较大。
哈希查找
- 适合对查询性能要求很高的场景，平均时间复杂度为 𝑂(1) 。
- 不适合需要有序数据或范围查找的场景，因为哈希表无法维护数据的有序性。
- 对哈希函数和哈希冲突处理策略的依赖性较高，具有较大的性能劣化风险。
- 不适合数据量过大的情况，因为哈希表需要额外空间来最大程度地减少冲突，从而提供良好的查询性能。
树查找
- 适用于海量数据，因为树节点在内存中是分散存储的。
- 适合需要维护有序数据或范围查找的场景。
- 在持续增删节点的过程中，二叉搜索树可能产生倾斜，时间复杂度劣化至 𝑂(𝑛) 。
- 若使用 AVL 树或红黑树，则各项操作可在 𝑂(log 𝑛) 效率下稳定运行，但维护树平衡的操作会增加额外开销。
总结
- ‧ 二分查找依赖于数据的有序性，通过循环逐步缩减一半搜索区间来实现查找。它要求输入数据有序，且 仅适用于数组或基于数组实现的数据结构。
- ‧ 暴力搜索通过遍历数据结构来定位数据。线性搜索适用于数组和链表，广度优先搜索和深度优先搜索 适用于图和树。此类算法通用性好，无须对数据预处理，但时间复杂度 𝑂(𝑛) 较高。
- ‧ 哈希查找、树查找和二分查找属于高效搜索方法，可在特定数据结构中快速定位目标元素。此类算法效 率高，时间复杂度可达 𝑂(log 𝑛) 甚至 𝑂(1) ，但通常需要借助额外数据结构。
- ‧ 实际中，我们需要对数据体量、搜索性能要求、数据查询和更新频率等因素进行具体分析，从而选择合 适的搜索方法。
- ‧ 线性搜索适用于小型或频繁更新的数据;二分查找适用于大型、排序的数据;哈希查找适合对查询效率 要求较高且无须范围查询的数据;树查找适用于需要维护顺序和支持范围查询的大型动态数据。
- ‧ 用哈希查找替换线性查找是一种常用的优化运行时间的策略，可将时间复杂度从 𝑂(𝑛) 降低至 𝑂(1) 。
排序
本人以往的一篇blog 已经详细说明了十大经典算法
排序算法的稳定性有什么实际意义？在现实中，我们有可能是在对象的某个属性上进行排序。例如，学生有姓名和身高两个属性， 我们希望实现一个多级排序/先按照姓名进行排序，得到 (A,180) (B,185) (C, 170) (D, 170);接下来对身高进行排序。由于排序算法不稳定，我们可能得到(D, 170) (C, 170)(A,180) (B,185) 可以发现，学生 D 和 C 的位置发生了交换，姓名的有序性被破坏了，而这是我们不希望看到 的。
快排中哨兵（pivot）划分中“从右往左查找”与“从左往右查找”的顺序可以交换吗?不行，当我们以最左端元素为基准数时，必须先“从右往左查找”再“从左往右查找”。这个 结论有些反直觉，我们来剖析一下原因。哨兵划分 partition() 的最后一步是交换 nums[left] 和 nums[i]。完成交换后，基准数左边的元素都 <= 基准数，这就要求最后一步交换前 nums[left] ≥ nums[i]必须成立，假设我们先“从左往右查找”，那么如果找不到比基准数更小的元素，则会在 i == j 时跳出循环，此时 可能 nums[j] == nums[i] > nums[left]。也就是说，此时最后一步交换操作会把一个比基准 数更大的元素交换至数组最左端，导致哨兵划分失败。 举个例子，给定数组 [0, 0, 0, 0, 1] ，如果先“从左向右查找”，哨兵划分后数组为 [1, 0, 0, 0, 0] ，这个结果是不正确的。 再深入思考一下，如果我们选择 nums[right] 为基准数，那么正好反过来，必须先“从左往右 查找”。
关于尾递归优化，为什么选短的数组能保证递归深度不超过 log 𝑛 ? 递归深度就是当前未返回的递归方法的数量。每轮哨兵划分我们将原数组划分为两个子数组。 在尾递归优化后，向下递归的子数组长度最大为原数组的一半长度。假设最差情况，一直为一 半长度，那么最终的递归深度就是 log 𝑛 。 回顾原始的快速排序，我们有可能会连续地递归长度较大的数组，最差情况下为 𝑛、𝑛 − 1、 ...、2、1 ，递归深度为 𝑛 。尾递归优化可以避免这种情况的出现。
分治
「分治 divide and conquer」，全称分而治之，是一种非常重要且常见的算法策略。分治通常基于递归实现，包括“分”和“治”两个步骤。
- 分(划分阶段):递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
- 治(合并阶段):从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。
归并排序就是分治策略的典型应用之一
一个问题是否适合使用分治解决，通常可以参考以下几个判断依据。
1. 问题可以被分解:原问题可以被分解成规模更小、类似的子问题，以及能够以相同方式递归地进行划分。
2. 子问题是独立的:子问题之间是没有重叠的，互相没有依赖，可以被独立解决。
3. 子问题的解可以被合并:原问题的解通过合并子问题的解得来。
显然，归并排序是满足以上三条判断依据的:
1. 问题可以被分解:递归地将数组(原问题)划分为两个子数组(子问题)。
2. 子问题是独立的:每个子数组都可以独立地进行排序(子问题可以独立进行求解)。
3. 子问题的解可以被合并:两个有序子数组(子问题的解)可以被合并为一个有序数组(原问题的解)。
并且，分治策略往往能提升效率（这点倒是有点反直觉），主要原因为 2 点：
- 操作数量降低
- 子策略可并行执行，从硬件层面实现优化
常见应用
一方面，分治可以用来解决许多经典算法问题。
- ‧ 寻找最近点对:该算法首先将点集分成两部分，然后分别找出两部分中的最近点对，最后再找出跨越两 部分的最近点对。
- ‧ 大整数乘法:例如 Karatsuba 算法，它是将大整数乘法分解为几个较小的整数的乘法和加法。
- ‧ 矩阵乘法:例如 Strassen 算法，它是将大矩阵乘法分解为多个小矩阵的乘法和加法。
- ‧ 汉诺塔问题:汉诺塔问题可以视为典型的分治策略，通过递归解决。
- ‧ 求解逆序对:在一个序列中，如果前面的数字大于后面的数字，那么这两个数字构成一个逆序对。求解逆序对问题可以通过分治的思想，借助归并排序进行求解。
另一方面，分治在算法和数据结构的设计中应用非常广泛。
- ‧ 二分查找:二分查找是将有序数组从中点索引分为两部分，然后根据目标值与中间元素值比较结果，决 定排除哪一半区间，然后在剩余区间执行相同的二分操作。
- ‧ 归并排序:文章开头已介绍，不再赘述。
- ‧ 快速排序:快速排序是选取一个基准值，然后把数组分为两个子数组，一个子数组的元素比基准值小，另一子数组的元素比基准值大，然后再对这两部分进行相同的划分操作，直至子数组只剩下一个元素。
- ‧ 桶排序:桶排序的基本思想是将数据分散到多个桶，然后对每个桶内的元素进行排序，最后将各个桶的元素依次取出，从而得到一个有序数组。
- ‧ 树:例如二叉搜索树、AVL 树、红黑树、B 树、B+ 树等，它们的查找、插入和删除等操作都可以视为
分治的应用。
- ‧ 堆:堆是一种特殊的完全二叉树，其各种操作，如插入、删除和堆化，实际上都隐含了分治的思想。
- ‧ 哈希表:虽然哈希表来并不直接应用分治，但某些哈希冲突解决策略间接应用了分治策略，例如，链式地址中的长链表会被转化为红黑树，以提升查询效率。 可以看出，分治是一种“润物细无声”的算法思想 ，隐含在各种算法与数据结构之中。
回溯（backtracking）
个人之前LC关于回溯总结
往往在全排列，以及岛屿涂色等可以用并查集方案的题目时可用回溯解决
总结
- ‧ 回溯算法本质是穷举法，通过对解空间进行深度优先遍历来寻找符合条件的解。在搜索过程中，遇到满足条件的解则记录，直至找到所有解或遍历完成后结束。
- ‧ 回溯算法的搜索过程包括尝试与回退两个部分。它通过深度优先搜索来尝试各种选择，当遇到不满足约束条件的情况时，则撤销上一步的选择，退回到之前的状态，并继续尝试其他选择。尝试与回退是两个方向相反的操作。
- ‧ 回溯问题通常包含多个约束条件，它们可用于实现剪枝操作。剪枝可以提前结束不必要的搜索分支，大幅提升搜索效率。
- ‧ 回溯算法主要可用于解决搜索问题和约束满足问题。组合优化问题虽然可以用回溯算法解决，但往往存在更高效率或更好效果的解法。
- ‧ 全排列问题旨在搜索给定集合的所有可能的排列。我们借助一个数组来记录每个元素是否被选择，剪枝掉重复选择同一元素的搜索分支，确保每个元素只被选择一次。
- ‧ 在全排列问题中，如果集合中存在重复元素，则最终结果会出现重复排列。我们需要约束相等元素在每轮中只能被选择一次，这通常借助一个哈希表来实现。
- ‧ 子集和问题的目标是在给定集合中找到和为目标值的所有子集。集合不区分元素顺序，而搜索过程会输出所有顺序的结果，产生重复子集。我们在回溯前将数据进行排序，并设置一个变量来指示每一轮的遍历起点，从而将生成重复子集的搜索分支进行剪枝。
- ‧ 对于子集和问题，数组中的相等元素会产生重复集合。我们利用数组已排序的前置条件，通过判断相邻元素是否相等实现剪枝，从而确保相等元素在每轮中只能被选中一次。
- ‧ 𝑛 皇后旨在寻找将 𝑛 个皇后放置到 𝑛 × 𝑛 尺寸棋盘上的方案，要求所有皇后两两之间无法攻击对方。该问题的约束条件有行约束、列约束、主对角线和副对角线约束。为满足行约束，我们采用按行放置的策略，保证每一行放置一个皇后。
- ‧ 列约束和对角线约束的处理方式类似。对于列约束，我们利用一个数组来记录每一列是否有皇后，从而 指示选中的格子是否合法。对于对角线约束，我们借助两个数组来分别记录该主、副对角线是否存在皇后;难点在于找处在到同一主(副)对角线上格子满足的行列索引规律。
递归
- 尾递归优化：函数最后一行，返回时再调用函数递归，能够被编译器等底层优化，节省函数栈上下文创建性能损耗
- 递归通常执行性能劣于迭代循环，但递归体现了
分治的思想：
本质上看，递归体现“将问题分解为更小子问题”的思维范式，这种分治策略是至关重要的。
- 从算法角度看，搜索、排序、回溯、分治、动态规划等许多重要算法策略都直接或间接地应用这种思维 方式。
- 从数据结构角度看，递归天然适合处理链表、树和图的相关问题，因为它们非常适合用分治思想进行分 析。
递归 vs 回溯？
回溯偏向于策略思想，递归偏向于工具方法
动态规划
谈及动规，少不了背包问题和爬楼梯问题，相关部分在本人早期 blog 中均有谈及：
本书也不例外，然后书里还额外提及了「编辑距离问题」
个人总结：
动态规划，本质上就是充分利用子问题局部解作为 memo，从而规避重复计算，提升效率。关键在于如何想出「状态转移方程」，这点在背包问题的 blog 中有详细讲解
本书总结：
• 子问题分解是一种通用的算法思路，在分治、动态规划、回溯中具有不同的性质。
• 动态规划问题的三大特性:重叠子问题、最优子结构、无后效性。
• 如果原问题的最优解可以从子问题的最优解构建得来，则它就具有最优子结构。
• 无后效性指对于一个状态，其未来发展只与该状态有关，与其所经历的过去的所有状态无关。许多组合优化问题都不具有无后效性，无法使用动态规划快速求解。
编辑距离问题
◦ ‧ 编辑距离(Levenshtein 距离)用于衡量两个字符串之间的相似度，其定义为从一个字符串到另一个字符串的最小编辑步数，编辑操作包括添加、删除、替换。
◦ ‧ 编辑距离问题的状态定义为将 𝑠 的前 𝑖 个字符更改为 𝑡 的前 𝑗 个字符所需的最少编辑步数。当𝑠[𝑖] ≠ 𝑡[𝑗] 时，具有三种决策:添加、删除、替换，它们都有相应的剩余子问题。据此便可以找出最优子结构与构建状态转移方程。而当 𝑠[𝑖] = 𝑡[𝑗] 时，无须编辑当前字符。
◦ ‧ 在编辑距离中，状态依赖于其正上方、正左方、左上方的状态，因此空间优化后正序或倒序遍历都无法正确地进行状态转移。为此，我们利用一个变量暂存左上方状态，从而转化到与完全背包等价的情况，可以在空间优化后进行正序遍历。
贪心
「贪心 VS 动规」
‧ 动态规划会根据之前阶段的所有决策来考虑当前决策，并使用过去子问题的解来构建当前子问题的解。
‧ 贪心算法不会重新考虑过去的决策，而是一路向前地进行贪心选择，不断缩小问题范围，直至问题被解决。
相较于动态规划，贪心算法的使用条件更加苛刻，其主要关注问题的两个性质。
‧ 贪心选择性质:只有当局部最优选择始终可以导致全局最优解时，贪心算法才能保证得到最优解。
‧ 最优子结构:原问题的最优解包含子问题的最优解。
对于某些复杂问题，贪心选择性质的证明并不简单。相对来说，证伪更加容易，例如零钱兑换问题。
贪心算法常常应用在满足贪心选择性质和最优子结构的优化问题中，以下列举了一些典型的贪心算法问题。
‧ 硬币找零问题:在某些硬币组合下，贪心算法总是可以得到最优解。
‧ 区间调度问题:假设你有一些任务，每个任务在一段时间内进行，你的目标是完成尽可能多的任务。如果每次都选择结束时间最早的任务，那么贪心算法就可以得到最优解。
‧ 分数背包问题:给定一组物品和一个载重量，你的目标是选择一组物品，使得总重量不超过载重量，且总价值最大。如果每次都选择性价比最高(价值 / 重量)的物品，那么贪心算法在一些情况下可以得到最优解。
‧ 股票买卖问题:给定一组股票的历史价格，你可以进行多次买卖，但如果你已经持有股票，那么在卖出之前不能再买，目标是获取最大利润。
‧ 霍夫曼编码:霍夫曼编码是一种用于无损数据压缩的贪心算法。通过构建霍夫曼树，每次选择出现频率 最小的两个节点合并，最后得到的霍夫曼树的带权路径长度(即编码长度)最小。
‧ Dijkstra 算法:它是一种解决给定源顶点到其余各顶点的最短路径问题的贪心算法。
- 分数背包问题在 0‐1 背包的基础上，允许选择物品的一部分，因此可使用贪心算法求解。贪心策略的正确性可以使用反证法来证明。
- 最大容量问题可使用穷举法求解，时间复杂度为 𝑂(𝑛2) 。通过设计贪心策略，每轮向内移动短板，可将时间复杂度优化至 𝑂(𝑛) 。
- 在最大切分乘积问题中，我们先后推理出两个贪心策略:≥ 4 的整数都应该继续切分、最优切分因子为 3 。代码中包含幂运算，时间复杂度取决于幂运算实现方法，通常为 𝑂(1) 或 𝑂(log 𝑛) 。
参考
《Hello-Algo》
- 作者:Tony
- 链接:https://wangqiwei.life/article/hello-algo-note
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。