Leetcode---图解算法与数据结构

最近因为可能要后面去考虑找实习，因此又重新拾起来一些算法与数据结构的知识。由于之前主要写c++，但自从搞上GS-SLAM和NeRF-SLAM后，主要的编程语言也从c++转为了python，从代码实现上确实python没有像c++那样要考虑很多边界和数据结构的问题，因此这次主要是写python相关的一些代码和知识，也希望后面自己在看或者再用的时候能有一些收获。（本文主要内容来自于leetbook算法与数据结构）

数据结构简介#

常见的数据结构可分为「线性数据结构」与「非线性数据结构」，具体为：「数组」、「链表」、「栈」、「队列」、「树」、「图」、「散列表」、「堆」。

数组 python中一般就是可变数组了 直接[]进行初始化，并利用append方法来添加相应的元素

链表 链表以节点为单位，每个元素都是一个独立对象，在内存空间的存储是非连续的。链表的节点对象具有两个成员变量：「值 val」，「后继节点引用 next」 。

class ListNode:
    def __init__(self, x):
        self.val = x     # 节点值
        self.next = None # 后继节点引用

## 实例化节点
n1 = ListNode(4) # 节点 head
n2 = ListNode(5)
n3 = ListNode(1)

## 构建引用指向
n1.next = n2
n2.next = n3

建立此链表需要实例化每个节点，并构建各节点的引用指向。python中应该是从左到右表示一个饮用指向，感觉不用像c++一样考虑一些数据结构的一些问题

栈与队列 栈：「先入后出」，python中可将列表当作栈使用，python中的入栈和出栈的相关操作分别对应append()方法和pop()方法

stack = [] # Python 可将列表作为栈使用

stack.append(1) # 元素 1 入栈
stack.append(2) # 元素 2 入栈
stack.pop()     # 出栈 -> 元素 2
stack.pop()     # 出栈 -> 元素 1

队列：「先入先出」，python中通常使用双端队列，deque，入队和出队操作分别对应append()方法和popleft()方法，这里是双端队列，所以可以控制出口，为了满足先入先出，调用的是popleft()方法。

## Python 通常使用双端队列 collections.deque
from collections import deque

queue = deque()

queue.append(1) # 元素 1 入队
queue.append(2) # 元素 2 入队
queue.popleft() # 出队 -> 元素 1
queue.popleft() # 出队 -> 元素 2

树

树是一种非线性数据结构，根据子节点数量可分为 「二叉树」 和 「多叉树」，最顶层的节点称为「根节点 root」。以二叉树为例，每个节点包含三个成员变量：「值 val」、「左子节点 left」、「右子节点 right」

class TreeNode:
    def __init__(self, x):
        self.val = x      # 节点值
        self.left = None  # 左子节点
        self.right = None # 右子节点

## 初始化节点
n1 = TreeNode(3) # 根节点 root
n2 = TreeNode(4)
n3 = TreeNode(5)
n4 = TreeNode(1)
n5 = TreeNode(2)

## 构建引用指向
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5

想要使用树结构也是要初始化每个节点，并指明其连接关系，比如从根节点开始的左子节点和对应的右子节点，同样也是遵从从左向右的指向原则

图

图是一种非线性数据结构，由「节点（顶点）vertex」和「边 edge」组成，每条边连接一对顶点。根据边的方向有无，图可分为「有向图」和「无向图」。本文 以无向图为例 开展介绍。

如下图所示，此无向图的 顶点 和 边 集合分别为：

顶点集合： vertices = {1, 2, 3, 4, 5} 边集合： edges = {(1, 2), (1, 3), (1, 4), (1, 5), (2, 4), (3, 5), (4, 5)}

表示法通常有两种，分别是邻接矩阵和邻接表，

• 邻接矩阵使用数组vertices 存储顶点，邻接矩阵 edges 存储边；edges[i][j] 代表节点 i+1 和 节点 j+1 之间是否有边。
• 邻接表使用数组vertices存储顶点，邻接表edges存储边。 edges 为一个二维容器，第一维i代表顶点索引，第二维edges[i]存储此顶点对应的边集和；例如edges[0]=[1,2,3,4] 代表vertices[0] 的边集合为 [1,2,3,4] 。

## 邻接矩阵
vertices = [1, 2, 3, 4, 5]
edges = [[0, 1, 1, 1, 1],
         [1, 0, 0, 1, 0],
         [1, 0, 0, 0, 1],
         [1, 1, 0, 0, 1],
         [1, 0, 1, 1, 0]]


## 邻接表

vertices = [1, 2, 3, 4, 5]
edges = [[1, 2, 3, 4],
         [0, 3],
         [0, 4],
         [0, 1, 4],
         [0, 2, 3]]

邻接矩阵的大小只与节点数量有关，即$N^2$，其中 N 为节点数量。因此，当边数量明显少于节点数量时，使用邻接矩阵存储图会造成较大的内存浪费。 因此，邻接表适合存储稀疏图（顶点较多、边较少）； 邻接矩阵适合存储稠密图（顶点较少、边较多）。

散列表

散列表是一种非线性数据结构，通过利用 Hash 函数将指定的「键 key」映射至对应的「值 value」，以实现高效的元素查找。字典应该是一种比较常用的散列表

实际的 Hash 函数需保证低碰撞率、 高鲁棒性等，以适用于各类数据和场景。

堆

堆是一种基于「完全二叉树」的数据结构，可使用数组实现。以堆为原理的排序算法称为「堆排序」，基于堆实现的数据结构为「优先队列」。堆分为「大顶堆」和「小顶堆」，大（小）顶堆：任意节点的值不大于（小于）其父节点的值。

完全二叉树定义： 设二叉树深度为k，若二叉树除第k层外的其它各层（第1至k−1 层）的节点达到最大个数，且处于第k层的节点都连续集中在最左边，则称此二叉树为完全二叉树。

如下图所示，为包含 1, 4, 2, 6, 8 元素的小顶堆。将堆（完全二叉树）中的结点按层编号，即可映射到右边的数组存储形式。python 看来有专门的堆数据结构heap，元素入堆要按照索引的顺序，方法为heappush()，元素出堆会自带一个排序?这里有点奇怪，可能要再查查

from heapq import heappush, heappop

## 初始化小顶堆
heap = []

## 元素入堆
heappush(heap, 1)
heappush(heap, 4)
heappush(heap, 2)
heappush(heap, 6)
heappush(heap, 8)

## 元素出堆（从小到大）
heappop(heap) # -> 1
heappop(heap) # -> 2
heappop(heap) # -> 4
heappop(heap) # -> 6
heappop(heap) # -> 8

算法复杂度#

算法复杂度旨在计算在输入数据量N的情况下，算法的「时间使用」和「空间使用」情况；体现算法运行使用的时间和空间随「数据大小 N 」而增大的速度。

算法复杂度主要可从 时间 、空间 两个角度评价：

时间： 假设各操作的运行时间为固定常数，统计算法运行的「计算操作的数量」 ，以代表算法运行所需时间； 时间复杂度 空间： 统计在最差情况下，算法运行所需使用的「最大空间」；空间复杂度

时间复杂度 时间复杂度指输入数据大小为N时，算法运行所需花费的时间。需要注意

• 统计的是算法的「计算操作数量」，而不是「运行的绝对时间」。计算操作数量和运行绝对时间呈正相关关系，并不相等。算法运行时间受到「编程语言 、计算机处理器速度、运行环境」等多种因素影响。例如，同样的算法使用 Python 或 C++ 实现、使用 CPU 或 GPU 、使用本地 IDE 或力扣平台提交，运行时间都不同。
• 体现的是计算操作随数据大小N变化时的变化情况。假设算法运行总共需要「1 次操作」、「100 次操作」，此两情况的时间复杂度都为常数级O(1) ；需要「N 次操作」、「100N 次操作」的时间复杂度都为O(N) 。
• 根据输入数据的特点，时间复杂度具有「最差」、「平均」、「最佳」三种情况，分别使用 O , Θ , Ω 三种符号表示。一般默认的情况是O，也就是最差的情况
• 一个常见的算法复杂度的顺序为：$O(1)<O(logN)<O(N)<O(NlogN)<O(N ^2)<O(2^N)<O(N!)$

常数O(1) 运行次数与 N 大小呈常数关系，即不随输入数据大小 N 的变化而变化。基本上要么是与N无关，要么就是一种返回常数的一个简单计算

线性O(N) 循环运行次数与N大小呈线性关系，时间复杂度为O(N) 。

平方$O(N^2)$ 两层循环相互独立，都与N呈线性关系，因此总体与N呈平方关系，时间复杂度为$O(N^2)$。冒泡排序的总的时间复杂度是$O(N^2)$

指数$O(2^N)$ 生物学科中的 “细胞分裂” 即是指数级增长。初始状态为1个细胞，分裂一轮后为2 个，分裂两轮后为4个，……，分裂N轮后有$2^N$个细胞。

算法中，指数阶常出现于递归，两层的递归会有这样的指数阶复杂度

阶乘$O(N!)$ 阶乘阶对应数学上常见的 “全排列” 。即给定 N 个互不重复的元素，求其所有可能的排列方案，则方案数量为：$N*(N-1)* (N-2)*(N-3) * 2 *1 = N!$

对数O(logN) 对数阶与指数阶相反，指数阶为 “每轮分裂出两倍的情况” ，而对数阶是 “每轮排除一半的情况” 。对数阶常出现于「二分法」、「分治」等算法中，体现着 “一分为二” 或 “一分为多” 的算法思想。

注意对数复杂度与这里的分成多少份，即log中的这个底a无关，因为这里总可以把其转化为以2为底的log操作，而对应的乘积项为常数项，常数项可以认为是O(1)因此还是O(logN)的时间复杂度。

线性对数O(NlogN) 线性对数阶常出现于排序算法，例如「快速排序」、「归并排序」、「堆排序」等，其时间复杂度原理如下图所示。

空间复杂度 空间复杂度涉及的空间类型有：

• 输入空间： 存储输入数据所需的空间大小；
• 暂存空间： 算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；
• 输出空间： 算法运行返回时，存储输出数据所需的空间大小；

通常情况下，空间复杂度指在输入数据大小为N时，算法运行所使用的「暂存空间」+「输出空间」的总体大小。

