数据结构与算法

基础

• 广义上的算法就是解决问题的方法，这是任何领域都需要考虑的问题，但是为什么只有信息领域如此强调呢？主要因为信息领域存在大量类似的问题，一个合适的算法优化可以带来极大的效用提高，相比之下，其它领域的问题缺少同质性。
• 程序设计=数据结构+算法。
• 算法的精髓：所有可以降低问题复杂度的算法都是在寻找一种划分，使得问题熵减。
  • 程序设计的三种基本结构：顺序结构、分支结构、循环结构。其中循环结构不会降低复杂度，因为它是用相同的策略来应对不同问题，而分支结构通过一定的划分，可以将问题（情况）分为不同的类，而不同的类有着更加明显的规律，可以用更加针对性的策略达到效果。
    • 二分：将情况分为两类，一类直接解决
    • 动态规划：通过一种解决顺序，可以将许多问题分到已经解决过的问题中
    • 回溯剪枝：通过判断，一类直接解决
• 计算机解决问题唯一的解决办法就是穷举，穷举所有可能性。算法设计就是先思考“如何穷举”，然后再追求“如何聪明地穷举”。或者说人也是如此。
  • 思考如何穷举就是证明问题是可以解决的，得到baseline方法；
  • 追求聪明的穷举就是通过加入先验知识，对各种情况特殊处理，降低计算成本。
• 实际的问题千千万万，我们不能记住所有具体的解决方案；但每个问题都可以抽象、分解为一些基本典型问题，只需要掌握这些基本问题的应对策略，就可以应对无穷的由基本问题组合而成的问题；这些基本问题也就是机器学习中的泛化特征。

问题思路

• 问题建模；
• 选择并描述算法；
• 证明算法是否能在所有实例上取得最优解；
• 分析算法效率。

算法要求

基础要求

• 正确性：零到多个输入，至少一个输出（广义上的输出）；
• 有穷性；
• 确定值；
• 可行性。

重要要求

• 可读性；
• 鲁棒性（能适应更加严苛、复杂的情况）；
• 时间空间复杂度低。

算法层次

• 没有语法错误；
• 对于合法输入能得到满足要求输出；
• 对于非法输入能够有合理应对；
• 对于故意刁难的输入可以得到满足要求的输出。

复杂度

时间复杂度
针对指定的基本运算和输入规模，算法所做运算的次数相对于输入规模的表达式。

• 基本运算应该满足：

  • 计算时间基本不变；
  • 在对应问题中其运算数量变化是影响运算时间的最主要因素。
  • 常见如：比较、加法、乘法、置指针、交换……
  • 常见的输入规模：数组元素多少、调度问题的任务个数、图的顶点数与边数……

• 复杂度中带$O(log(n))$的往往会用到二分或者类似二分的操作（树、堆）

• 复杂度中带$O(mn)$的往往需要for循环或动态规划计算

• 指数复杂度的场景往往输入规模极小，个位数量级

空间复杂度
针对指定的空间单位和输入规模，算法所需的空间量相对于输入规模的表达式。

时间复杂度和空间复杂度都是十分重要的，但是一般算法之间的空间复杂度差别远不及时间复杂度上的差别，因此更多比较的也是时间复杂度。

主定理

对于递推关系： $T(n)=aT(\frac{n}{b})+f(n),a>=1,b>1$
$n$为问题规模，$a$为子问题个数，$\frac{n}{b}$为子问题规模，$f(n)$为递归以外的计算工作。

$log_ba$与$f(n)$直接影响复杂度

情况一
当$O(f(n)) < O(n^{log_ba})$ 多项式地小于时：$O(n^{log_ba})$主导复杂度，$T(n)=O(n^{logb(a)})$

情况二
当$O(f(n)) > O(n^{log_ba})$ 多项式地大于时：$f(n)$主导复杂度，$T(n)=O(f(n))$

情况三
当$O(f(n)) = O(n^{log_ba}log^{k}n)$差距不足多项式时，共同影响复杂度，$T(n)=O(n^{log_ba}log^{k+1}n)$

注：部分复杂度符号使用粗略

遍历

• 广度优先：从一个节点开始，往外一层一层地拓展，第零层为起始节点，第一层为直接与起始节点相连的结点，第n层为直接与第n-1层相连但不属于前面任意一层地结点，直到遍历完所有节点。
• 深度优先：从第一个节点开始，随机查找下一个未被访问的节点，直到无法前进（走进死胡同），然后开始回退，一旦发现有未被访问的节点就继续前进，直到遍历所有节点。

递归

• 直接或间接调用自身的算法称为递归算法，必须有停止条件。
• 递归可以使得解决思路简洁、清晰；

缺点

• 有时候比较低效，经历大量的重算，可以用动态规划优化。
• 压入堆栈消耗更多空间

数据结构

逻辑结构和物理结构

• 数据结构分为逻辑结构和物理结构，逻辑结构是元素间的抽象关系，物理结构是元素在计算机上的存储方式。
• 数据物理结构：
  • 连续存储结构：在存储介质上连续存放，与逻辑结构的数组对应；
  • 非连续存储结构：数据元素存放在任意位置，通过指针（地址）联系；
