# 2023 Fall Algo 复习总结笔记
# Two Pointer
# Array and String
## Prefix Sum 前缀和
前缀和是一种简单但是非常实用的技巧，常用于解决一类特定的问题：对于一个给定的数组，快速查询某个区间的和。通过预处理，使用前缀和能在O(1)的时间复杂度完成这种查询。
```plaintext
[1, 3, 7, 5, 2]
[0, 1, 4, 11, 16, 18]
```
```python
def prefix_sum(nums):
# initialize
prefix = [0] * (len(nums) + 1)
# 计算前缀和
for i in range(n):
prefix[i + 1] = prefix[i] + nums[i]
return prefix
def query_sum(prefix, i, j):
# 查询子数组[i, j]的和
return prefix[j + 1] - prefix[i]
```
`prefix[i]` 就代表着`nums[0, ..., i - 1]`所有元素的累加和，如果我们想求区间。
`prefix[j + 1] - prefix[i] = sum(nums[i, ..., j])`
## Difference Array 差分数组
差分数组和前缀和思想非常类似。主要使用场景是频繁对原始数组的某个区间的元素进行增减。
比如说，我给你输入一个数组 `nums`，然后又要求给区间 `nums[2..6]` 全部加 1，再给 `nums[3..9]` 全部减 3，再给 `nums[0..4]` 全部加 2，再给...
一通操作猛如虎，然后问你，最后 nums 数组的值是什么？
常规的思路很容易，你让我给区间 `nums[i..j]` 加上 val，那我就一个 for 循环给它们都加上呗，还能咋样？这种思路的时间复杂度是 O(N)，由于这个场景下对 nums 的修改非常频繁，所以效率会很低下。
所以差分数组就是来解决这个问题的 `diff[i] = nums[i] - nums[i - 1]`
通过差分数组是可以反推出原始数组的：
```python
res = [0] * len(diff)
# 根据差分数组构造结果数组
res[0] = diff[0]
for i in range(1, len(diff)):
res[i] = res[i - 1] + diff[i]
```
**Code Signal 这道例题同时应用类差分思想和前缀和思想**
有一些灯泡摆放在一个数轴上。每一个灯泡都可以照亮数轴上的一个特定的片段（或者说，段落）。这些灯泡的位置由一个二维数组 lamps 表示。其中，第 i 个灯泡能照亮数轴上从 lamps[i][0] 到 lamps[i][1] 的这段区域。
然后题目给你一组点（用数组装），你需要返回一个数组，result[i] 表示的就是第i个点被多少个灯照亮。
这道题，提示我们用前缀和和差分思想的点在于：
1. 区间操作：当问题涉及到在数组or数轴的某个连续区间上进行操作，差分思想就很自然地被考虑，因为它可以高效地对连续区间进行更新。
2. 多个区间的叠加：每个灯泡都有一个照亮的区间，这些区间可能会有重叠。使用差分思想，我们可以很容易地叠加这些区间的效应。
3. 频繁查询：题目要求我们针对每个控制点查询它被多少灯泡照亮 ==> 频繁查询数组某个区间的和的问题
```python
def solution(lamps, points):
# 1. 初始化prefix数组
max_point = max([lamp[1] for lamp in lamps] + points)
prefix = [0] * (max_point + 2)
# 取出右端点，合并列表，找到最大值，并且通过这个最大值确定prefix数组的长度，
# 保证prefix数组可以cover所有灯泡和points的位置
print(max_point)
print(prefix)
# 2. 更新prefix数组
for lamp in lamps:
prefix[lamp[0]] += 1
prefix[lamp[1] + 1] -= 1
# 对于每一个灯泡，我们都会在它的左端点位置增加1，再它的右断点位置 - 1
# 如果一个点被某个灯泡覆盖，那么它在前缀和数组中的值会增加1。
# 而如果这个点超过了灯泡的右端点，我们要减去1，
# 表示这个灯泡不再照亮后面的位置。
# 3. 计算前缀和
for i in range(1, len(prefix)):
prefix[i] += prefix[i - 1]
# 4. 获取每个控制点的照亮灯数
res = [prefix[point] for point in points]
return res
# Test
lamps = [[1, 7], [5, 11], [7, 9]]
points = [7, 1, 5, 10, 9, 15]
print(solution(lamps, points))
```
# Binary Search
## 不会出错的二分法模版
```python
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums) - 1
while left + 1 < right:
mid = (left + right)//2
if nums[mid] < target:
left = mid
else:
right = mid
# when we need the first index of target
if nums[left] == target:
return left
# last index of the target
if nums[right] == target:
return right
return -1
```
## 变体 - 改成查找目标元素的个数
```python
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
left = 0
right = len(nums) - 1
while left <= right: # 注意此处条件为等号
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1 # 向右搜索
elif nums[mid] > target:
right = mid - 1 # 向左搜索
else:
# 找到目标元素后，不要立即返回，而是继续向左向右搜索，确定目标元素的个数
count = 1 # 初始化目标元素个数为1
# 向左搜索
left_idx = mid - 1
while left_idx >= 0 and nums[left_idx] == target:
count += 1
left_idx -= 1
# 向右搜索
right_idx = mid + 1
while right_idx < len(nums) and nums[right_idx] == target:
count += 1
right_idx += 1
return count
return -1 # 如果循环结束仍然没有找到目标元素，则返回-1
```
# 二叉树的种类
**二叉搜索树**是一个有序树。
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
**平衡二叉搜索树**
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
### 二叉树的储存
二叉树可以链式存储，也可以顺序存储。
那么链式存储方式就用指针， 顺序存储的方式就是用数组。
顾名思义就是顺序存储的元素在内存是连续分布的，而链式存储则是通过指针把分布在各个地址的节点串联一起。
链式存储是大家很熟悉的一种方式，那么我们来看看如何顺序存储呢？
其实就是用数组来存储二叉树，顺序存储的方式如图：
用数组来存储二叉树如何遍历的呢？
如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。
但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。
所以大家要了解，用数组依然可以表示二叉树。
### 二叉树经典例题
[100. Same Tree](https://leetcode.com/problems/same-tree/description/)
[572. Subtree of Another Tree](https://leetcode.com/problems/subtree-of-another-tree/description/)
[226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)
[101. Symmetric Tree](https://leetcode.com/problems/symmetric-tree/description/)
[104. Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/description/)
[111. Minimum Depth of Binary Tree](https://leetcode.com/problems/minimum-depth-of-binary-tree/description/)
[938. Range Sum of BST](https://leetcode.com/problems/range-sum-of-bst/description/)
Sum = root.val + left_subtree_sum + right_subtree_sum
下面的代码是用
```preseudo
func(root, low, high) -> int {
# end
if root is None:
return 0
leftSum = func(root.left, low, high)
rightSum = func(root.right, low, high)
res = leftSum + rightSum
if (low <= root.val <= high): {
res = res + val
}
return res
}
```
# BFS
```mermaid
graph LR
%% 根节点
BFS使用场景 --> Node1(联通块问题Connected Component)
BFS使用场景 --> Node2(分层traversal)
BFS使用场景 --> Node3(拓扑排序 Topological Sorting)
%% Node1 的子节点
Node1 --> Node1-1(通过一个点找到途中联通的所有点)
Node1 --> Node1-2(非递归的方式找到所有方案)
%% Node2 的子节点
Node2(分层traversal) --> Node2-1(图的层次遍历)
Node2(分层traversal) --> Node2-2(简单图最短路径 Simple Graph Shortest Path)
%% Node3 的子节点
Node3 --> 求任意拓扑序
Node3 --> 求是否有拓扑序
Node3 --> 求字典序最小的拓扑序
Node3 --> 求是否有唯一拓扑序
%% 例题
Node1-1 --> Node1-1-1(137 Clone Graph)
Node2-2 --> Node2-2-1(127 Word Ladder)
```
## 简单图最短路径问题
什么是简单图
* 没有方向 undirected
* 没有权重 unweighted
* 两点之间最多只有一条边 no multiple edges
* 一个点没有一条边直接连着自己 (no graph loop)
## 最简洁的BFS算法的通用模版
* 容易出错点在：
* 1.**需要一入队就标记成被访问，不然会有元素重复入队** (这样是最节省内存的)
* 2.如果需要分层的话，就加一层循环，
* `for _ in range(len(queue))` (python 写法)
Python队列建议使用deque，不建议使用Queue(涉及多线程枷锁会更慢)
```python
# step1 初始化
# 初始节点放到deque里, 并标记distance = 0
# distance 有两个作用，一是判断是否已经访问过，二是记录离起点的距离
queue = collections.deque([node])
distance = {node: 0}
# step2: 不断访问队列
# while 循环 + 每次pop队列中一个点出来
while queue:
# for _ in range(len(queue)):
node = queue.popleft()
# step3: 拓展相邻节点
# pop出的节点的相邻 node ，加入队列并在distance中存储距离
for neighbor in node.get_neighbors():
if neighbor in distance:
continue
distance[neighbor] = distance[node] + 1
queue.append(neighbor)
```
java队列建议用ArrayDeque, 比 LinkedList快
```java
Queue<Node> queue = new ArrayDeque<>();
HashMap<Node, Integer> distance = new HashMap<>();
// Step 1. initialize => 入队时就得标记成被访问
// distance 有两个作用，一是判断是否已经访问过，二是记录离起点的距离
queue.offer(node);
distance.put(node, 0);
// Step 2. 不断访问队列（while循环），每次pop队列中的一个点出来
while(!queue.isEmpty()) {
Node node = queue.poll()
// int size = queue.size()
// for (int i = 0; i < size; i++) {
// }
// Step 3: 拓展相邻节点
// pop 出的节点的相邻节点，加入队列并在distance中存储距离
for (Node neighbor : node.getNeighbors()) {
if (distance.containsKey(neighbor)) {
continue;
}
distance.put(neighbor, distance.get(node) + 1);
queue.offer(neighbor);
// 80% 的人都容易在这里出错，这里需要入队的时候就标记成被访问
// 不是在出队的时候标记！
}
}
```
## 二叉树的Vertical Traversal
用BFS做：
对于一棵树，我们设其根节点的位置为0。 对于任一非叶子节点，若其位置为x，设其左儿子的位置为x-1，右儿子位置为x+1。 按照以上规则bfs遍历整棵树统计所有节点的位置，然后按位置从小到大输出所有节点。
## BFS练习题目
联通块问题
[137 clone graph](https://leetcode.com/problems/clone-graph/)
* Step1: find all the nodes
* Step2: copy nodes 可以用hashtable确保每个点只被复制一次
* Step3: copy sides(neighbors)
简单图最短路径问题
[127 Word Ladder](https://leetcode.com/problems/word-ladder/) 这道题解法是BFS, get_neighbors 是O(N)的时间复杂度，这玩意儿得暴力搜一遍。=> 整体的时间复杂度是 O(N^2)
[1197 minimum knight move](https://leetcode.com/problems/minimum-knight-moves/description/) 这道题有很多“小优化”的剪枝策略来减少搜索范围，很值得一看
矩阵中的宽度优先搜索
[200. Number of Islands](https://leetcode.com/problems/number-of-islands/) BFS 的解法是 get_neighbors 变成上下左右四个方向都遍历一遍
## 拓扑排序 Topological Sorting
拓扑排序是对有向无环图(DAG)的顶点的线性排序
**入度（In-Degree)**: **有向图（Directed Graph）** 中指向当前节点的点的个数（或指向当前节点的边的条数。
**算法描述**：
1. 统计每个点的入度(In-Degree)
2. 将每个入度为0的点放入队列Queue中作为起始节点
3. 不断从队列中拿出一个点，去掉这个点的所有连边（指向其他点的边），其他点相应的入度 -1
4. 一旦发现新的入度为0的点，丢回队列中
一个图可能存在多个拓扑序，也可能不存在任何拓扑序。
所以这类问题有四种问法
* 求任意一个拓扑排序
* 问是否存在拓扑排序
* 求是否存在且仅存在一个拓扑排序
* 求字典序最小的拓扑排序
**求任意一个拓扑排序 + 问是否存在拓扑排序**
[207. Course Schedule](https://leetcode.com/problems/course-schedule/)
* 难点1，要自己把图建立起来
* 难点2，从in_degree为0的开始，而不是从任意一个node开始
* 难点3，get_neighbors 就是要结合自己一开始建的图，像这里其实直接用了嵌套的list
* 难点4，要 in_degree == 0 的才可以入队
* 难点5，这里没有用visited，而是用in_degree == 0 和 num_choose来代替，然后来检测有没有足够的节点被choose了
```python
class Solution(object):
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: bool
"""
# initialize graph
graph = [[] for i in range(numCourses)]
# 1. get in_degree, and create graph
in_degree = [0] * numCourses
for node_in, node_out in prerequisites:
graph[node_out].append(node_in)
in_degree[node_in] += 1
# 2. initialize: start from all the nodes with 0 in_degree
queue = collections.deque()
for i in range(numCourses):
if in_degree[i] == 0:
queue.append(i)
num_choose = 0
topo_order = []
# 3. BFS
while queue:
cur = queue.popleft()
topo_order.append(cur)
num_choose += 1
for next_possible in graph[cur]:
in_degree[next_possible] -= 1
if in_degree[next_possible] == 0:
queue.append(next_possible)
if num_choose == numCourses:
return True
return False
```
**求是否存在且仅存在一个拓扑排序**
[Sequence Reconstruction](https://leetcode.com/problems/sequence-reconstruction/)
这个算法的重点在：
```python
def topological_sort(self, graph):
...
while queue:
# 如果队列中有超过一个入度为0的节点，说明存在多个有效的拓扑顺序。
if len(queue) > 1:
return None # 或者返回一个特殊值，表示不是唯一的
...
```
**求字典序最小的拓扑排序**
[269. Alien Dictionary](https://leetcode.com/problems/alien-dictionary/)
* 难点在构建graph（用字典，key = letter, value = list(letters)）
* 第二个是如何让字典序最小
```python
queue = [node for node in graph if inDegree == 0]
heapify(queue)
```
`heapify()` 把列表转换为堆数据结构。堆是一种特殊的树形数据结构，其每个父节点的值都小于或等于其所有子节点的值（这是最小堆；对于最大堆，父节点的值大于或等于其子节点的值）。堆通常用于实现优先队列。
`heapq.heappop(lst)`：从堆中弹出并返回最小元素。
`heapq.heappush(lst, value)`：将新元素添加到堆中，并确保维持堆的性质。
这些操作的时间复杂度分别是O(log n)和O(log n)。
```java
Queue<Character> queue = new PriorityQueue<>();
```
# DFS
从一点开始，任选一条路走到下一个点，直到走到尽头。
如果走到尽头，就回撤一步，换条路继续走。
在遍历的过程中搜索目标值或者目标路径。
在同一条路径中不走重复点，在不同路径中走过的重复点可以重复走。
## 递归
一般来说，如果面试官不特别要求的话，DFS都可以使用递归(Recursion)的方式来实现。
递归三要素是实现递归的重要步骤：
• 递归的终止条件
• 递归函数的返回值以及参数
• 递归的拆解 - 单层搜索的逻辑
**When Recursion?**
* 在之前的课程中，我们知道了二叉树（Binary Tree）的问题大部分都可以用DFS求解
* 除了二叉树以外DFS的题，要么是组合combination，要么是排列 permutation。
* 碰到让你找**所有方案**的题，基本可以确定是DFS (一个path就可以看做是方案)
* 如果题目给了你一个树或者图，可以在上面进行DFS
* 如果题目没有直接给你一个树或图，可以把题目的解空间看成一个树或图，然后在上面进行DFS。找到树或图中的所有满足条件的路径。
* 路径 = 方案 = 图中节点的排列组合
## DFS 解决二叉树问题的模版
**递归模版**
```python
class TreeNode:
def __init__(self, value = 0, left = None, right = None):
self.value = value
self.left = left
self.right = right
def dfs(node): # Preorder 根 -> 左 -> 右
if not node:
return
# 处理当前节点
process(node)
# 递归左子节点
dfs(node.left)
# 递归右子节点
dfs(node.right)
# Inorder 左 -> 根 -> 右
# Postorder 左 -> 右 -> 根
```
**带返回值**
```python
def dfs_with_return(node):
if not node:
# 返回一个基值或者默认值
return some_default_value
# 左子树结果
left_result = dfs_with_return(node.left)
# 右子树结果
right_result = dfs_with_return(node.right)
# 根据左右子树结果和当前节点值进行计算
return combine_results(node, left_result, right_result)
# 示例：获取二叉树的最大深度
def max_depth(node):
if not node:
return 0
left_depth = max_depth(node.left)
right_depth = max_depth(node.right)
return max(left_depth, right_depth) + 1
```
**graph的dfs需要多加一个visited**
```python
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
# 访问节点
visited.add(node)
for neighbour in graph[node]:
# 如果邻居没被访问过，递归访问它
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
```
# 回溯 Backtracking
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。属于一种brute force，不是什么高效算法，本质是穷举。
- 组合问题：N个数里找K个数
## 回溯法的模版
```plaintext
void backtracking(parameters):
if (终止条件) {
存放结果
return；
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点
backtracking（路径，选择列表）; // recursion
回溯，撤销处理结果
}
```
结合图和这个伪代码，我们可以看出这是DFS
for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。
backtracking这里自己调用自己，实现递归。
大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。
## 组合 Combination （把题目解空间看作是一个树）
[77.Combinations](https://leetcode.com/problems/combinations/)
```python
class Solution(object):
def combine(self, n, k):
"""
:type n: int
:type k: int
:rtype: List[List[int]]
"""
result = []
self.backtracking(n, k, 1, [], result)
return result
def backtracking(self, n, k, startIndex, path, result):
if len(path) == k:
result.append(path[:])
return
for i in range(startIndex, n - (k - len(path)) + 2):
path.append(i)
self.backtracking(n, k, i + 1, path, result) # 为什么这里是 i + 1 而不是 startIndex + 1 => 想想那张特别经典的图
path.pop()
```
剪枝优化从 `for i in range(startIndex, n + 1)`
到 `for i in range(startIndex, n - (k - len(path)) + 2)`
1. 已经选择的元素个数：path.size();
2. 还需要的元素个数为: k - path.size();
3. 在集合n中至多要从该起始位置 : n - (k - path.size()) + 1，开始遍历
4. 为什么有个+1呢，因为包括起始位置，我们要是一个左闭的集合。
# Heap/Priority Queue
什么时候会想到用heap/priority queue
题目里要求去求 最大/最小 值的时候，可以考虑使用heap
数组实现如何得到左右孩子？ (BST才能做到)
Left Child Index = Parent Index * 2 + 1
Right Child Index = Parent Index * 2 + 2
把 节点 13 （index 3） 作为例子
left = 3 * 2 + 1 = 7 (index) --> node 2
**注意:**
* heap里面的数据不是完全排序的
* heap的parent比它的children node
* heap的任意一颗子树都是最大堆/最小堆
**基本操作：**
构建堆 heapify O(N)
遍历堆 O(NlogN)
add O(logN)
- eg: 底层实现是这样的，比如加个150，150作为Leaf node加进去，然后一层层往上比。比如加到3下面，然后发现150比3大，150就和3换位置，然后再发现150比19大，所以150就和19再换个位置，同理150和100换位置。因为add和树的高度有关，所以时间复杂度是logN
pop O(logN)
- pop 和add是同一个道理，把100删掉，然后把7（最后一个node）放到第一个，但是7当大王显然不太合适，然后交换36和7，再交换25和7
- 也是和高度相关，所以是log n
- 
remove 理论上可以 O(logN) PriorityQueue 原生支持 O(N)
# 排序类问题
## Quick Sort 快排
### 快排的思想
1. 选取基准数 (pivot)
2. 将数组分割成两部分，长度不一定相等（partition） （算法核心），使得数组的左边小于等于数组的右边
3. 对左右两部分数组分别排序（递归）
### Partition - 如何把数组分成两部分
- 两个指针，分别指向当前数组的头和尾
- 移动左边的指针，直到左边指针指向的数字 >= 基准数 pivot
- 移动右边的指针，直到右边指针指向的数字小于等于基准数pivot
- 回到第二步，直到两个指针相遇
### Time Complexity:
所以是 O(NlogN)
```python
def quick_sort(A, start, end):
# 递归的出口
if start >= end:
return
# Partition
left, right = start, end
pivot = A[start + (end - start) // 2]
while left <= right:
while left <= right and A[left] < pivot:
left += 1
while left <= right and A[right] > pivot:
right -= 1
if left <= right:
A[left], A[right] = A[right], A[left]
left += 1
right -= 1
# 递归
quick_sort(A, start, right)
quick_sort(A, left, end)
```
### 快排变体：Quick Select
The Quick Select Algorithm is a selection algorithm to find the k-th smallest element in an unordered list. It is closely related to the Quicksort sorting algorithm. Here's the basic outline of how the Quickselect algorithm work.
**步骤：**
1. 选择pivot
2. 分区 partition
3. 选择
* 如果pivot的位置是k，返回pivot（因为它是第k个最小的元素）
* 如果k < pivot's index, 则递归地将算法应用于数组左侧
* 如果k > pivot's index, 则递归地将算法应用于数组的右侧
4. 重复步骤1-3，直到pivot的位置在k
例题：[215. Kth Largest Element in an Array](https://leetcode.com/problems/kth-largest-element-in-an-array/description/)
**时间复杂度分析**
- 算法通过枢轴至少排除了数组中的一部分元素。在平均情况下，枢轴会大致将数组分为等分，这意味着每次递归处理的元素数量大约是上一次的一半。
- 因此，第一次递归处理 n 个元素，下一次大约是 n/2，再下一次是 n/4，以此类推。这产生了一个序列 n, n/2, n/4, ..., 直到找到第 k 大的元素。
- 这个序列的和是一个几何级数，其总和接近 2n。因此，算法的平均时间复杂度是 O(n)。
----
# Greedy 贪心算法
# DP 动态规划
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，**这一点就区分于贪心**，贪心没有状态推导，而是从局部直接选最优的，
在**[关于贪心算法，你该了解这些！ (opens new window)](https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html)**中有一个背包问题的例子。
例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。**每件物品只能用一次**，求解将哪些物品装入背包里物品价值总和最大。
**动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。**
但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。
所以贪心解决不了动态规划的问题。
## 三种适用dp的场景
* 求可行性
* dp[]的值是true/false
* dp[大问题] = dp[小问题1] or dp[小问题2] or ...
* 代码通常用 for 小问题 if dp[小问题] == true then break 的形式实现（找到一个true就跑）
* 记忆化搜索例题
* [139 Word Break](https://leetcode.com/problems/word-break/description/)
* [140 Word Break ii](https://leetcode.com/problems/word-break-ii/)
* [44 Wildcard Matching](https://leetcode.com/problems/wildcard-matching/)
* 求方案数
* dp[]的值的类型是方案数（整数）
* $dp[大问题] = \sum(dp[小问题1]，dp[小问题2]，dp[小问题3]，...)$
* $\sum = sum$
*
* 求最值
* dp[]的值的类型是最优值的类型
* dp[大问题] = max{dp[小问题1]，dp[小问题2]，...}
* dp[大问题] = min{dp[小问题1]，dp[小问题2]，...}
## 动态规划的时间复杂度
= 记忆化搜索的时间复杂度
= O(状态总数 * 计算每个状态的时间耗费)
## 解题步骤
1. 确定dp数组（dp table） 以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
# 记忆化搜索
**DFS + Memo**
在函数返回钱，记录函数的返回结果。
在下一次以**同样参数**访问函数时直接返回记录下的结果。
**如何理解呢？**
路径A和路径B可能是有重复的，那在这种情况下，我们就不需要将路径B重新搜索一遍。
**深度优先搜索DFS + 记忆**
动态规划的两种实现方式：
1. 递归方式 => 记忆化搜索
2. 循环方式（下节课）
记忆化搜索就是动态规划的一种实现方式
动态规划的另一种实现方式是多重循环（下节课）
所以记忆化搜索就是动态规划
**记忆化搜索的函数的三个特点**
* 函数有**返回值**
* 返回结果和**输入参数**相关，和其他的全局状态无关
* 参数列表中传入哈希表或者其他用于记录计算结果的数据结构
# Bit Manipulation 位运算
## 位运算的概念
位运算是一种对整数在二进制层面上进行操作的算术方式。我们通常使用的运算，如加、减、乘、除，是在更高的抽象层次上对数字进行操作。而位运算则是直接操纵整数的二进制位。在编程中，位运算因为其速度快和直接操作硬件的能力而被广泛使用。
了解位运算之前，需要先知道整数在计算机中是如何表示的。计算机使用二进制来存储和处理数据。例如，十进制的数字3，在8位二进制中表示为 00000011。
1. 按位与 (AND) - `&`
* 只有两个对应位中有一个是1，结果才是1
* `0101 & 0011 => 0001`
2. 按位或（OR） - `|`
* 只要两个对应位中有一个是1，结果就是1
* `0101 & 0011 => 0111`
3. 按位异或 (XOR) - `^`
* 当两个对应位不相同的时候，结果位是1；相同的时候结果位是0.
* 例如：`0101 ^ 0011 => 0110`
* 异或运算有一个有趣的性质：任何数与自己异或的结果为0，与0异或是其自身。
4. 按位取反（NOT） - `~`
* 对数字的每一位取反，即将1变为0，将0变为1。
* 例如：``~0101 的结果是 1010`（实际上，由于计算机中整数通常有符号，这里还涉及到补码表示，所以真实结果可能不同）。
5. 左移（Left Shift） - `<<`
* 将一个数的所有位向左移动指定的位数，右边空出的位用0填充。
* 例如：`0101 << 1 的结果是 1010`。
* 左移一位的操作相当于乘以2。
6. 右移（Right Shift） - >>
* 分为逻辑右移和算术右移，逻辑右移在左边空出的位用0填充，算术右移则填充最左边的位（通常是符号位）。
* 例如：`0101 >> 1（逻辑右移）的结果是 0010`。
* 右移一位的操作相当于除以2。
## 原码 补码 反码
* 原码（True Form）：
原码是指一个二进制数直接按照正负号和大小写成的码，最高位是符号位，0表示正数，1表示负数，其余位表示数值大小。
* 反码（One's Complement）：
反码是对二进制数的每一位取反。对于正数，反码与原码相同；对于负数，除符号位外，其余每一位都取反。
* 补码的定义：
* 正数的补码是其二进制表示，最左边的位（称为最高位）是0。
* 负数的补码是在正数的基础上，取反（将每一位的0变为1，1变为0）后加1。
* 为什么需要补码？
为了简化加法和减法的电路设计，使得负数的加法和减法可以和正数相同。
避免有两个0，+0 和 -0 的情况，补码只有1个0的表示
假设我们要计算 `-5 + 3`
1. `+5` 的二进制原码是 `00000101`，补码也是 `00000101`。
2. `-5` 的二进制补码是 `+5` 的补码取反后加1，即 `11111011`。
3. `+3` 的二进制原码是 `00000011`，补码也是 `00000011`。
现在，我们直接对 `-5` 和 `+3` 的补码进行二进制加法运算：
```plaintext
11111011
+ 00000011
-----------
11111110
```
结果 `11111110` 是一个补码，它表示的是一个负数（因为最高位是1）。我们将其转换回十进制来验证结果：
1. 先不考虑符号位，取反得到`000000001`
2. 然后加1，得到`00000010`，也就是10进制的2
3. 加上负号，因此补码`11111110`表示的是`-2`
减法示例：
同样地，减法可以用加上一个数的相反数来实现。例如，5 - 3 可以写为 5 + (-3)。
+5 的二进制原码是 00000101，补码也是 00000101。
-3 的二进制原码是 00000011，其补码是 11111101。
```plaintext
00000101
+ 11111101
-----------
1 00000010 （最左边的1是溢出位，并不计入结果中）
```
## 位运算的相关题目
[Leetcode 191. NUmber of 1 Bits](https://leetcode.com/problems/number-of-1-bits/description/)
[B站讲解LC191](https://www.bilibili.com/video/BV1YT4y117AH?p=4&vd_source=092a4adfeea57cb27dfef99636cca9f0)
# 单调栈
**Definition:** 单调栈是一种特殊的栈，栈内元素按照一定的顺序（递增或递减）排列。
**我怎么能想到用单调栈呢？ 什么时候用单调栈呢？**
通常是一维数组，**要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了**。
单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。
更直白来说，**就是用一个栈来记录我们遍历过的元素**，因为我们遍历数组的时候，我们不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以我们需要用一个容器（这里用单调栈）来记录我们遍历过的元素。
## 递增栈/递减栈
使用单调栈有三个判断条件：
* 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
* 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
* 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
**把这三种情况分析清楚了，也就理解透彻了。**
接下来我们用`temperatures = [73, 74, 75, 71, 71, 72, 76, 73]`为例来逐步分析，输出应该是 `[1, 1, 4, 2, 1, 1, 0, 0]`。
Sign in with Wallet
Connect another wallet