而根据不同来源，算法使用的内存空间分为三类：

• 指令空间：编译后，程序指令所使用的内存空间。
• 数据空间：算法中的各项变量使用的空间，包括：声明的常量、变量、动态数组、动态对象等使用的内存空间。
• 栈帧空间：程序调用函数是基于栈实现的，函数在调用期间，占用常量大小的栈帧空间，直至返回后释放

算法中，栈帧空间的累计常出现于递归调用。因为相当于上一次的结构可能要将递归当中的结果累积，因此不能直接释放，要等所有结果返回了，当前的函数才能被释放。

常见种类 根据从小到大排列，常见的算法空间复杂度有：$O(1)<O(logN)<O(N)<O(N ^2)<O(2^N)$

常数O(1) 普通常量、变量、对象、元素数量与输入数据大小N无关的集合，皆使用常数大小的空间。

线性O(N) 元素数量与N呈线性关系的任意类型集合（常见于一维数组、链表、哈希表等），皆使用线性大小的空间

平方$O(N^2)$ 元素数量与N呈平方关系的任意类型集合（常见于矩阵），皆使用平方大小的空间。

指数$O(2^N)$ 指数阶常见于二叉树、多叉树。例如，高度为 N 的「满二叉树」的节点数量为$2^N$, 占用$O(2^N)$大小的空间；同理，高度为N的「m满二叉树」的节点数量为$m^N$,

对数$O(logN)$ 对数阶常出现于分治算法的栈帧空间累计、数据类型转换等, 例如：

• 快速排序, 平均空间复杂度为 $\Theta(\log N)$, 最差空间复杂度为 $O(N)$ 。拓展知识：通过应用 尾递归优化，可以将快速排序的最差空间复杂度限定至 $O(N)$ 。
• 数字转化为字符串, 设某正整数为 $N$, 则字符串的空间复杂度为 $O(\log N)$ 。推导如下: 正整数 $N$ 的位数为 $\log _{10} N$, 即转化的字符串长度为 $\log _{10} N$, 因此空间复杂度为 $O(\log N)$ 。

链表部分解题思路:#

双指针方法(一个指向head，一个指向None)，或者是快慢指针方法(都指向head)似乎是解决链表问题的一个比较好的方式。

字符串部分的注意事项#

split()的时候，多个空格当成一个空格；split(’ ‘)的时候，多个空格都要分割，每个空格分割出来空。如果只是像分割并取出空格，可以用split()方法

strip()函数也蛮好用的，可以用于去除字符串开头和结尾的空格，从而有效的对直接的字符串进行读取

ord()函数可以得到该字符的ascci码，这样可以更方便的处理数字的字符转数字等问题，这里可能会比较常用

' '.join(res) 这段 Python 代码的含义是将一个列表(res)或任何可迭代的序列（其中的元素必须是字符串）中的元素合并成一个单一的字符串。这里的 ’ ’ 是一个空格，它被用作连接各个元素的分隔符。 ''.join(res) 同样也可以用这种方法将res列表中的字符串进行拼接，直接得到一个更长的字符串

栈和队列的注意事项#

栈(列表)的删除操作 在python中栈是通过列表的方式来进行实现的，对于list，添加元素的操作是append(),由于和栈很像，因此通过pop()方法可以弹出最后一个元素，但需要注意的是如果list为空则pop操作会报错。

同时对于list列表来说，我们也可以通过remove(“元素”)函数来删除列表中的元素，而如果list当中有多个重复的元素，则由于list的一个元素访问的性质，他会从栈底开始进行查找，删除第一个找到的list中的元素。同样如果元素不在list中也会报错。

同样也可以通过pop的方式来对列表中的元素进行删除，列表名.pop(索引)，这里的索引的顺序也是从栈底到栈顶的顺序，同时pop操作是可以返回这个删除的变量的。如果索引不存在，则依旧会报错

同样也可以采用切片的方式来对列表中的元素进行删除，例如: 列表名[起始索引:结束索引] = []

用双栈的方式可以得到队列的类似的效果。

.sort()方法是对原有的元素进行直接的操作，而sorted(List)函数是将List排序之后的结果返回，可以用变量来进行存储

.reverse()方法是对原有的元素进行直接的操作，而reversed(List)函数是将List反转之后的迭代器返回，需要注意的是这里并不是直接放回反转的列表，因此需要配合list(reversed(List))语句来将其转换为列表

bisect高效的得到有序插入数据(不能用于乱序和逆序列表) 在插入数据的过程中，如果想要高效的得到一个有序的序列，可以用bisect模块中的函数快速完成，这里的插入时基于二分法来进行插入的，这个模块主要包含两个基础功能：bisect_left 和 bisect_right（又名 bisect），以及两个辅助的插入函数 insort_left 和 insort_right。默认的列表时递增的。需要注意：bisect.insort 只能在递增列表中插入新元素，即不能用于乱序和逆向列表。一般情况下默认用left方法

1. bisect_left bisect_left 函数查找指定元素应插入列表的位置(返回下标)，以保持列表的有序性，并且在列表中已存在相等元素时，插入点会在这些元素的前面（左侧）。

import bisect

a = [1, 2, 4, 4, 5]
x = 4
index = bisect.bisect_left(a, x)
print(index)  # 输出 2

2. bisect_right 或 bisect bisect_right（或简称为 bisect，因为 bisect 实际上是 bisect_right 的别名）也是查找元素应当插入的位置（返回下标），区别在于，如果存在相等的元素，插入点会在这些元素的后面（右侧）。

index = bisect.bisect_right(a, x)
print(index)  # 输出 4

3. insort_left insort_left 直接在适当位置插入元素，以保持列表顺序，遇到相同的元素，会将其插入到元素的左侧(前面)。

bisect.insort_left(a, 3)
print(a)  # 输出 [1, 2, 3, 4, 4, 5]

4. insort_right 或 insort insort_right 也是用来插入元素，遇到相同的元素，会将其插入到元素的右侧(后面)。

bisect.insort_right(a, 4)
print(a)  # 输出 [1, 2, 4, 4, 4, 5]

数结构的注意事项#

树当中的一个很重要的应用就是有关于二叉树的层次遍历，主要采用的方式就是BFS(广度优先搜索)，就是把每一层的节点全部便利一遍，知道最后得到完整的树形结构。BFS的核心是要构造一个队列，利用队列先入先出的方式来对树结构的每个节点按照从做到右的方式进行便利，下面是一个简单的例子：

class Solution:
    def decorateRecord(self, root: TreeNode) -> List[int]:
        if not root: 
            return []
        res, queue = [], collections.deque()
        queue.append(root)
        while queue:
            # 这里利用了队列先入先出的特性
            node = queue.popleft()
            res.append(node.val)
            if node.left: 
                queue.append(node.left)
            if node.right: 
                queue.append(node.right)
        return res

判断两个二叉树是否相等可以递归的去做。

python中的一个三目运算符的一个写法

max = a if a>b else b

二叉搜索树的概念 在二叉搜索树中：

• 若任意结点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值。
• 若任意结点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值。
• 任意结点的左、右子树也分别为二叉搜索树

二叉搜索树的中序遍历为递增序列。根据此性质，易得二叉搜索树的 中序遍历倒序 为 递减序列。可以利用这个性质来判断这个树是不是二叉搜索树，只需要中序遍历对应的节点的访问的值是递增的。

class Solution:
    # 类变量为所有共享
    pre = -inf
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 二叉搜索树的中序遍历是递增的
        if not root:
            return True
        
        # 递归左
        if not self.isValidBST(root.left):
            return False

        # 根
        if root.val <= self.pre:
            return False
        self.pre = root.val

        # 如果有问题值会直接回弹过来的
        return self.isValidBST(root.right)

树的遍历 树的遍历方式总体分为两类：

• 深度优先搜索（DFS）： 先序遍历(根左右)、中序遍历(左根右)、后序遍历(左右根)；
• 广度优先搜索（BFS）： 层序遍历；

对于深度搜索和广度优先搜索，可以分为递归法和非递归法(如果采用非递归法就要采用辅助栈的方式)，其中递归函数在计算机中实现隐式的利用了被称为调用栈的栈，即递归利用了栈，只是隐式的利用了栈，没有显示的让你看到其使用了栈。以先序遍历为例，利用一个辅助栈，来进行访问结点并入栈遍历左子树，结点出栈遍历右子树。中序遍历，结点入栈访问结点的左子树，出栈访问结点，并且遍历结点的右子树。

后序遍历感觉还挺重要的！

树中递归部分的一些理解

排序算法#

排序算法用作实现列表的排序，列表元素可以是整数，也可以是浮点数、字符串等其他数据类型。生活中有许多需要排序算法的场景，例如：

• 整数排序： 对于一个整数数组，我们希望将所有数字从小到大排序；
• 字符串排序： 对于一个姓名列表，我们希望将所有单词按照字符先后排序；
• 自定义排序： 对于任意一个 已定义比较规则 的集合，我们希望将其按规则排序；

同时，某些算法需要在排序算法的基础上使用（即在排序数组上运行），例如：

• 二分查找： 根据数组已排序的特性，才能每轮确定排除两部分中的哪一部分；
• 双指针： 例如合并两个排序链表，根据已排序特性，才能通过双指针移动在线性时间内将其合并为一个排序链表。

常见算法 常见排序算法包括「冒泡排序」、「插入排序」、「选择排序」、「快速排序」、「归并排序」、「堆排序」、「基数排序」、「桶排ss序」。如下图所示，为各排序算法的核心特性与时空复杂度总结。

分类方法 排序算法主要可根据稳定性 、就地性 、自适应性 分类。理想的排序算法具有以下特性：

• 具有稳定性，即相等元素的相对位置不变化；
• 具有就地性，即不使用额外的辅助空间；
• 具有自适应性，即时间复杂度受元素分布影响；

特别地，任意排序算法都不同时具有以上所有特性 。因此，排序算法的选型使用取决于具体的列表类型、元素数量、元素分布情况等应用场景特点。

稳定性: 根据相等元素在数组中的相对顺序是否被改变，排序算法可分为「稳定排序」和「非稳定排序」两类。