• 数据逻辑结构分为：
  • 集合结构：元素间没有关系；
  • 线性结构：一个接一个的关系，更准确的说是按一定顺序先后排列的关系；
  • 树形结构：一对多关系；
  • 图形结构：多对多关系；

常用数据结构：数组、字符串、链表、栈、队列、双端队列、树、图……

基本数据结构：数组&链表

• 数组的优势在于查改，$O(1)$的时间实现访问、读写；缺点是增删时复杂度高；
• 链表的优势在于增删改，$O(1)$的时间实现插入和删除节点；缺点是查询时复杂度高，且随机访问对cache不友好；
• 数据长度确定，需要频繁读写时数组更合适，而数据长度不定，需要频繁改变时链表更有优势。
• 数组和链表的优缺点比较互补，所以很适合组合在一起，优势互补，得到各方面时间复杂度都低的数据结构，例如：哈希表、哈希表+链表等，想要实现更好的数据结构，一个思路就是组合不同数据结构的优势。

数据结构操作：增删改查=遍历+操作

• 数据结构分为（广义）线性和非线性；
• 操作的核心在遍历，遍历分为迭代和递归；
• 一般线性结构用迭代，非线性结构用递归；
• 递归本质上是通过堆栈实现，所以递归可以通过堆栈+迭代实现，这样可读性和实现难度往往不如迭代，但有时候问题较为清晰时可以改成迭代以降低空间消耗。

数组

特殊数组

• 前缀和数组：等于原数组的积分，适用于频繁使用数组一段区间大小的情况；
• 差分数组：等于数组的差分，适用于数组频繁对一段区间的值进行共同加减操作的情况；

常见题目

• 删除数组重复元素、删除数组指定元素、移动指定元素：双指针，快指针寻找元素，慢指针指示位置；
• 数组和为 k 的子数组：
  • 元素为正：
    • 左右指针滑窗：$O(n)$时间复杂度，遍历一次即可；
  • 任意元素：
    • 前缀和数组：空间$O(n^2)$，时间$O(n)$；
    • 哈希表代替前缀和数组，空间时间都是$O(n)$
• $O(1)$时间随机获得元素，要将元素紧凑的存在数组中；
• 查找缺失元素：长度为n的序列，包含0~n之间的数，每个数字出现一次，找到没有出现过的数；
  • 排序：时间$O(n*log(n))$，空间$O(1)$
  • 哈希表记录：时间$O(n)$，空间$O(n)$
  • 异或：时间$O(n)$，空间$O(1)$
  • 求和：时间$O(n)$，空间$O(1)$

字符串

字符串可以看成数组，区别在于当它以字符串形式出现时，不适合直接操作单个字符；但当以字符数组出现时可以，与数组几乎完全一致。
常见题型

• 规则判断：是否是回文、是否符合整数、能否转化为数值、能否转化为算式；
• 字符计数：哈希表、固定长度数组（字符数量有限）、滑动窗、无重复最长子串；
• 动态规划：最长公共（回文）子串（子序列）；

常见题目

• 二叉树匹配：判断一棵树是否是另一棵树的子结构
  • 暴力解法：递归地对匹配树的每一个结点，与模式树进行比较，复杂度$O(n*m)$。
  • 最佳解法：树的序列化+KMP算法，复杂度$O(n+m)$，将树变为字符串，然后进行字符串匹配，树的序列化要正确，具有唯一性，一对一映射。
• 两个字符串是否为变形词：使用哈希表或数组记录每个字符出现的次数进行比较，可以只用一个哈希表或数组记录其中一个的字符串的字符次数，然后遍历另一个字符串，做减法，遇到负数还可以提前结束。
• 两个字符串是否为旋转词：在长度相等的情况下，将一个字符串重复两次（这样包含了所有旋转词的情况），然后用KMP判断是否包含另外一个词，复杂度$O(n)$。
• 字符串单词逆序：
  • Python一行：split，翻转，拼接；额外空间
  • 两次翻转：遍历，对每个单词翻转；然后对整个字符串翻转，如果是字符数组时，不用额外空间。
• 字符串前后调换：
  • Python一行：额外空间
  • 两次翻转：同上
• 字符串数组字典排序：不能直接比较字符串的字典序，而要将两个字符串拼接比较，看哪个应该在前面。
• 字符串替换：将字符串中的字符替换成字符串，字符串会变长，可以先遍历一遍，看看有多少符合的字符，然后从后往前填充。
• 括号字符串是否有效：
  • 如果只有一种括号，可以遍历并记录左右括号的数量，空间复杂度$O(1)$；
  • 如果有多种括号，用栈，空间复杂度$O(n)$。
• 最长无重复子串：双指针遍历记录目前最长无重复子串，哈希表记录遍历元素最大位置，根据遍历元素位置调整指针。
• 字符串解析：可以用栈或更加方便地用递归；字符串括号等里面是独立的单元，可以调用递归；
• 保证相对顺序和字典序最小的字符串去重：贪心+单调栈；记录每个字符的出现次数，依次入栈，尽可能删除小字符前的字符，如果一个字符已经加进去了就不加；

链表