• 稳定排序」在完成排序后不改变相等元素在数组中的相对顺序。例如：冒泡排序、插入排序、归并排序、基数排序、桶排序。
• 「非稳定排序」在完成排序后，相等素在数组中的相对位置可能被改变。例如：选择排序、快速排序、堆排序。

数组排序中，由于元素皆为数字，因此稳定和非稳定排序皆可输出相同结果，此时无需考虑排序算法的稳定性。当我们排序的是一个具有一定属性的要素时，当采用非稳定排序就很容易出现某一个相对关系被破坏，比如按照年龄排序，但姓名排序会被破坏。

就地性： 根据排序过程中是否使用额外内存（辅助数组），排序算法可分为「原地排序」和「异地排序」两类。一般地，由于不使用外部内存，原地排序相比非原地排序的执行效率更高。

• 「原地排序」不使用额外辅助数组，例如：冒泡排序、插入排序、选择排序、快速排序、堆排序。
• 「非原地排序」使用额外辅助数组，例如：归并排序、基数排序、桶排序。

自适应性： 根据算法时间复杂度是否受待排序数组的元素分布影响，排序算法可分为「自适应排序」和「非自适应排序」两类。

• 「自适应排序」的时间复杂度受元素分布影响；例如：冒泡排序、插入排序、快速排序、桶排序。
• 「非自适应排序」的时间复杂度恒定；例如：选择排序、归并排序、堆排序、基数排序。

是否基于比较： 比较类排序基于元素之间的比较算子（小于、相等、大于）来决定元素的相对顺序；相对的，非比较排序则不基于比较算子实现。

• 「基于比较排序」基于元素之间的比较完成排序，例如：冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序。
• 「非基于比较排序」不基于元素之间的比较完成排序，例如：基数排序、桶排序。

时空复杂度 总体上看，排序算法追求时间与空间复杂度最低。而即使某些排序算法的时间复杂度相等，但实际性能还受输入列表性质、元素数量、元素分布等等因素影响。

设输入列表元素数量为 N ，常见排序算法的「时间复杂度」和「空间复杂度」如下图所示。

对于上表，需要特别注意：

• 「基数排序」适用于正整数、字符串、特定格式的浮点数排序， k 为最大数字的位数；「桶排序」中 k 为桶的数量。
• 普通「冒泡排序」的最佳时间复杂度为$O(N^2)$，通过增加标志位实现提前返回，可以将最佳时间复杂度降低至$O(N)$ 。
• 在输入列表完全倒序下，普通「快速排序」的空间复杂度劣化至$O(N)$，通过代码优化 尾递归优化保持算法递归较短子数组，可以将最差递归深度降低至$logN$。
• 普通「快速排序」总以最左或最右元素为基准数，因此在输入列表有序或倒序下，时间复杂度劣化至$O(N^2)$；通过随机选择基准数，可极大减少此类最差情况发生，尽可能地保持$O(NlogN)$的时间复杂度。
• 若输入列表是数组，则归并排序的空间复杂度为$O(N)$；而若排序链表，则「归并排序」不需要借助额外辅助空间，空间复杂度可以降低至$O(1)$ 。

冒泡排序 冒泡排序是最基础的排序算法，由于其直观性，经常作为首个介绍的排序算法。其原理为：

• 内循环： 使用相邻双指针 j , j + 1 从左至右遍历，依次比较相邻元素大小，若左元素大于右元素则将它们交换；遍历完成时，最大元素会被交换至数组最右边 。
• 外循环： 不断重复「内循环」，每轮将当前最大元素交换至 剩余未排序数组最右边 ，直至所有元素都被交换至正确位置时结束。

如下图所示，冒泡排序的「外循环」共 N−1 轮，每轮「内循环」都将当前最大元素交换至数组最右边，从而完成对整个数组的排序。

def bubble_sort(nums):
    N = len(nums)
    for i in range(N - 1):           # 外循环
        for j in range(N - i - 1):   # 内循环
            if nums[j] > nums[j + 1]:
                # 交换 nums[j], nums[j + 1]
                nums[j], nums[j + 1] = nums[j + 1], nums[j]

算法特性：

• 时间复杂度$O(N^2)$
  • 最佳 Ω(N) ： 普通冒泡排序的时间复杂度恒为$O(N^2)$，对于近似排序数组，通过加入标志位可实现提前返回, 在内循环中如果不发生交换，则提前终止，对于已经拍好的序列可以做到O(N)
  • 平均与最差$O(N^2)$ 「外循环」共 N−1 轮，使用 O(N) 时间；每轮「内循环」分别遍历N−1 , N−2 , ⋯⋯ , 2 , 1 次，平均$N/2$次，使用$O(N/2)=O(N)$时间，因此总的时间复杂度是$O(N^2)$
• 空间复杂度 O(1)： 只需原地交换元素，使用常数大小的额外空间。
• 冒泡排序是通过不断交换元素实现排序（交换 2 个元素需要 3 次赋值操作），因此速度较慢；
• 原地： 指针变量仅使用常数大小额外空间，空间复杂度为$O(1)$；
• 稳定： 元素值相同时不交换，因此不会改变相同元素的相对位置；
• 自适应： 通过增加一个标志位 flag ，若某轮内循环未执行任何交换操作时，说明已经完成排序，因此直接返回。此优化使冒泡排序的最优时间复杂度达到$O(N)$（当输入数组已排序时）；

快速排序(非常经典，算是考察的比较多了) 快速排序算法有两个核心点，分别为哨兵划分和递归。

哨兵划分：以数组某个元素（一般选取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。

递归：对左子数组和右子数组分别递归执行哨兵划分，直至子数组长度为 1 时终止递归，即可完成对整个数组的排序。

## 快排递归调用
def quick_sort(nums, l, r):
    # 子数组长度为 1 时终止递归
    if l >= r: return
    # 哨兵划分操作
    i = partition(nums, l, r)
    # 递归左（右）子数组执行哨兵划分
    quick_sort(nums, l, i - 1)
    quick_sort(nums, i + 1, r)

## 获取划分位置    
def partition(nums, l, r):
    # 以 nums[l] 作为基准数
    i, j = l, r
    while i < j:
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[l], nums[i] = nums[i], nums[l]
    return i

## 调用
nums = [3, 4, 1, 5, 2]
quick_sort(nums, 0, len(nums) - 1)

算法特性：

• 时间复杂度
  • 最佳 Ω(NlogN)： 最佳情况下， 每轮哨兵划分操作将数组划分为等长度的两个子数组；哨兵划分操作为线性时间复杂度$O(N)$,递归的总轮数为$O(logN)$
  • 平均Θ(NlogN)： 对于随机输入数组，哨兵划分操作的递归轮数也为O(logN) 。
  • 最差$O(N^2)$:「对于某些特殊输入数组，每轮哨兵划分操作都将长度为 N 的数组划分为长度为 1 和 N−1 的两个子数组，此时递归轮数达到 N 。

通过 「随机选择基准数」优化，可尽可能避免出现最差情况，详情请见下文。

• 空间复杂度O(N)： 快速排序的递归深度最好与平均皆为logN ；输入数组完全倒序下，达到最差递归深度N 。
• 虽然平均时间复杂度与「归并排序」和「堆排序」一致，但在实际使用中快速排序 效率更高，这是因为：
  • 最差情况稀疏性： 虽然快速排序的最差时间复杂度为$O(N^2)$，差于归并排序和堆排序，但统计意义上看，这种情况出现的机率很低。大部分情况下，快速排序以 O(NlogN) 复杂度运行。
  • 缓存使用效率高： 哨兵划分操作时，将整个子数组加载入缓存中，访问元素效率很高；堆排序需要跳跃式访问元素，因此不具有此特性。
  • 常数系数低： 在提及的三种算法中，快速排序的比较、赋值、交换三种操作的综合耗时最低（类似于插入排序快于冒泡排序的原理）。
  • 原地： 不用借助辅助数组的额外空间，递归仅使用 O(logN) 大小的栈帧空间。
  • 非稳定： 哨兵划分操作可能改变相等元素的相对顺序。
  • 自适应： 对于极少输入数据，每轮哨兵划分操作都将长度为 N 的数组划分为长度 1 和 N−1 两个子数组，此时时间复杂度劣化至$O(N^2)$。

优化： 随机基准数： 同样地，由于快速排序每轮选取「子数组最左元素」作为「基准数」，因此在输入数组完全有序或完全倒序时， partition()每轮只划分一个元素，达到最差时间复杂度$O(N^2)$。

因此，可使用随机函数，每轮在子数组中随机选择一个元素作为基准数，这样就可以极大概率避免以上劣化情况。

值得注意的是，由于仍然可能出现最差情况，因此快速排序的最差时间复杂度仍为$O(N^2)$ 。

def partition(nums, l, r):
    # 在闭区间 [l, r] 随机选取任意索引，并与 nums[l] 交换
    ra = random.randrange(l, r + 1)
    # 随机选择一个基准，并交换到最左侧
    nums[l], nums[ra] = nums[ra], nums[l]
    # 以 nums[l] 作为基准数
    i, j = l, r
    while i < j:
        while i < j and nums[j] >= nums[l]: j -= 1
        while i < j and nums[i] <= nums[l]: i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[l], nums[i] = nums[i], nums[l]
    return i

归并排序 归并排序体现了 “分而治之” 的算法思想，具体为：

• 「分」： 不断将数组从中点位置划分开，将原数组的排序问题转化为子数组的排序问题；
• 「治」： 划分到子数组长度为 1 时，开始向上合并，不断将 左右两个较短排序数组 合并为 一个较长排序数组，直至合并至原数组时完成排序

如下图所示，为数组 [7,3,2,6,0,1,5,4] 的归并排序过程。

算法流程：

1. 递归划分：
   1. 计算数组的中点m，递归的来对数组进行划分，划分为左子树组merge_sort(l,m)和右子树组merge_sort(m+1, r),l和r分别是左右的端点
   2. 当$l>=r$时，则说明两个指针重合了，因此子数组的长度为0或1，此时终止划分，开始进行合并操作
2. 合并子数组
   1. 暂存数组$nums$闭区间[l,r]内的元素到辅助数组tmp
   2. 循环合并：设置双指针i和j，分别指向tmp的左/右数组的首元素：

   nums 子数组的左边界、中点、右边界分别为 l , m , r ，而辅助数组 tmp 中的对应索引为 0 , m−l , r−l ；

   • 当i==m−l+1时： 代表左子数组已合并完，因此添加右子数组元素tmp[j] ，并执行 j=j+1
   • 否则，当j==r−l+1时： 代表右子数组已合并完，因此添加左子数组元素tmp[i]，并执行i=i+1 ；
   • 否则，当tmp[i]≤tmp[j]时： 添加左子数组元素tmp[i] ，并执行i=i+1 ；
   • 否则（即当tmp[i]>tmp[j]时）： 添加右子数组元素tmp[j] ，并执行j=j+1 ；

查找类相关题型#

需要注意的是，Python3.6及之后的版本Python字典的输出是有序的（按插入的顺序），这里下标访问这里仍然是无序的，采用items()方法可以使其输出是按照输入的顺序来进行。

排序数组中的搜索问题，首先想到 二分法 解决。主要的思想是将其通过条件转换为变成左右两个数组的问题，之后在通过二分搜索来得到左右指针停止搜索的一个边界。感觉二分搜索比较适合得到一个有序数组的一个什么边界这样的问题。

感觉对于有序数组的这个二分查找这里还得在练一练，有的时候用二分查找并不是一个很好的方式，尤其是对于一个非单调的序列的时候，其边界和临界条件会很多，就很容易出错

回溯相关题型#

常用的回溯一般是递归回溯，一般指用深度优先搜索来探索解空间，感觉先用递归判断往深了去搜索，在用回溯的方式来对不满足条件的，或者搜索的尽头进行回退，直至所有的状态全部探索玩的一种算法。

这块题感觉还是缺少一些思想的东西，先把一些深度优先，广度优先和回溯问题的一些思想看了。。。

B站上灵神对回溯问题进行了划分，分为了子集型回溯，组合型回溯和排列型回溯等。子集型回溯：每个元素都可以选或者不选。

判断回文串的技巧: 一个比较便捷的做法，直接将列表逆序，看了两者是否相同 s[::-1] == s

深度优先搜索专项#

遍历元素最常见的两种方法是深度优先搜索(DFS)和广度优先搜索(BFS)，遍历也称为穷举，穷举的思想在人类看来虽然很不起眼，但借助 计算机强大的计算能力，穷举可以帮助我们解决很多专业领域知识不能解决的问题。

「遍历」和「搜索」可以看作是两个的等价概念，通过遍历 所有 的可能的情况达到搜索的目的。遍历是手段，搜索是目的

树的深度优先遍历 二叉树的深度优先遍历还可以分为：前序遍历、中序遍历和后序遍历。

1. 前序遍历 对于任意一棵子树，先输出根结点，再递归输出左子树的所有结点、最后递归输出右子树的所有结点
2. 中序遍历 对于任意一棵子树，先递归输出左子树的 所有 结点，然后输出根结点，最后递归输出右子树的 所有 结点。这里的根节点一定是在中间的
3. 后序遍历（重要） 对于任意一棵子树，总是先递归输出左子树的 所有 结点，然后递归输出右子树的 所有 结点，最后输出根结点。后序遍历体现的思想是：先必需得到左右子树的结果，才能得到当前子树的结果，这一点在解决一些问题的过程中非常有用。自下而上的信息的传递的反馈？？？

后序遍历是非常重要的遍历方式，解决很多树的问题都采用了后序遍历的思想，请大家务必重点理解「后序遍历」一层一层向上传递信息的遍历方式。并在做题的过程中仔细体会「后序遍历」思想的应用。

根据定义不难得到以下重要性质。 性质 1：二叉树的前序遍历序列，根结点一定是最先访问到的结点； 性质 2：二叉树的后序遍历序列，根结点一定是最后访问到的结点； 性质 3：根结点把二叉树的中序遍历序列划分成两个部分，第一部分的所有结点构成了根结点的左子树，第二部分的所有结点构成了根结点的右子树。

深度优先遍历有「回头」的过程，在树中由于不存在「环」（回路），对于每一个结点来说，每一个结点只会被递归处理一次。而「图」中由于存在「环」（回路），就需要 记录已经被递归处理的结点（通常使用布尔数组或者哈希表），以免结点被重复遍历到。

数据结构-栈 在深度优先遍历的过程中，需要将 当前遍历到的结点 的相邻结点 暂时保存 起来，以便在回退的时候可以继续访问它们。遍历到的结点的顺序呈现「后进先出」的特点，因此 深度优先遍历可以通过「栈」实现。

再者，深度优先遍历有明显的递归结构。我们知道支持递归实现的数据结构也是栈。因此实现深度优先遍历有以下两种方式：

• 编写递归方法；
• 编写栈，通过迭代的方式实现。

重要心得 一般来说，递归和回溯是一起使用的，递归的下面的部分就是回溯，只不过有些利用了回溯去做事情，有些并没有用回溯去做事情。

回溯常解决的问题有：组合问题（强调没有顺序），切割问题（字串，回文子串之类），子集问题，排列问题（强调元素的顺序），棋盘问题（）。回溯法是可以抽象成一个树形结构的

树相关的基础概念 树的几个概念：满二叉树，完全二叉树（需要注意完全二叉树的底部从左到右一定是连续的），二叉搜索树（左子树上所有结点的值均不大于它的根结点，右子树上的所有节点均不小于它的根节点。二叉搜索树对于节点布局没要求，对于节点顺序是有要求的），平衡二叉搜索树（任何结点的左子树和右子树高度最多相差1，C++中的set，map，multimap，multiset都是用这种方式做底层实现，插入和查询都是logn级别的）

树的存储方式：顺序存储（对于完全二叉树可以通过2*i+1和2*i+2的方式访问左右节点）,要看一下二叉树的构建方式，二叉树看成一个带左右指针的链表

二叉树的搜索：深度优先搜索(DFS,回溯,前中后序遍历,一般用递归实现(一般用栈是可以模拟递归的行为的，因此用迭代法也可以实现前中后序))，广度优先搜索(BFS,常见层序遍历)

二叉树节点的定义：

class TreeNode:
 def __init__(self, val=0, left=None, right=None):
     self.val = val
     self.left = left
     self.right = right

可以转成搜索问题。入队和出队是对称的，dfs下面开始进行回溯。其实可以不用值去接受，把这个问题看成是搜索问题即可，用全局变量去记录，找到宝藏后添加即可。回溯过程也可以通过值传递的方式来做，这样在放回上一层的时候对应的调用栈的值也可以被恢复。

回溯算法#

对于有显式的数据结构的，深度优先搜索都是在树和图上面进行的。在实际问题中，往往不存在一个树或者图，但是我们可以通过 记录状态和状态转移的方式，建立虚拟的树和图。

反过来看，在问题建模出来的状态转换图上进行深度优先遍历，其实就相当于实际生活中遇到多个选择时一个一个尝试的过程。如果当前选择可行，就继续下去；如果不可行，那么我就退回到上一个选择。这个退回到上个选择的步骤恰好能与递归里的回溯对应起来，因此这样的解决问题的思路（算法）被称作为回溯算法。

在代码实现的层面，我们可以利用变量去描述状态的相关信息。不同的变量的值代表解决一个实际问题中所处的不同的阶段，这些变量就叫做「状态变量」。所有的状态变量构成的集合称为 「状态空间」。

在具体进行时，通过递归与回溯完成往前走和重新选择的过程，就是完整的回溯算法的实现了。

在最根本的思想上，回溯法会与枚举法非常类似，因为它是枚举所有的选择，所以我们也会把回溯法称作为「暴力搜索」。但是与最简单的循环不同，在搜索时的遍历，是期望能够走到解决问题的状态的遍历，并且也会尽量往解决问题的状态走。因此，回溯算法是有方向的遍历。

回溯算法其实是在一棵隐式的树或者图上进行了一次深度优先遍历，我们在解决问题的过程中需要把问题抽象成一个树形问题。充分理解树形问题最好的办法就是用一个小的测试用例，在纸上画出树形结构图，然后再针对树形结构图进行编码。画图是一个很好的方法

回溯算法问题的问法 问「一个问题 所有的 解」一般考虑使用回溯算法。因此回溯算法也叫「暴力搜索」，但不同于最粗暴的多个 for 循环，回溯算法是有方向的遍历。

「状态」和「状态空间」 为了区分解决问题的不同阶段、不同规模，我们可以通过语言描述进行交流。在算法的世界里，是通过变量进行描述的，不同的变量的值就代表了解决一个实际问题中所处的不同的阶段，这些变量就叫做「状态变量」。所有的状态变量构成的集合称为「状态空间」。

不同状态之间的联系形成图（树）结构 我们可以把某种规模的问题描述想象成一个结点。由于规模相近的问题之间存在联系，我们把有联系的结点之间使用一条边连接，因此形成的状态空间就是一张图。

树结构有唯一的起始结点（根结点），且不存在环，树是特殊的图。这一章节绝大多数的问题都从一个基本的问题出发，拆分成多个子问题，并且继续拆分的子问题没有相同的部分，因此这一章节遇到的绝大多数问题的状态空间是一棵树。

我们要了解这个问题的状态空间，就需要通过 遍历 的方式。正是因为通过遍历，我们能够访问到状态空间的所有结点，因此可以获得一个问题的 所有 解。

为什么叫回溯 而「回溯」就是 深度优先遍历 状态空间的过程中发现的特有的现象，程序会回到以前访问过的结点。而程序在回到以前访问过的结点的时候，就需要将状态变量恢复成为第一次来到该结点的值。(这里如果显示传参的话对应的值是可以随着回溯恢复的，因为是值传递)

在代码层面上，在递归方法结束以后，执行递归方法之前的操作的 逆向操作 即可。

回溯算法的实现细节

解释递归后面状态重置是怎么回事

• 当回到上一级的时候，所有的状态变量需要重置为第一次来到该结点的状态（在pycharm调试中是在进入递归后，函数整个状态会被保存，并压入堆栈），这样继续尝试新的选择才有意义；
• 在代码层面上，需要在递归结束以后，添加递归之前的操作的逆向操作，用于返回上一步状态，或者直接带变量传参；

基本类型变量和对象类型变量的不同处理