• 反转链表：
  • 迭代和递归都可以，迭代不需要额外空间，递归写起来简洁；
  • 迭代：从前往后遍历，存储几个必要节点，交换指向；
  • 递归：子函数实现递归，返回下一个节点反转后的头节点和尾节点；
• k个一组反转链表：边界判断 + 反转k个节点链表；
  • 迭代：从前往后遍历，有k个节点则调用子函数部分反转；
  • 递归：有k个子节点则调用子函数反转前面，调用自身处理后面，再整合；
• 反转部分链表：
  • 迭代：遍历至指定位置，执行指定数量反转；
  • 递归：传参数加入带反转的位置信息，以判断操作；
• 删除链表重复元素：有序链表直接遍历，无序用哈希表；

栈&队列

	栈	队列
进出	先进后出	先进先出
常用操作	pop、push、top/peak、size	pop、push、size
图搜索	深度优先	广度优先
编程结构	递归	迭代

栈

• 后进先出，因为操作都是在栈的顶部完成，且需要频繁改动，所以可以用单链表实现，各种操作都是$O(1)$时间。
• 如果用单链表实现栈，则入栈时单链表往头部方向扩展。
• 如果用数组来实现栈，当栈的长度超过数组长度时，运算复杂度不再是$O(1)$。
• 使用栈的场合往往是主要关注上一个操作的。

队列

• 先进先出，常用于顺序处理问题的场合，如：广度优先搜索。
• 双端队列可以利用双链表来实现，在队列的两端都用$O(1)$的时间进行查询、增加、删除。常用于长度动态变化的窗口或区间。
• 循环队列的一个好处是可以固定长度的数组实现。

单调栈

• 递减子数组数目；
• 滑窗最大值；
• 下一个更大元素；
• 下一个更大元素的距离（存储下标）
• 循环数组的下一个更大元素：让原数组重复一次；

常见题目

• 设计一个能够在$O(1)$时间复杂度返回最小元素的栈：可以设计一个额外记录最小值的栈，记录当前位置的最小值，额外空间复杂度$O(n)$；只在弹入值小于等于当前最小值时压入记录最小值的栈；
• 用两个栈实现队列：两个先进后出就可以得到先进先出，一个栈接收数据，一个栈倒出数据，但是从第一个往第二个倒的时候第二个栈必须是空的，且一次倒完。
• 栈的逆序：
  • 用递归函数实现：一个递归函数实现删除/弹出栈底元素，第二个递归函数调用第一个递归函数递归删除到最后后逆序压入，时间复杂度高；
  • 用队列实现：依次弹出栈元素，放入队列，从队列中取出压入栈；队列先进先出，而栈后进先出的特性带来了逆序。
• 用一个额外的栈实现栈中元素排序：原理就是让元素倒来倒去，让元素有序；原理类似于插入排序。
• 数组取划窗最大值：双端队列，存放元素下标，压入的时候比较，去掉不符合的，同时从一端获得最大元素的下标。

树

• 完全二叉树适合数组存储
• 可视为一个拥有N 个节点和N-1 条边的一个有向无环图。

遍历

• 一般采用递归的方法遍历比较清晰，二叉树遍历分为：前序遍历、中序遍历、后序遍历
• 树的遍历得到的结果并非一一对应，不同的树可以得到相同的遍历结果。
• 很多问题一旦写成递归形式都可以看成树的遍历，快排-前序遍历、归并排序-后序遍历、回溯-决策树DFS遍历
• 二叉树相关的题大多可以通过写成递归遍历的形式快速解决；

  /* 二叉树遍历框架 */
  def traverse(root):
      // 前序遍历
      traverse(root.left)
      // 中序遍历
      traverse(root.right)
      // 后序遍历

常见题目

• 反转二叉树、二叉树展开为链表、求二叉树高度
• 通过列表、前中后序遍历重构二叉树
• 寻找重复子树：后序遍历+序列化+哈希
• 二叉树的节点数：
  • 任意二叉树：遍历+计数，$O(n)$；
  • 满二叉树：找深度，$O(log(n))$：
  • 完全二叉树：判断+用任意二叉树和满二叉树的方式，$O(log(n)*log(n))$；
• 二叉树最长路径：状态是每一个节点的优化值，子问题是子节点的优化值。

哈希表

• 一种使用哈希函数组织数据，以支持快速插入和搜索的数据结构。
• 哈希+大数组[+链表]

堆

• 完全二叉树（适合数组存储）；
• 每个节点的值大于等于（小于等于）子树的值。

堆删除元素是弹出堆顶元素，将末尾元素放到堆顶，然后从上往下堆化；堆插入元素是将待插入元素放置在堆末尾，然后从下往上堆化。

堆排序VS快速排序

• 快排顺序遍历，对cache更加友好，堆排序随机访问，对cache不友好；
• 堆排序会打乱原有顺序，增加逆序度，因此实际中的交换次数可能更多。

堆的应用

• 求最值，排序；
• 合并多个有序序列；
• 高性能定时器，获取需要执行的任务，不需要反复轮询；
• 求topk大元素，只需要建一个大小为k的小根堆，每次新来元素同堆顶元素比较，如果大于堆顶元素就替换，否则不操作；
• 动态求中位数，一个大顶堆存小元素和一个小顶堆存大元素，保持两个堆元素数量平衡，即可快速，动态得到中位数。