• 基本类型变量每一次向下传递的时候的行为是复制（值传递？），所以无需重置；
• 对象类型变量在遍历的全程只有一份，因此再回退的时候需要重置；
• 类比于 Java 中的 方法参数 的传递机制：
  • 基本类型变量在方法传递的过程中的行为是复制，每一次传递复制了参数的值；
  • 对象类型变量在方法传递的过程中复制的是对象地址，对象全程在内存中共享地址。

字符串问题的特殊性

• 如果使用 + 拼接字符串，每一次拼接产生新的字符串，因此无需重置；
• 如果使用 StringBuilder 拼接字符串，整个搜索的过程 StringBuilder 对象只有一份，需要状态重置。

为什么不是广度优先遍历

• 广度优先遍历每一层需要保存所有的「状态」，如果状态空间很大，需要占用很大的内存空间；
• 深度优先遍历只要有路径可以走，就继续尝试走新的路径，不同状态的差距只有一个操作（深度优先搜索的状态差异只有一步），而广度优先遍历在不同的层之前，状态差异很大，就不能像深度优先遍历一样（广度优先搜索层与层状态变化太大，因此不太好去进行递归和状态的转移），可以 使用一份状态变量去遍历所有的状态空间，在合适的时候记录状态的值就能得到一个问题的所有的解。

减枝策略#

剪枝的必要性 剪枝的想法是很自然的。回溯算法本质上是遍历算法，如果 在遍历的过程中，可以分析得到这样一条分支一定不存在需要的结果，就可以跳过这个分支。

剪枝技巧 发现剪枝条件和「空间换时间」都是剪枝的技巧。「力扣」第 51 题：（N 皇后）和第 37 题（解数独），都需要在遍历的时候，记录已经放置的棋盘上的棋子的信息，这种空间换时间的思想其实也达到了剪枝的效果。

剪枝会在遍历的过程中带来性能消耗，如果问题规模较小则没有必要剪枝。如果问题规模较大，剪枝就很有必要了。

递归和分治专项#

这部分专项主要来自于LeetCode中的Leetbook 分而治之专项，剩下的包含一些做题过程中的自我总结，链接：https://leetcode.cn/leetbook/read/recursion-and-divide-and-conquer/r21rci/ ↗

递归是编程技巧，直接体现在代码上 ，即函数自己调用自己；在调用的函数执行完毕之后，程序会回到产生调用的地方，继续做一些其他事情。调用的过程被称作为递归，返回的过程被称作为回溯。

分治是一种算法设计的思想，将大问题分解成多个小问题，例如归并排序将大问题：「排序整个数组」，分解为小问题：「排序左半和右半」；绝大部分情况下「分治算法」通过「递归」实现。即：子问题的求解通过递归方法实现。

「递归」函数基于 「自顶向下」拆分问题，再「自底向上」逐层解决问题的思想设计而成，这是所熟知的「分而治之」的算法思想。

递归的设计思想：分而治之 tips: 分治是一种设计思想，而想实现分治则可以利用递归的实现技巧（递归是手段）来将主问题进行拆分，之后在通过回溯的方式来得到最终的答案。

分而治之（Divide-and-Conquer）的思想分为如下三步：

1. 拆分：将原问题拆分成若干个子问题；
2. 解决：解决这些子问题；
3. 合并：合并子问题的解得到原问题的解。 这样的三步恰好与递归的程序写法相吻合：

拆分：即对当前的大问题进行分析，写出相应代码，分解为子问题。 解决：即通过递归调用解决子问题； 合并：即在回溯的过程中，根据递归返回的结果，对子问题进行合并，得到大问题的解。

因此，分治算法一般通过递归实现。

更加形象的一种说法是：一开始我们只有一个问题，我们通过分治，将其分解成多个问题，发散开来，“自顶向下”走出去。在解决完子问题之后，在回溯的过程中合并子问题的解，将发散开来的问题合并成一个，“自底向上”走回来。

典型的分治思想的应用是：归并排序、快速排序、绝大多数「树」中的问题（先把原问题拆分成子树的问题，当子树中的问题解决以后，结合子树求解的结果处理当前结点）、链表中的问题。

「分治思想」的特例是「减治思想（Decrease-and-Conquer）」：每一步将问题转换成为规模更小的子问题。「减治思想」思想的典型应用是「二分查找」「选择排序」「插入排序」「快速排序」算法。「分治」与「减治思想」的区别如下：

• 分治思想：将一个问题拆分成若干个子问题，然后再逐个求解，根据各个子问题得到的结果得到原问题的结果；
• 减治思想：在拆分子问题的时候，只将原问题转化成 一个 规模更小的子问题，因此子问题的结果就是上一层原问题的结果，每一步只需要解决一个规模更小的子问题，相比较于「分治思想」而言，它 没有「合并」的过程。

总结：

• 「分治」是思想，「减治」是分治的特例；
• 「递归」是代码表现形式；
• 「递归」有先拆分问题的过程，真正解决问题，需要在拆分到底以后，一层一层向上返回

自顶向下(记忆化递归)和自底向上(递推) 尾递归是指一个函数里的 return 语句 是返回一个函数的调用结果的情形，即最后一步调用的函数返回值被当前函数作为结果返回。

尾递归的特点是：return 这一行直接实现递归调用，而不进行额外的操作（最后一个 return 语句是单纯函数），也就是说没有「合并」的过程。

如果我们知道了一个问题最开始的样子，就可以通过递推的方式一步一步求解，直到得到了我们想要的问题的解，相对于递归而言，这样的思考方向是「自底向上」的。

动态规划有两个思考的方向：一个是记忆化递归，另一个是递推。记忆化递归对应了「自顶向下」的解决问题的方向，递推对应了「自底向上」的逐步求解问题的方向，自底向上的去合并计算结果。

很明显：「自底向上」思考问题的方向直接从一个问题的「源头」开始，逐步求解。相比较于「自顶向下」而言：

• 少了一层一层拆分问题的步骤；
• 也不需要借助一个数据结构（栈）记录拆分过程中的每一个子问题。

dfs变成f数组，递归变成循环，递归边界变成数组初始值。

树的问题绝大多数都可以使用「分治思想」解决

！！！！后面一定要做一下先序中序后序遍历的一些问题

二分查找#

有序数组的二分查找，分为闭区间，开区间和半开半闭区间。本质上是循环不变量的一个确定，核心的思想是循环部分要保证这个查找的区间要是空的，只要不是空则一直在循环即可。

对于有序数组的查找可能是查找大于等于(target)，大于(可以看成是target+1，如果是整数的情况)，小于(可以看成是大于等于target的左边的那个数)或者小于等于(大于等于target+1左边的数)这种情况，

对于一个有序数组查找，需要注意的是，由于我们想要的是第一个等于target的位置的下标，因此循环判断中，start部分的移动需要严格的比target小，这样才能保证最后得到的这个下标对应的值是刚刚等于target，也就是大于等于的情况，否则的话等于的部分的值会被连续的跳过。

这里实际上二分返回的边界是刚刚满足条件或者是刚刚不满足条件的边界

贪心算法#

贪心算法与回溯算法、动态规划的区别 「解决一个问题需要多个步骤，每一个步骤有多种选择」这样的描述我们在「回溯算法」「动态规划」算法中都会看到。它们的区别如下：

• 「回溯算法」需要记录每一个步骤、每一个选择，用于回答所有具体解的问题；
• 「动态规划」需要记录的是每一个步骤、所有选择的汇总值（最大、最小或者计数）,动态规划需要考虑原问题的所有子问题；
• 「贪心算法」每一次只需要考虑一个字问题，一般而言只需要记录与当前步骤相关的变量的值，通常是自底向上来进行求解。

可以使用「贪心算法」的问题需要满足的条件

• 最优子结构：规模较大的问题的解由规模较小的子问题的解组成，区别于「动态规划」，可以使用「贪心算法」的问题「规模较大的问题的解」只由其中一个「规模较小的子问题的解」决定；
• 无后效性：后面阶段的求解不会修改前面阶段已经计算好的结果；
• 贪心选择性质(全局最优性)：从局部最优解可以得到全局最优解，全局最优等同于局部最优。

贪心算法一般伴随着排序，这样把一个完整的问题变成子问题来进行逐步求解

滑动窗口和双指针#

双指针的应用需要其满足单调性，即往往是while中从满足要求变为不满足要求，或者从不满足要求逐渐变为满足要求，这样使用双指针，比较经典的是最小长度子数组209和乘积小于K的子数组713。滑动窗口的右端点的一个写法 for right, x in enumerate(nums):

在使用双指针的时候免不了需要对循环变量，i和j的指针位置来进行划分。在codebook里面引入了一个叫做循环不变量的概念。这里具体可能要看下算法导论第三版中出现的内容

这里我根据例题简单对双指针这个问题进行一个分析，对于双指针，或者一些排序插入等问题，区间的划分是很重要的，因此最开始的时候我们就需要对整个遍历的空间进行一个按照区间段的划分，这里要注意，需要涵盖整个遍历的空间，如[0,p1),[p1,i),[p2,len),这样，则通过这样的集合关系来得到i的一个循环的条件，这里就是i<p2，且在初始化的时候要注意，每一个区间都是空集合，不能出现非空，或者漏了的情况

循环不变量是人为定义的，无需记忆。只要我们在编码的开始明确了我们对变量和区间的定义，

当一个问题没有思路的时候，可以先考虑暴力求解的方式

滑动窗口」是一类通过使用两个变量在数组上同向交替移动解决问题的算法。这一类问题的思考路径通常是：先思考暴力解法，分析暴力解法的缺点（一般而言暴力解法的缺点是重复计算），然后 结合问题的特点，使用「双指针」技巧对暴力解法进行剪枝。因此，思考算法设计的合理性是更关键的，这一点适用于所有算法问题。

• left 和 right 同方向移动；
• 定义条件，即我们需要时刻检测的一件事情；
• 原理：充分利用本题本身的特点，以减少不必要的计算；
• 利用「循环不变量」保证代码边界正确；
• 不要记忆代码模板，应该结合具体问题分析出什么时候滑动窗口最长，什么时候滑动窗口最短；
• 掌握处理字符串的技巧。

动态规划#

最优子结构 最优子结构规定的是子问题与原问题的关系