图

基本概念

• 图可以用邻接矩阵、邻接表来表示。
• 无向图：$G=(V,E)$,V表示结点，数量为n，E表示边，数量为m。
• 有向图：图$G=(V,E)$的边是带有方向的，如网页超链接。
• 路径（path）：无向图$G=(V,E)$中的路径定义为由一系列结点构成的序列，其中两个连续结点之间有一条边。
• 简单路径：所有节点都是不相同的。
• 连通无向图：任意两个结点之间存在一条路径。
• 圈/环：有且只有首尾为相同结点的路径。
• 有向无环图：不包含有向环的有向图。
• 树是连通且不包含圈/环的无向图。
• 对于有n个结点的无向图，这三条中任意两条可以作为树的定义并推导出第三条：连通，边数为$n-1$，没有圈。
• 二部图/二分图：如果一个无向图的结点用红蓝两种颜色区分，可以使得每条边的两个结点一个是红色一个是蓝色。
  • 如果一个无向图不包含奇圈，那就是二部图。
  • 广度优先遍历的结果中不包含连接同一层结点的边的无向图是二部图。
• 如果有向图两个结点之间相互可达，这两个结点是强连通的，如果有向图中所有结点是相互可达的，则此图是强连通的。
  • 任意一个结点与其它结点相互可达，这个图就是强联通的。
  • 判断方式：取一个点作为根节点做广度优先，边的方向反向再做广度优先，如果两次都可以到达所有点，则此图是强联通的。

遍历

• 广度优先遍历中，通过一条边连接起来的两个结点的层数最多相差一层。

Trie

• 前缀树就是将字符串按照前缀整合起来，形成一棵树，插入和遍历的过程都是从树的根节点向下遍历的过程；
• 前缀树每一个节点存储元素通过哈希方式记录；因为每个节点记录单个元素，所以可以通过比较容易的方式实现哈希，如果只有英文字符可以使用ASCII码关系进行对应；
• 优势：
  • 适合前缀匹配场景，如搜索匹配、自动补全等；
  • 可以快速在大量字符串中插入、查询、匹配、计数等等
• 缺点：
  • 如果查询的字符集过大，会使得存储空间浪费；
  • 如果字符串前缀重合度小，也会造成空间浪费；
  • 指针对缓存不友好

AC自动机

• 快速在主串中查找字符串，适合敏感词过滤场景；
• AC自动机-Trie树=KMP-BF
• KMP通过next数组记录匹配失败时指针跳转的位置，AC自动机通过失败指针记录匹配失败时跳转的位置，一般效率极高；

组合结构

经典题目

• LRU：缓存满时删除最旧的，快速查找需要用到哈希，时间排序用到（双向）链表；
• LFU：缓存满时删除访问频率最低的中最旧的，快速查找、记录每个缓存的访问次数、每个访问次数对应的缓存以及对应顺序的LRU需要用到3/4个哈希，每一个访问次数内用双向链表记录顺序；
• 平均$O(1)$时间插入，删除，随机返回一个元素：随机返回可以用数组+随机数实现，插入删除可以将被删元素移到数组结尾，用哈希表记录元素索引；

算法思想

算法	最优子结构	无后效性	重复子问题	最优化
回溯	Y	Y	N
动态规划	Y	Y	Y	Y
贪心	Y	Y		Y
分治	Y		N
	通过子问题的最优解，推导出问题的最优解，分治思想	某阶段状态只取决于前面的的状态	不同决策序列有重复问题	从多个解中寻找最优解

贪心

• 贪心就是每次用局部最优的选择；
• 许多问题可以设计策略，使得通过连续的局部最优解最终得到全局最优解；可以通过贪心得到全局最优解的问题往往可以在一定程度上对前后问题解耦；

霍夫曼编码

• 问题：如何用尽量少的空间编码字符；
• 思路：不同字符出现的频率不同，可以用尽量短的编码来编码高频字符，以及用到的编码不作为其他字符编码的前缀，如此总的编码数量在加权平均后会减少；

计算机的cache-内存-外存设计

• 问题：如何用尽量少的成本获得尽量高的性能；
• 思路：将最高频的计算放在少量的cache中，经常的计算放在内存中，不经常的大量计算放在外存中，使得计算效率接近cache，成本接近外存；

常见问题

• 分糖果：m个糖果和n个孩子,m < n，糖果的大小分别是s1，s2，s3，……，sm。孩子对糖果大小的需求分别是g1，g2，g3，……，gn。如何分配能尽可能满足最多数量的孩子：
  • 优先分配需求小的孩子，优先用小糖果
• 钱币找零：有不同面额的货币，如何用尽量少的数量找钱：
  • 先用面额大的货币，当每一个大额货币是任意小额货币的整数倍时，为全局最优，否则不一定；
• 区间覆盖：n个区间，选出一部分区间，满足两两不相交，最多能选出多少个区间呢：
  • 优化的是最大化区间数量，按照区间右边界排序，先选择结束早的区间；
  • 任务调度、排课问题等；
• 区间覆盖：n个区间，组成新的序列，满足两两不相交，最少需要多少个序列才能满足呢：
  • 优化的是最小序列数量，每一个区间最终都要被选择，则选择的过程就是要让区间尽量紧凑；
  • 按照左边界排序，依次安排各个会议的会议室；先从现有的会议室中找最早结束的，如果不满足则开辟新的会议室；会议室放在堆中，堆顶是最早结束的会议室；

分治

• 分治是将问题划分为规模更小地子问题，递归或迭代地求解子问题，再将子问题的解合并得到原问题的解。
  • 要求：子问题与原问题的性质完全一样、最小的子问题可以直接求解、子问题之间可以独立求解，独立是分治与动态规划的一个明显区别。
• 分治的常见场景：二分法（每次问题规模减半）、二分归并排序；
  • 似乎分治的效果都是将一个n的复杂度变成了$log(n)$

MapReduce

• 每一个Maper完成部分数据的处理，Reducer则完成数据的聚合，大部分时候并不需要聚合成一个文件，因此也可以用多个Reducer。

常见应用

• 幂乘可以二分进行，从线性复杂度转化为对数复杂度；
• 斐波拉切数列求解可以转化成幂乘问题，然后用分治化简。
• 归并排序、快速排序
• 快排思想选k大/小
• 几乎各种存在有序线性搜索的地方都可以改为二分；

动态规划

基本思想

• 基本思路：穷举+备忘录
  • 穷举是为了比较所有可能的情况，每一个问题可以由一系列小问题的答案组合而成，一般是$max(dp[小1],dp[小2],…)$。
  • 备忘录是通过记录子问题的结果，避免重复计算，用空间换时间，降低时间复杂度
• 重点是穷举过程的转移方程，也就是将原问题转化为更简单的子问题的转移关系，一定要正确
  • 正确得到穷举的转移方程需要明确问题的变量（自由度），最后的问题就变成了多维（自由度）数组的元素填充问题。
• 穷举方向可以是自顶向下的递归，也可以是自底向上的迭代
• 一个优化角度是穷举顺序，合适的穷举顺序可以少使用备忘录，降低空间复杂度
• 对于有指数种情况的问题:要么是可以用动态规划来求解;要么就只能应用在输入规模极小的场景；或者可以在回溯中大量剪枝。

通用框架

# 自底向上
dp = ...
for 状态1 in 状态1取值:
    for 状态2 in 状态2取值:
        for ...:
            dp[状态1][状态2][...] = 择优(选择1,选择2,...)
# 自顶向下
memory = ...
def dp(状态1,状态2,...):
    if 状态1,状态2,... not in memory:
        memory[状态1][状态2][...] = 择优(dp(选择1),dp(选择2),dp(...))
    return memory[状态1][状态2][...]

常见题目

• 凑零钱问题：状态是总的钱数，子问题是减去可能的零钱后的钱数，优化的是最少零钱数；
• 0-1背包问题：状态是背包容量与待装物品，子问题是某个物品装与不装后的背包容量和剩下的待装物品，优化的是总价值；
• 股票买卖：状态是每一天的买卖情况、第几次买卖等，子问题是前一天或前几天的状态，优化的是最终收益。
• 最小路径和：状态是二维平面上每一个点的最小路径，子问题是前面点的最小路径，优化的是目的地的最小路径。
• 编辑距离：状态是两个字符串的子串的编辑距离，子问题是通过几种可选择的操作可以得到的子问题，优化的是编辑距离。
• 最长公共子序列：状态是两个字符串的子串的最长公共子序列，子问题是减掉一两个字符串最后一个字符得到的。
• 最长回文子序列：状态是字符串的子串的最长回文子序列，子问题是从左右两端减掉一两个字符后的最长回文子序列。
• 最长上升子序列：状态是索引，子问题是每个位置前所有元素中，包括这个位置的最长上升子序列。
• 得分数组左右取分，预测赢家，状态是剩下数字的起始和结束位置；
• 为运算表达式设计优先级：子问题是一段表达式可能的优先级；

回溯

基本思想

• 回溯就是一个决策树的DFS深度优先搜索过程；
• 基本思路：决策遍历+停止判断；
• 做决策的过程就是向子节点递归的过程，回退的时候需要撤销选择回到原来的状态，或者说回到对应节点的状态；
• 动态规划和回溯都有递归+DFS搜索：
  • 动态规划一定有重叠子问题，而回溯没有。某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用备忘录优化，将递归树大幅剪枝，这就变成了动态规划。
  • 动态规划有求最值的过程，将子问题的结果整合成一个，而回溯是记录所有满足的结果（也可能是找到一个满足的）
  • 动态规划是返回到最顶层后得到结果，而回溯是递归到最底层得到结果。
• 有时候适当调整选择顺序可以降低最坏复杂度。

通用框架

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

1. 路径：也就是已经做出的选择。
2. 选择列表：也就是当前可以做的选择。
3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

常见题目

• n皇后：每行一个皇后，所以选择列表就是每一行的皇后的列数，选择的时候判断是否冲突；
• 全排列：每一步从剩下的选择中选择；
• m个元素平分成k个元素和相同的子集：决策深度为元素数m，每个元素有k种选择，每个集合的最终总和是确定的，用于判断是否合适；
  • 可以先对元素进行排序，优先选择较大的元素，更容易触发停止条件，以减小计算量。
  • 也可以从桶的角度，先选择桶，再选择元素放不放，各个桶之间的状态相对独立一些，可以把最坏复杂度从$O(k^m)$降到$O(k*2^m)$。