动态规划要解决的都是一些问题的最优解，即从很多解决问题的方案中找到最优的一个。当我们在求一个问题最优解的时候，如果可以把这个问题分解成多个子问题，然后递归地找到每个子问题的最优解，最后通过一定的数学方法对各个子问题的最优解进行组合得出最终的结果。总结来说就是一个问题的最优解是由它的各个子问题的最优解决定的。

将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键。在解题中一般用状态转移方程描述这种组合。

重复子问题 重复子问题规定的是子问题与子问题的关系。没有重复的子问题则根本不用考虑动态规划

当我们在递归地寻找每个子问题的最优解的时候，有可能会重复地遇到一些更小的子问题，而且这些子问题会重叠地出现在子问题里，出现这样的情况，会有很多重复的计算，动态规划可以保证每个重叠的子问题只会被求解一次。当重复的问题很多的时候，动态规划可以减少很多重复的计算。

重复子问题不是保证解的正确性必须的，但是如果递归求解子问题时，没有出现重复子问题，则没有必要用动态规划，直接普通的递归就可以了。

动态规划算法中关于最优子结构和重复子问题的理解的关键点：

1. 证明问题的方案中包含一种选择，选择之后留下一个或多个子问题
2. 设计子问题的递归描述方式
3. 证明对原问题的最优解包括了对所有子问题的最优解
4. 证明子问题是重叠的（这一步不是动态规划正确性必需的，但是如果子问题无重叠，则效率与一般递归是相同的）

对于动态规划问题，首先的第一步就是将问题的规模减小，一些典型的减小方式是动态规划分类的依据，例如线性，区间，树形等。数组上有两种常见的思路，第一个是每次减少一半，另一个是每次减少一个(相当于一个是对半的去进行收缩，而另一种是一个一个的进行递归转移)

在自顶向下的算法(记忆化)中，由于递归的存在，程序运行时有额外的栈的消耗。

有了状态转移方程，我们就知道如何从最小的问题规模入手，然后不断地增加问题规模，直到所要求的问题规模为止。在这个过程中，我们同样地可以记忆每个问题规模的解来避免重复的计算。这种方法就是自底向上的方法(迭代法)，由于避免了递归，这是一种更好的办法。

但是迭代法需要有一个明确的迭代方向，例如线性，区间，树形，状态压缩等比较主流的动态规划问题中，迭代方向都有相应的模式。但是有一些问题迭代法方向是不确定的，这时可以退而求其次用记忆化来做。

动态规划和其他算法之间的关系

分治（并不存在重复子问题，即不存在数据复用的问题）： 解决分治问题的时候，思路就是想办法把问题的规模减小，有时候减小一个，有时候减小一半，然后将每个小问题的解以及当前的情况组合起来得出最终的结果。例如归并排序和快速排序，归并排序将要排序的数组平均地分成两半，快速排序将数组随机地分成两半。然后不断地对它们递归地进行处理。

这里存在有最优的子结构，即原数组的排序结果是在子数组排序的结果上组合出来的，但是不存在重复子问题，因为不断地对待排序的数组进行对半分的时候，两半边的数据并不重叠，分别解决左半边和右半边的两个子问题的时候，没有子问题重复出现，这是动态规划和分治的区别。

贪心：

1. 关于最优子结构

   • 贪心：每一步的最优解一定包含上一步的最优解，上一步之前的最优解无需记录
   • 动态规划(是局部最优，但未必是上一步的最优解)：全局最优解中一定包含某个局部最优解，但不一定包含上一步的局部最优解，因此需要记录之前的所有的局部最优解

2. 关于子问题最优解组合成原问题最优解的组合方式

   • 贪心：如果把所有的子问题看成一棵树的话，贪心从根出发，每次向下遍历最优子树即可，这里的最优是贪心意义上的最优。此时不需要知道一个节点的所有子树情况，于是构不成一棵完整的树（属于是一步的探索走，可能并没有探究所有的可能）
   • 动态规划：动态规划需要对每一个子树求最优解，直至下面的每一个叶子的值，最后得到一棵完整的树，在所有子树都得到最优解后，将他们组合成答案（本质上对于之前的步是吸收了在当前的所有情况的一个最优解，因此是最优解的组合）

3. 结果正确性

   • 贪心不能保证求得的最后解是最佳的，复杂度低
   • 动态规划本质是穷举法，可以保证结果是最佳的，复杂度高

线性动态规划#

线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的，较大规模的问题的解依赖较小规模的问题的解。

这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。

状态定义：

dp[n] := [0..n] 上问题的解

状态转移：

dp[n] = f(dp[n-1], ..., dp[0])

从以上状态定义和状态转移可以看出，大规模问题的状态只与较小规模的问题有关，而问题规模完全用一个变量 i 表示，i 的大小表示了问题规模的大小，因此从小到大推 i 直至推到 n，就得到了大规模问题的解，这就是线性动态规划的过程。

线性动态规划解决的问题主要是单串，双串，矩阵上的问题，因为在单串，双串，矩阵上问题规模可以完全用位置表示，并且位置的大小就是问题规模的大小。因此从前往后推位置就相当于从小到大推问题规模。

单串问题 单串 dp[i] 线性动态规划最简单的一类问题，输入是一个串，状态一般定义为 dp[i] := 考虑[0..i]上，原问题的解，其中 i 位置的处理，根据不同的问题，主要有两种方式：

• 第一种是 i 位置必须取，此时状态可以进一步描述为 dp[i] := 考虑[0..i]上，且取 i，原问题的解；
• 第二种是 i 位置可以取可以不取

线性动态规划中单串dp[i]的问题，状态的推导方向以及推导公式如下:

1. 依赖比 i 小的 O(1) 个子问题 dp[n] 只与常数个小规模子问题有关，状态的推导过程 dp[i] = f(dp[i - 1], dp[i - 2], …)。时间复杂度O(n)，空间复杂度O(n) 可以优化为O(1)，leetcode 70, 801, 790, 746 都属于这类。

如图所示，虽然紫色部分的 dp[i-1], dp[i-2], …, dp[0] 均已经计算过，但计算橙色的当前状态时，仅用到 dp[i-1]，这属于比 i 小的O(1)个子问题。

2. 依赖比 i 小的 O(n) 个子问题 dp[n] 与此前的更小规模的所有子问题 dp[n - 1], dp[n - 2], …, dp[1] 都可能有关系。

状态推导过程如下：

dp[i] = f(dp[i - 1], dp[i - 2], ..., dp[0])

依然如图所示，计算橙色的当前状态 dp[i] 时，紫色的此前计算过的状态 dp[i-1], …, dp[0] 均有可能用到，在计算 dp[i] 时需要将它们遍历一遍完成计算。

其中 f 常见的有 max/min，可能还会对 i-1,i-2,…,0 有一些筛选条件，但推导 dp[n] 时依然是O(n)级的子问题数量。 leetcode 139,818属于这一类

注意：在定义DFS或者DP数组的含义的时候，只能表示从一些元素中算出的结果，而不能表示从一个元素中算出的结果。

把递归的结果保存下来，那么下次递归到同样的入参的时候就直接放回之前保存的结果

递归搜索+保存计算结果=记忆化搜索，时间复杂度 = 状态的个数*单个状态所需要的计算时间

0-1背包问题是一个经典的选和不选的问题，递归一上来就要开始进行选和不选的判断

刷题当中的需要注意的python用法#

泛型编程，python3特有，typing库

from typing import List, Dict, Tuple

泛型允许你定义数据结构或函数时使用类型参数，这些类型参数在具体使用时可以被替换为具体的类型。Python 的 typing 模块提供了对泛型的支持。typing 是python3.5中开始新增的专用于类型注解(type hints)的模块，为python程序提供静态类型检查，若有一些元素声明，则后面会跟一个方括号[]

这篇文章还是写的不错的可以看看：https://blog.csdn.net/weixin_46713695/article/details/125032851 ↗

随机数和随机采样相关的问题 用法：

random.sample(list, k)

其中，list是要进行抽样的序列，可以是列表、元组、字符串、range范围等；k是要抽取的元素个数。

python中二维矩阵的初始化问题 False] * n 直接初始化的是每行元素，后面的for循环直接初始化整个的矩阵，得到所有的行

dp = [[False] * n for _ in range(n)]

递归中的nonlocal函数的用法

def 外层函数():
    # 定义一个外层函数的局部变量
    变量 = 值
    
    def 嵌套函数():
        # 使用nonlocal关键字声明要修改的外层函数的局部变量
        nonlocal 变量
        # 修改外层函数的局部变量
        变量 = 新值
        
    # 调用嵌套函数
    嵌套函数()
    
    # 返回外层函数的局部变量
    return 变量

刷递归相关的题的时候很容易用到的一个技巧，如果不想显式的传入参数，利用回溯/栈回退的方式来恢复局部变量，我们可以使用这种方式来声明一个局部变量，并在递归函数中去更改这个局部变量，从而将具体的变量带出。这种方式不需要接收返回值，更像一种递归的搜索问题。

nonlocal是python中的一个关键字，它用于在嵌套函数中修改外层函数的局部变量。局部变量是在函数内部定义的变量，它们只在函数的作用域内有效，不能被其他函数访问或修改

使用nonlocal可以帮助我们：

• 实现一些高级的功能，比如闭包，装饰器，生成器等
• 保持外层函数的局部变量的状态，避免使用全局变量或类属性等
• 提高代码的封装性和可读性，避免命名冲突和污染全局命名空间

python中的有关负无穷和正无穷的值的处理 可以写成：left=inf, right=inf的形式，用inf关键字来表示负无穷到正无穷的范围

lambda表达式和排序的使用 Python 自定义函数主要有两种方式，一是 def，二便是 lambda。lambda表达式没有函数名称，因此也被称为是匿名函数。 其定义的格式为：

lambda [arg1,[arg2,arg3…]]: expression

## 此处只是为了举例，平常不建议这样将lambda表达式赋值给变量
a = lambda x: x ** 2

其中[]内是捕获的变量，感觉这个在c++11中也是有的，可能涉及一些捕获方式的问题，这里是用x来捕获迭代器中的变量，在去按照排序的选择进行。

lambda表达式只有一行，相比于函数，它具有的优势：