• 求子集：每一个元素加或不加是选择，没有中间的剪枝，所以也可以不用模版直接迭代；
• 求组合：按顺序依次取，每一个元素加或不加是选择，当元素数量达到指定数量时停止；
• 求排列：不按顺序取，每一个元素加或不加是选择，当元素数量达到指定数量时停止；
• 括号组合：每次加一种（左右，大小）括号进去，判断是否不合法；
  • 如果是只有一种括号可以直接用数字记录括号数量是否合法，或者迭代生成；
  • 如果有多种括号，需要用栈来判断是否合法；
• 有向无环图求所有可能路径：
  • DFS回溯：
  • BFS：

双指针

双指针可分为快慢指针、左右指针、滑窗等。

快慢指针

• 判断链表是否有环：慢指针一次走一步，快指针一次走两步，如果相交则有环，快指针走到头则无环；
• 找链表环的起始点：找到环后，一个指针从起点开始，一个从相遇点开始，各一次走一步，在环的起始点相遇；
• 两个链表是否相交：两个指针分别从两个链表开始走，到头则换到另一个链表开始，如果中间指向同一节点则相交；
• 找链表中点：慢指针一次走一步，快指针一次走两步，快指针到头时，慢指针为中点；
• 找倒数第k个节点：快指针先走k个节点，快指针到头时，去慢指针；
• 删除数组重复元素、删除数组指定元素、移动指定元素：快指针寻找元素，慢指针指示位置；

左右指针

• 二分查找：两个指针控制搜索区间，每次区间减半；
  • 每一次二分都要保证：搜索区间减小，正确处理边界
  • 不要用else，而是把所有情况用 else if写清楚
• 有序数组两数之和：左右边界开始往中间找；
• 反转数组；

滑动窗口
通过一定规则，判断是让前指针走还是后指针走，在遍历的过程中记录答案；

• 数组和为k的子数组：$O(n)$时间复杂度，遍历一次即可；
• 最小覆盖子串：前指针往前走，找到覆盖子串，然后后指针往前走，找最小的覆盖子串；
• 字符串排列/异位词子串：前指针往前走，找到排列子串，遇到不在子串的字符或者超过的字符就移动后指针，缩减窗口；
• 无重复最长子串：哈希表记录位置，遍历判断是否需要更新起始位置；

BFS

BFS 相对 DFS 的最主要的区别是：BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多

经典问题

• 最短路径：
  • 图上最短路径适合BFS搜索，
  • 数组上的最短路径适合用动态规划的方式；但是如果数组上加入了许多约束，如蛇梯棋，也适合BFS
• 找解决方案：变相求最短路径，通过几种可选的策略BFS搜索，直到找到解决方案。

经典问题

排序问题

时间复杂度

• 时间复杂度为$O(n^2)$的排序算法有：冒泡排序、选择排序、插入排序

  这些排序算法是很直观的做法，但效率都比较低，随着元素数量增加，计算代价迅速增加，有优化的空间。例如这些算法在执行的时候，原数组会开始变得有序，这种有序就可以加以利用，进而降低复杂度，也就有了$O(nlog(n))$的算法。进一步如果待排序元素的种类/个数是有限的，还可以利用桶进一步降低复杂度。

• 时间复杂度为$O(nlog(n))$的排序算法有：快速排序、归并排序、堆排序、希尔排序
• 时间复杂度为$O(n+k)$的排序算法有：计数排序、基数排序

冒泡排序

• 自然界中，在重力作用下密度小的物体有向上运动的趋势，而密度大的物体有向下运动的趋势，也就是自然存在依密度排列的趋势。
  • 冒泡排序的思路就是这么朴素，让元素按大小自然沉浮。
  • 对于长度为$n$的数组，循环$n-1$次，每次都让剩下元素中最大的元素沉下去（当然可以让最小的浮上来）。

选择排序

• 同样对于长度为n的数组，循环$n-1$次，每次遍历剩下元素，把最大（最小）地元素提取出来。
• 与冒泡排序类似，不同的是冒泡每次比较发现逆序都会交换元素，而选择排序会记录当前的最大值的位置。

插入排序

• 对于长度为$n$的数组，循环$n-1$次，每次从剩下元素取第一个往有序部分线性插入。
• 选择排序是在取的时候得到有序，而插入排序是在放的时候得到有序。
• 在数组是由链表构成时，如果插入的时候不是线性插入，而是二分插入（数组不能二分插，还是要搬运各个元素，链表可以借助跳表），可以将复杂度降到$O(nlog(n))$

快速排序

• 利用二分和分治的思想，大约循环$log(n)$层，每次将原数组划分成两个无序部分，但是其中一个部分都大于另一个部分。
• 可以看成是一种特殊的冒泡排序，所有元素跟相同的元素比较，使得每次比较一遍可以让所有元素都沉或浮。
• 还可以看成是一种前序遍历，根节点完成划分，两个子节点完成子数组的排序；
• 快排每次划分不一定是在中间，需要记住划分位置，所以空间复杂度为$O(log(n))-O(n)$，如果用递归，空间复杂度就是递归深度，如果是迭代做，空间复杂度就是记住划分位置。

  def partition(arr, low, high):
      i, j = low, low 
      pivot = arr[high] # 取最后一个元素当做pivot
      while j < high:
          # 当前元素小于或等于 pivot
          if arr[j] < pivot:
              arr[i], arr[j] = arr[j], arr[i]
              i += 1 #pivot位置前进1步
          j += 1
      arr[i], arr[high] = arr[high], arr[i] #将pivot放到正确的位置并返回位置索引i
      return i
  # 快速排序函数
  def quick_sort(arr, low, high):
      if low < high:
          pi = partition(arr, low, high)
          quick_sort(arr, low, pi - 1)
          quick_sort(arr, pi + 1, high)
   
  arr = [1,10,2,7, 8, 9,1, 5]
  # arr = [1,1,1,1,1]
  quick_sort(arr, 0, len(arr)-1)
  print(arr)

归并排序

• 利用分治的思想，将问题划分为更小的子问题，$问题数量的增长+额外代价 < 问题复杂度的减小$时就可以降低复杂度。
  • 这里随着分治的进行，问题数量指数增加，问题复杂度指数减小，但是问题复杂度减小地更快。
  • 空间复杂度$O(n)$
• 也可以看成后序遍历，子节点完成前后两部分的排序，根节点完成合并。

堆排序

• 利用最大/小堆，每次弹出最大/小值，可以看成是一种优化的选择排序。
• 建立堆的过程复杂度为$O(n)$：不同结点需要比较的次数不一样，但平均不超过2。

希尔排序

• 当原数组是非常有序时，插入排序的复杂度极低，可以接近$O(n)$。希尔排序是一种改良的插入排序，先通过较大的步长尽可能减少逆序，降低插入的代价。
• 复杂度与步长选择有关，当原数组较为有序时可以考虑小一些的步长；当步长不合适时复杂度会增加至$O(n^2)$。
• 当数据量过大时，希尔排序容易低效，更适合数据量小的时候。

计数排序

• 当排序数组的元素取值为有限值时，可以根据可能的取值构建桶，将元素按值放入桶中，对桶中的元素计数，得到元素的顺序，是一种在特殊情况下以空间换时间的方式。

基数排序

• 在元素取值为有限位时，从低位到高位，每次对其中一位进行排序。
• 两种桶排序的空间复杂度跟桶的数量有关。

常见题目

基本有序数组排序
基本有序数组：每个元素跟最终有序位置距离不超过k。
在这种特殊情况下，能够将一些排序算法的时间复杂度再降一降.
插入排序$O(n*k)$：每个元素最多比较$k$次。
改进堆排序$O(nlog(k))$：每次只需要取前$k$个元素建立堆，不过可能要使用额外空间建堆，不能像原来一样在原地操作。

判断是否有重复元素
空间复杂度$O(n)$：哈希表。
空间复杂度$O(1)$：非递归堆排序

两个有序数组合并
链表就直接按序比较
如果是数组，其中一个数组后面有多余空间时，则从空的位置开始放。

荷兰国旗问题

• 问题：将只包含0,1,2三种数的无序数组排有序
• 用三个指针，两个指向0和2，一个遍历，将0和2往两边甩，类似于快排。
• 也可以直接对0，1，2三种元素计数，然后改写即可；

行列有序二维数组查找
右上开始，至左下，$O(n+m)$

需要排序最短子数组
从左向右、从右往左遍历，记录边界（小于最大数的右边界，大于最小数的左边界），也就是找到两边不用排序的部分，留下中间存在逆序的部分。

无序数组排序后的最大差值
通过$n$个桶，平均划分区间，将元素放入这些桶中，按序遍历查找。

拓扑排序

• 定义：对有向无环图的节点进行排序，使得排序结果符合边方向

Kahn算法

• 将入度为0的节点选择出来，并去掉对应的出边；
• 反复循环至取出所有节点。

DFS解法

• 循环对每个节点调用DFS深度优先搜索遍历
• 在遍历中对节点的上级节点进行DFS，最后打印自己
• 因此每个节点都是在所有上级节点遍历完成后才打印的。

字符串匹配

BF、RK、BM、KMP、Trie树、AC自动机
BF
时间复杂度很高$O(m*n)$，但也很常用，因为：

• 大多数时候主串和匹配串的长度都不大；
• 大多数时候会较早遇到不匹配的情况然后停止；
• 实现简单不容易出错。

RK

• 通过设计合适的哈希算法，将复杂度降低到$O(n)$；
• 没有散列冲突的哈希算法可能会整形溢出，可以允许有一定的冲突，平衡空间与时间

BM
实验统计，BM的性能是著名的KMP算法的3到4倍

KMP算法