• 对于单行函数，使用 lambda 表达式可以省去定义函数的过程，让代码更加简洁；
• 对于不需要多次复用的函数，使用 lambda 表达式可以在用完之后立即释放，提高程序执行的性能。

sorted() 函数对所有可迭代的对象进行排序操作。sorted的语法如下：

sorted(iterable, key=None, reverse=False)

参数说明：

• iterable — 可迭代对象。
• key — 主要是用来进行比较的元素，注意这里的key是sorted函数里面的一个参数名，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
• reverse — 排序规则，reverse = True 降序 ， reverse = False 升序

sort() 和sorted() 函数中，key=lambda x:x[] 即表示待排序对象按第多少维度进行排序。例如下面就是按照第2个字段来进行排序：

list2 = [['小明', 23], ['大美', 22], ['小帅', 18], ['张三', 24]]
list3 = sorted(list2, key=lambda x: x[1])

拷贝相关的问题

matrix = matrix_new
matrix[:] = matrix_new

这两个的区别，上面那个直接是把引用挂到了matrix_new上，在leetcode上需要原地返回更改结果的往往会不过，因为内存的位置被进行了修改。而下面是说matrix通过切片的方式对内容进行了更新，更新的内容和matrix_new中的一样，需要注意的是，这里依然是一个浅拷贝，即matrix_new中的内容发生变化的时候，matrix中的内容也会发生变化。因此如果需要把这个值固定下来，需要用深拷贝的方式。

数组中enumerate的使用 有时候遍历数组的时候需要同时得到当前的值和数组下的下标，这时就可以利用python中的enumerate用法对list来进行id和value的放回

for i, x in enumerate(nums): 

灵神代码精讲#

滑动窗口类问题 滑动窗口」是一类通过使用两个变量在数组上同向交替移动解决问题的算法。这一类问题的思考路径通常是：先思考暴力解法，分析暴力解法的缺点（一般而言暴力解法的缺点是重复计算），然后 结合问题的特点，使用「双指针」技巧对暴力解法进行剪枝。因此，思考算法设计的合理性是更关键的，这一点适用于所有算法问题。

滑动窗口类的题目有一个特性就是单调性，就是比如说递增的，或者累加的，或者累乘的，或者逐渐增常的，代表性的题目有：713. 乘积小于 K 的子数组；3. 无重复字符最长字串；209. 长度最小字数组（连续子数组，求和大于某个值）。这类题的特点都是遍历右端点，之后收缩左端点和对应的结果，找到左端点对应的边界，和历史的满足条件的结果，选出最满足题意的结果。

二分查找问题 二分查找最核心的是先去确认我们的左右的区间到底是全闭，半开半闭还是全开，分别对应[left, rigt],[left, right),以及(left, right)，核心的思想是要遍历数组中的所有的元素，while的循环变量是不能为空的，而边界的变化也是由我们确认的最开始的访问的空间来决定，例如：

def lower_bound(nums: List[int], target: int) -> int:
    # 这里的左右指针的定义决定了搜索的区间的定义
    left = 0
    right = len(nums) - 1 # 此时是左闭，右闭区间

    while left <= right:  # 区间不为空
        mid = left + (right - left) // 2
        if nums[mid] < target:
            # left的取值一定是大于等于target的
            left = mid + 1   # [mid+1, right]
        else:
            # 当找到目标的时候 left=right时，right会向后移动一位，因此left是满足条件的第一个值
            right = mid - 1   # [left, mid-1]

        return left

当始终没找到的时候left会移动到队尾，如果定义的区间是左闭右开区间：

def lower_bound(nums: List[int], target: int) -> int:
    # 这里的左右指针的定义决定了搜索的区间的定义
    left = 0
    right = len(nums) # 此时是左闭，右开区间

    while left < right:  # 区间不为空，如果有相等则根据定义还是为空，只有严格小于是不为空
        mid = left + (right - left) // 2
        if nums[mid] < target:
            # left的取值一定是大于等于target的
            left = mid + 1   # [mid+1, right)
        else:
            # 当找到目标的时候 left=right时，right会向后移动一位，因此left是满足条件的第一个值
            right = mid   # [left, mid-1]->[left, mid)

        return left   # 此时返回right也是可以的，mid即为left的位置

如果定义的区间全部都是开区间

def lower_bound(nums: List[int], target: int) -> int:
    # 这里的左右指针的定义决定了搜索的区间的定义
    left = -1    # 要到前一位
    right = len(nums) # 此时是左开，右开区间

    while left+1 < right:  # 区间不为空，如果有相等则根据定义还是为空，只有严格小于是不为空
        mid = left + (right - left) // 2
        if nums[mid] < target:
            # left的取值一定是大于等于target的
            left = mid   # [mid+1, right]->(mid, right)
        else:
            # 当找到目标的时候 left=right时，right会向后移动一位，因此left是满足条件的第一个值
            right = mid   # [left, mid-1]->(left, mid)

        return right   # nus[mid] == target时，left开区间不包括，right正好等于mid？

第一种方法对应的是大于等于target的情况，那可能也有大雨，小于，或小于等于的情况，这些都可以给予大于等于去做改进，如果是大于，则可以看成是大于等于target+1的情况（例如大于8，和大于等于9是等价的，因为大于8不可能等于8，则最近的数就是9，因此等价于大于等于9），如果是小于等于，则可以是大于target+1的位置的左边的数，如果是小于，则可以看成是大于等于target位置的左边的数。以上的情况都是整数的情况

反转链表类别 实际上也称为头插法，有点双指针的味道。先初始化一个pre，作为一个节点，紧接着，cur和pre不断的向后移动，cur每次的next都进行反转，并更新pre和cur的新的位置，在反转之前先要对cur的next结果进行保存，所以要留有一个中间变量，用于最后将cur更新到临时变量中。

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        pre = None
        cur = head
        while cur:
            nxt = cur.next   # 先保存结果
            cur.next = pre   # 重新指向cur值
            pre = cur   # 更新pre
            cur = nxt   # 再更新cur
        return pre   # pre指向列表最后，cur已经为空

另一种链表的反转问题只反转中间的部分变量，那么实际上中间部分的反转和简单的链表反转一样，只不过需要找到最开始的需要反转部分的头的位置，同时要插入一个哨兵的节点，用于找到最开始的头，因为当left等于1是是没有p0的，需要引入一个在虚拟的头节点。这样p0的next的next指向cur，也就是不需要反转的那个节点，而反转部分节点的末尾在pre哪里，因此p0的next要指向pre。最后返回哨兵节点的next就可以了

递归类问题 以二叉树的最大深度为例，我们可以通过自底向上的将信息传回来，从而计算左右子树的最大深度，也可以通过自顶向下的传递当前层的深度来得到最大的值的时候的深度，这种有点类似于搜索的感觉，通过全局变量记录，只是通过return终止当前的递归。而之前只是通过将下面的结果逐层的回溯过来从而产生当前的一个结果估计。

子集型回溯问题 单纯的循环嵌套的表达能力是有限的，通过递归可以达到多重循环的效果。回溯有一个增量构造答案的过程，这个过程通常是用递归来进行实现的。只要边界条件和非边界条件逻辑写对，那就一定能得到正确的结果。

回溯三问：

需要注意，python的切片都是左闭右开的

组合型回溯问题 从n个树中选k个数，可以通过剪枝的方法，来加快求解

动态规划问题1----从记忆化搜索到递推 核心就是状态定义和状态的转移方程，要把大问题拆解成规模更小的子问题，从第一个或者最后一个问题来进行思考是比较容易的。如果有递归的方式去写，可能会由于多次计算同一个递归结果导致计算的超时，因此需要做记忆化，就是将一些中间的结果记录下来。对于python可以用@cache装饰器来做，用hashmap来记录入参和对应的返回值。对应的也可以用数组来实现，即用空间换时间。时间复杂度=状态个数*单个状态所用的时间。

自顶向下对应记忆化搜索，子底向上计算对应递推。把记忆化搜索改成递推。1:1翻译成递推，dfs->数组，递归->循环，递归边界->数组初始值。但需要对i=0和1进行特殊处理，因为会产生负数的下标。

以leetcode的这个198的打家劫舍的题目为例，首先先确定递归的关系，f(n) = max(f(n-1), f(n-2)+nums[i])，这个是一切的前提。先写出一个简单的递归方法，由于递归的有些变量会被重复的使用，因此这里可以用functools中的cache关键字来进行修饰，进行存储。

class Solution:
    def rob(self, nums: List[int]) -> int:
        # f(n) = max(f(n-1), f(n-2)+nums[i])
        from functools import cache

        # cache等价于DP中的精细化搜索
        @cache
        def dfs(i):
            # 对于递归方法一定要给终止条件，这个根据数值的意义可以进行设定
            if i < 0:
                return 0
            return max(dfs(i-1), dfs(i-2)+nums[i])
        return dfs(len(nums)-1)

当然我们也可以把dfs的结果利用一个数组给他显式的记录下来。则代码可以写为：

class Solution:
    def rob(self, nums: List[int]) -> int:
        # f(n) = max(f(n-1), f(n-2)+nums[i])
        from functools import cache
        
        cache = [-1] * len(nums)
        
        def dfs(i):
            # 对于递归方法一定要给终止条件，这个根据数值的意义可以进行设定
            if i < 0:
                return 0
            if cache[i] != -1:
                return cache[i]
                
            res = max(dfs(i-1), dfs(i-2)+nums[i])
            
            # 这个就是cache[i]也就是dfs[i]的值，需要在计算后进行写入，这样在回溯的时候可以节省计算量
            cache[i] = res
            return res
        return dfs(len(nums)-1)

这里实际上只是在最后自底向上的归的过程中发生了计算，直接去掉递归，从最下面开始算，这个也成为递推。 把dfs改成数组，把递归改成循环。但需要对i等于1和等于0的情况进行特殊处理。这时代码会改写成为：

class Solution:
    def rob(self, nums: List[int]) -> int:
        # f(n) = max(f(n-1), f(n-2)+nums[i])
        n = len(nums)
        f = [0] * (n+2)
        for i, x in enumerate(nums):
            f(i+2) = max(f(i+1), f(i)+x)
        return f(n+1)  # 正常是n-1，但为了下标不为负数，所以所有的都加了2