• KMP算法相对于单纯的滑动比较，主要改进在于发现最长公共前后缀在冲突时的作用，进而通过动态规划的方式避免重复劳动，降低复杂度。
• 在比较冲突的时候，已经比较配对的部分中匹配串与模式串是相同的，因此接下来的滑动相当于是已匹配部分自己与自己比较，即寻找最长公共前后缀。
• 最长公共前后缀与模式串的字符位置对应，因此记录最长公共前后缀信息的数组就是next数组，也是动态规划中的Memory。
• 计算next数组的过程就是动态规划的过程，当连续匹配时next数组可以依次写出，当出现不匹配时直接调用以计算出的部分即可。
• 所以KMP算法是一种动态规划的实现，以空间换时间，用next数组记录运算信息，避免重复子问题。

m数之和

• 排序+左右指针：
  • m=2：排序，左右指针从两边向中间移动，复杂度$O(nlog(n))$；
  • m>2：排序，从第一个数的取值开始循环，每一层循环m降低一，最后调用两数之和，左右指针从两边向中间移动，复杂度$O(n^{m-1})$；
• 哈希+遍历比较：哈希计算并记录m//2数之和的可能性，然后遍历并记录，最坏的时间复杂度$O(n^{m//2+1})$，实际可能更低；

查并集

问题
有$n$个节点，节点之间有$m$对关系，找到节点直接的圈子

暴力解法
将一对有关系的节点放到一个集合中，若存在两个集合，则对集合进行合并。

高效解法

• 对于新的关系，寻找两个节点是否有公共祖先，没有则合并，将一个祖先的祖先设置为另一个祖先，找祖先的代码：

  def find(x):
      if nums[x] != x:
          nums[x] = find(nums[x])
      return nums[x]

• 合并的时候将简单的树合并到复杂的树上，以尽量控制树的深度。

  def merge(x,y):
      if rank[x] < rank[y]:
          x, y = y, x
      rank[x] = rank[x] + rank[y]
      nums[y] = x

发糖果

• 问题：给一个列表，是孩子的评分，给孩子发糖果，要保证评分高的孩子得到的糖果数比两边评分低的孩子多
• 解决：左右各遍历一次，记录给每个孩子最少的糖果，取最大值。

蓄水池采样

• 问题：数据流式到达，总数$n$未知，从中采样$k$个，保证每个数据被采样的概率都是$\frac{k}{n}$；
• 解决：前$k$个数据直接保存，第$m$个数据到达时，以$\frac{k}{m}$的概率替代当前保留数据，使得所有数据等概率；

素数数量

• 统计区间$[2,n)$的素数个数,外循环从小到大寻找素数，内循环将其倍数标注为非素数；
• 外循环只需要遍历到$\sqrt n$的位置，内循环只需要从$i^2$开始遍历；

  def count_primes(n):
      is_primes = [True for _ in range(n)]
      for i in range(2, int(n**0.5)+1):
          if is_primes[i]:
              for j in range(i**2, n, i):
                  is_primes[j] = False
      return sum(is_primes)-2

阶乘后面的0

• 任意一个数的阶乘，后面有多少个0，其实是看有多少个2,5组合，2远多于5，所以只看5

  def trailingZeroes(n):
      zero_count = 0
      while n > 0:
          n //= 5
          zero_count += n
      return zero_count

• 有k个0的阶乘有多少个，在上一个问题的基础上，通过二分查找确定边界，然后定位；

取模问题

• 当问题规模较大时，可能出现溢出的情况或有其它要求，希望结果取模；
• 考虑到性质：$(a * b)\%k=(a\%k)*(b\%k)\%k$，可以将取模运算放在计算前，以避免溢出；

智力题

概率问题

男孩女孩

• 有一个家庭，有两个孩子：
  • 其中有一个男孩，问另一个也是男孩的概率；两个孩子有男男、男女、女男、女女四种情况；其中一个是男孩，则只剩3种情况，另一个是男孩的概率为$\frac{1}{3}$
  • 第一个是男孩，问第二个也是男孩的概率；独立，概率为$\frac{1}{2}$

生日相同

• 需要有多少人，才能使得存在至少两个人生日是同一天的概率达到50%；
• 概率为：$1-\frac{365!}{(365-n)!365^n}$，
• 即要求$2*365!<(365-n)!365^n$，答案是23

三门问题

• 三扇门，两个后面是山羊，一个后面是跑车，选手先选一个门，然后主持人打开一个是山羊的门，此时选手可以选择是否换门；
• 不换拿到跑车的概率是$\frac{1}{3}$，换拿到跑车的概率是$\frac{2}{3}$；

选择题排除

• 4个选项，先蒙A，然后发现B、C一定不对，是否要换D；
• 不换正确的概率是$\frac{1}{4}$，换正确的概率是$\frac{3}{4}$；

电灯开关

• 有n盏电灯，最开始时都是关着的，第k轮每k个电灯按一次，最后有多少灯是开着的；
• 大部分序号都可以分解成成对的因子，因此灯会被开关偶数次，最后是关着灯，而可以被整数开平方的灯会被按奇数次，最后会开着；
• 因此结果是$int(sqrt(n))$

价值选择/石头游戏

左右选择一个

• 一排偶数堆石头，两个人依次从中选择，只能从最左边或最右边选择；
• 先手一定赢，因为先手可以控制自己选择奇数堆还是偶数堆；

顺序选择多个

• 一排东西，两个人依次选择，可以选择多个，取到最后一个的人赢；
• 根据可以选择的个数循环，一定赢或一定输；