也可以将当前，上一个和上上一个记录下来，循环更新这几个值，这样空间复杂度就从o(n)降低到了o(1)。

class Solution:
    def rob(self, nums: List[int]) -> int:
        # f(n) = max(f(n-1), f(n-2)+nums[i])
        n = len(nums)
        f0 = f1 = 0
        for i, x in enumerate(nums):
            # f(i+2) = max(f(i+1), f(i)+x)
            new_f = max(f1, f0+x)
            f0 = f1
            f1 = new_f
        return f1  # 最后的这个f1，和new_f一样是代表当前循环结束后最新的值

注意：自己写记忆化搜索转递推过程中出现的问题：

1. dfs的时候可以用返回的方式来终止循环同时取值，而这里改成for循环后变成了一种分类讨论和选择，因此要注意条件的判断，用if else的方式来对dp的数组的更新进行显示的判断
2. 二维数组初始化的时候，里面的变量要是一个list，要写成dp = [[0] * (n+1) for _ in range(m+1)]，这里的0要写成[]，[0] * (n+1) 是一种列表初始化的方式
3. 行列顺序的问题访问问题，初始化数组的时候，内层的循环生成的是每一行的所有列，实际上是列的个数，而最外层的循环是生成行，对应行的个数，矩阵通过下标访问的时候是先行后列，如dp[i][j]代表的是矩阵第i行和第j列的元素，因此数组初始化的顺序要和后面的for循环过程中的下标访问的方式保持一致，比如都是先行后列，i为行，j为列

动态规划问题2----0/1背包，完全背包，目标和等问题 动态规划的核心，要先想明白子问题，给出转移的函数过程。0-1背包问题，是指在容量有限的情况下，原则物品让其价值和最大，这就是典型的选与不选的问题，可以用回溯的思想看，考虑第i个物体（也就是底了）。这里i是当前步，c是总容量，w是当前容量，v是当前的价值。 dfs(i,c)=max(dfs(i-1,c), dfs(i-1, c-w[i])+v[i]))

完全背包，是有n种物品，每种物体可以重复选。因此在递归的过程中，在选择当前物品的状态底前一项递归还是f(i)，之后不选才会递归到f(i-1) dfs(i,c)=max(dfs(i-1,c),dfs(i,c-w[i])+v[i])

线性DP，最长公共子序列1143，编辑距离72

对于最长公共子序列问题，实际上就是得到一个状态转移的式子，从最后看，如果两个字母相等，会等于两个字母都不选在加1的LCS子问题中，如果两个不想等，那么会落在其中一个不选的LCS问题当中，取最大。

状态转移方程。

@cache就是改记忆化搜索的一个操作。

对于编辑距离问题，同样可以列出以下的转移方程：

当s和t的最新的这位相等时，不需要进行操作，则直接等于上一位的操作的结果。如果当前的并不相等，则可能会有三种操作，分别是插入，删除和替换，对于插入由于从末尾插入，则插入后在同时取掉改字母，实际上s和t取掉最后这位是一致的，如果是删除则说明删除一位和t是相等的，如果是替换，则说明替换后两者相同，则说明说明替换后两者都相同，一起取掉当前的元素，则会推到i-1和t-1的状态。核心思想，相同位数位置前移。

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 如果两个字符串相等，则最长公共子距离+1
        # 如果不等等于三者之间的最大值
        n = len(text1)
        m = len(text2)

        def dfs(i, j):
            if i < 0 or j < 0:
                return 0

            if text1[i] == text2[j]:
                return dfs(i-1, j-1) + 1

            return max(dfs(i-1, j), dfs(i, j-1))

        return dfs(n-1, m-1)

## leetcode 72 编辑距离
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        # 如果两者相同则不需要编辑，和上一步相同
        # 如果两者不同，则可能存在删除，插入和替换的情况注意要取最小值看一下。
        n = len(word1)
        m = len(word2)

        def dfs(i, j):
            # 如果其中一个为空，则需要把另一个完全删除才可以
            if i < 0:
                # 下标还有j，说明还有j+1个字符，需要操作j+1次
                return j + 1
            if j < 0:
                return i + 1

            if word1[i] == word2[j]:
                return dfs(i - 1, j - 1)

            return min(dfs(i - 1, j), dfs(i, j - 1), dfs(i-1, j-1)) + 1

        return dfs(n - 1, m - 1)

线性DP最长递增子序列 最长递增子序列，等于和nums排序去重之后的最长公共子序列，如果最长递增子序列允许重复，则nums只需要排序并不需要去重。

对于动态规划优化时间复杂度的进阶技巧，需要交换状态与状态值。

这个还是要看一下，那个加1的操作有点没懂。

状态机DP，买卖股票系列 可以分为两种类型，一种是不限制交易次数的（包含冷冻期问题），另一个中限制交易次数的（至多交易k次）。可以借助状态机更好的梳理状态转移方程。为了方便改成递推，推荐从后面来进行倒着思考。表示状态之间转换关系的图叫做状态机。 从图中可以看出，状态的转移一共有4种情况，从而定义状态和状态转移方程。得到如下的图，如果当天持有股票，则卖出，从持有状态变为未持有状态，如果买入，则当前是从未持有变为持有的状态。 通过取最大值，则可知道当前持有和未持有状态下的最佳值： 紧接着要考虑递归边界的问题，这里对很多dp问题都很重要，初始状态，或者初始的计数应该是什么样的。dfs(-1, 0)也就是第0天开始的时候未 持有股票的最大利润，则就是0。dfs(-1, 1)是第0天开始持有股票的最大利润，因为第0天开始不可能持有股票，因此可以初始化为负无穷。作者这样写主要担心prices数组是空的，这样递归到0可能会有问题。但为啥-1就没问题呢？

紧接着确定递归的关系和方程，正常应该是max(dfs(n-1, 0), dfs(n-1, 1))但最后一天持有股票一定是亏钱的，因此不可能比最有一天卖出去赚的多，所以大不了当天卖掉，那实际上还是会退回了最开始没有股票的状态。因此max(dfs(n-1, 0), dfs(n-1, 1))=dfs(n-1, 0)

如果有冷冻期，那说明前一天没发进行操作。如果卖出股票，第二天是没办法买入股票的，也就是说要想卖入股票，前一天不能卖出股票。那么卖入的状态转移要从i-1过度到i-2也就是前一天。

如果限制至多交易k次，如果想要有交易的要求，就需要记录当前交易的次数，因此dfs(i,0)就要改为dfs(i,j,0)，表示到第i天结束至多完成j笔交易，未持有股票时的最大利润，同理dfs(i,j,1)，表示到第i天结束至多完成j笔交易，持有股票时的最大利润。则如果要卖入则需要消耗一次交易的次数，如果是卖出，前面一定有卖入的操作，这里一买一卖算一笔操作，因此卖的部分就不需要在消耗交易的次数，这里默认只有买入的时候消耗交易次数。同理也可以认为买入不消耗次数，而卖出消耗交易次数，因此也可以把j-1写在0这个状态里。

恰好交易k次和至少k次，区别主要是在边界条件上：这个f[0][1][0]还是不太明白啥意思：

区间DP，最长回文子串，最优三角抛分等问题 最长回文子序列，可以通过将字符串反转，之后求两个的最长公共子序列。也可以变成从开始和最有位置往前看的选或者不选的问题，如果相同则两个都选，状态转移，如果不同则两个选其中最长的那个子序列的结果。注意加@cache就是改为记忆化搜索

当1:1翻译成为递推过程时，由于计算i得时候要先有i+1，因此i要倒叙枚举。而j的时候要有j-1算出，因此j要正序枚举。注意一下倒叙枚举的常见的写法for i in range(n-1, -1, -1)，由于range是左闭右开因此是从n-1到0的所有可能，每次减1。

最优三角抛分问题。

树形DP，树的直径 如果能够找到和原问题相似的子问题，并建立两者之间的联系，就可以用递归来尝试进行解决。数的直径和最大深度是否有联系？ 如果要计算二叉树的最大直径，思考的递归的单元是每一个node，递归的部分是最优子树的最长的链路，对于当前节点的最大链路等于左右子树的最大链路+2，而对于当前节点向父节点返回的最大链路，等于当前左右链路的最大值在加1

单调栈，每日温度，接雨水 对于单调栈来说需要及时去除无用数据，保留后面有用的数据，如果当前值比当前栈内的元素值都大，则清除所有之前的值，并把当前值加入。

    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        ans = [0] * n
        # 栈元素
        st = []
        for i in range(n):
            # 这里不能有等于，因为我们找的是严格大于的温度，等于并不行。
            while st and temperatures[st[-1]] < temperatures[i]:
                ans[st[-1]] = i - st[-1]
                st.pop()
            # t小于等于栈顶意味着无法更新栈顶，因为栈顶已经是小的元素了，无法更新栈里面的任何元素
            st.append(i)

        return ans

接雨水也可以用单调栈解决

如果我们发现题目需要涉及上一个或者下一个更大或者更小的元素，可以尝试用单调栈解决。

单调栈，滑动窗口最大值

及时去掉无用数据，保证双端队列有序，当前数字大于等于队尾，弹出队尾（和单调栈一样），弹出队首不在窗口内的元素。

基础深度学习函数书写

import numpy as np

def softmax(x):
    # 为避免溢出，通常对输入进行减去最大值操作
    x_max = np.max(x, axis=-1, keepdims=True)
    e_x = np.exp(x - x_max)  # 减去最大值，防止溢出
    e_x_sum = np.sum(e_x, axis=-1, keepdims=True)
    
    # 为了避免分母为0的情况，确保不为0的值加上一个小常数
    e_x_sum = np.maximum(e_x_sum, 1e-9)  # 避免除以0

    return e_x / e_x_sum

灵神的基础精讲 15，16，6，7，8还没看 灵神在做DP问题的时候都是先做dfs的公式的情况推导，在将其转为记忆化搜索给出@cache关键字。之后作者会进行1:1的翻译改成递推，这里的思考逻辑要考虑，感觉应该是为了避免重复的去计算dfs，因此将每部的dfs的结果都存储下来。当下标加1时对应的DP矩阵也需要加1

最长公共子序列的那个改成单个数组的那个逻辑还没懂