算法学习笔记
算法学习笔记
算法小技巧
1. 判断区间满足要求个数
总共分为三种情况：
- 闭区间
[l,r]：res=r-l+1- 左开右闭
(l,r]，左闭右开[l,r)：res=r-l- 左开右开
(l,r)：res=r-l-1
2.map判断不同key个数
unordered_map<int,int> cnt;
cnt[nums[r]]++;
if(cnt.size()>=k)//如果哈希表中不同元素个数>=k进行操作。
res=max(res,temp);//满足条件操作。
if(--cnt[nums[l]]==0)//如果删除后为0，移除这个key
cnt.erase(num[l]);3.位运算技巧
如果一个数
x与另一个数y按位与(&)的值为0（前提），另一个数与他们(|)按位或的值相与为0，那么同时也和数x数y按位与为0。同时如果想减去一个值，可以直接减去，也可以对他们或的值异或(^)想要减去的值x&y==0 z=x|y 若有a&z==0 则a&x==0 且a&y==0 若想恢复某一个值 有y=z^x x=z^y
4.快速转换大小写
利用字母异或上32即可完成大小写转换。再次异或上32恢复
5. 可排序容器中获取最大最小值
在c++可排序的容器中map,set,muiltset,muiltimap，
set可以使用*s.begin()以及*s.rbegin()获取最大和最小值。map使用
*m.begin()->first以及*m.rbegin()->first
6.循环数组的处理
for (int i = 0; i < 2 * n; i++) {
int current = nums[i % n]; // 循环处理数组
// 只在第一次遇到该元素时，才将其压入栈中
if (i < n) {
//进行操作
}
}7.整数向上取整
a/b向上取整，等价于(a+b-1)/b;
8.负数取余
如果
a是一个负数，取余对其映射到正数(a%k+k)%k
9.vector去重
vector<int> vec = {1, 3, 2, 3, 1, 4, 2};
// 方法1：最常用的方法
void removeDuplicates(vector<int>& vec) {
// 1. 先排序
sort(vec.begin(), vec.end());
// 2. 使用unique获取不重复区间的末尾
// 3. 使用erase删除重复元素
vec.erase(unique(vec.begin(), vec.end()), vec.end());
}10.堆定义
// 方式2：自定义结构体
struct Node {
int dist, id;
bool operator > (const Node& w) const {
return dist > w.dist;
}
};
priority_queue<Node, vector<Node>, greater<Node>> heap;//小跟堆1.基础算法
排序
快速排序
主要步骤：
- 确定分界点：一般采用
partial=nums[l],partial=nums[(l+r)/2],partial=nums[r],随机（partial=l + rand() % (r - l + 1);）。- 调整范围：保证分界点左边的数一定
<=partial，分界点右边的数一定>=partial- 递归左右两端（不包括
partial因为此时它已经在正确位置上）
//随机模板
void quick_sort(vector<int>& nums, int l, int r) {
// 基本条件：如果左指针大于或等于右指针，返回
if (l >= r) return;
// 随机选择枢轴，防止极端情况下性能退化
int i = l + rand() % (r - l + 1);
// 将随机选择的枢轴元素与最左边的元素交换
swap(nums[l], nums[i]);
// 将最左边的元素（现为随机选择的枢轴元素）作为枢轴
int pivot = nums[l];
// 初始化左右指针
int left = l, right = r;
// 循环将元素重新排序，使得枢轴左边的元素小于或等于枢轴，右边的元素大于或等于枢轴
while (left < right) {
// 从右向左寻找小于枢轴的元素
while (left < right && nums[right] >= pivot) right--;
// 将右指针位置的元素移动到左指针位置
nums[left] = nums[right];
// 从左向右寻找大于枢轴的元素
while (left < right && nums[left] <= pivot) left++;
// 将左指针位置的元素移动到右指针位置
nums[right] = nums[left];
}
// 将枢轴元素放回正确位置
nums[left] = pivot;
// 递归对枢轴左边的子数组进行排序
quick_sort(nums, l, left - 1);
// 递归对枢轴右边的子数组进行排序
quick_sort(nums, left + 1, r);
}归并排序
主要步骤：（以空间换时间，需要一个辅助数组）
- 确定分界点：
mid=l+(r-l)/2;- 递归排序左右两段
- 将排好序左右两段合二为一
// 归并排序函数
void merge_sort(vector<int>& nums, int l, int r, vector<int>& temp) {
// 终止条件：如果左指针大于或等于右指针，返回
if (l >= r) return;
// 计算中间索引
int mid = l + (r - l) / 2;
// 递归对左半部分进行排序
merge_sort(nums, l, mid, temp);
// 递归对右半部分进行排序
merge_sort(nums, mid + 1, r, temp);
// 初始化临时数组的索引，以及左右半部分的起始索引
int k = 0, i = l, j = mid + 1;
// 合并两个有序子数组
while (i <= mid && j <= r) {
// 将较小的元素放入临时数组
if (nums[i] <= nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 拷贝左半部分剩余的元素到临时数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 拷贝右半部分剩余的元素到临时数组
while (j <= r) {
temp[k++] = nums[j++];
}
// 将临时数组中的元素拷贝回原数组
for (i = l, j = 0; i <= r; i++, j++) {
nums[i] = temp[j];
}
}堆排序
定义：
堆排序是一种基于比较的排序算法，它利用了二叉堆这一数据结构来实现。分为大根堆和小跟堆。
主要步骤（以小跟堆为例子）：
- down（下沉）：当前位置的元素必须满足，大根堆（根>=左右孩子）小跟堆（根<=左右孩子）检查当前位置元素是否满足要求，如果不满足，将当前位置元素跟左右孩子中最小的一个交换位置。之后继续下沉。
- up（上浮）：该操作主要用于插入元素，插入元素后，将该元素跟他的父节点比较即可，因为左兄弟一定满足条件左>=父,因此仅考虑当前插入元素与父元素关系。如果当前元素小于父元素，那么需要交换当前元素与父元素，之后不断的上浮。上浮过程仅需要跟父元素对比即可。
- 建堆：从
n/2开始，对每个节点进行下沉操作，直到第一个元素下沉操作完成。代表建堆完成。- 排序：将最顶部元素跟最底部元素交换，缩小堆的大小，然后不断下沉顶部元素。直到堆的大小为
1应用
- 得到升序序列：将大根堆排序，即最大元素沉底
- 得到降序序列：将小跟堆排序，即最小元素沉底
操作：
- 插入一个数：heap[ ++ size] = x; up(size);
- 获取最小值：heap[1];
- 删除最小值：heap[1] = heap[size]; szie -- ; down(1);
- 删除任意一个元素：heap[k] = heap[size]; size -- ; down(k); up(k);
- 修改任意一个元素：heap[k] = x; down(k); up(k);
class Solution {
public:
// 函数将元素下沉到适当的位置以维持大根堆的性质
void down(int x, vector<int> &nums, int n) {
int t = x; // t记录当前节点位置
// 比较当前节点和左子节点，选择较小的节点
if (2 * x + 1 < n && nums[t] < nums[2 * x + 1]) t = 2 * x + 1;//小根堆仅需将<变为>即可
// 比较当前节点和右子节点，选择较小的节点
if (2 * x + 2 < n && nums[t] < nums[2 * x + 2]) t = 2 * x + 2;
// 如果当前节点不是最小节点，则交换并递归调用down函数
if (t != x) {
swap(nums[t], nums[x]);
down(t, nums, n);
}
}
void up(int u,vector<int> &nums){
//下标从1开始为u/2,如果从0开始为(u-1)/2;
while(u/2&&nums[u/2]>nums[u]){
swap(nums[u/2],nums[u]);
u=u/2;
}
}
// 堆排序函数
vector<int> sortArray(vector<int>& nums) {
int n = nums.size();
// 构建最小堆
for (int i = n / 2; i >= 0; i--)
down(i, nums, n);
// 逐步将堆顶元素移除并重新调整堆
for (int i = n - 1; i >= 1; i--) {
swap(nums[0], nums[i]); // 将堆顶元素与堆的最后一个元素交换
down(0, nums, i); // 调整新的堆顶元素位置
}
return res;
}
void insert(vector<int> &nums,int val){
nums.push_back(val);// 插入元素到数组末尾
up(nums.size()-1,nums); // 调用上浮函数调整堆
}
};TopK 问题
取数组中最大的 K 个元素 / 第 K 大元素 一般的做法有两种 1.使用快排的思路进行快速选择 2.使用小根堆维护K个
class Solution {
public:
int quickSelect(vector<int> &nums,int L,int R,int k){
if(L>=R)return nums[L];
//选择枢轴
int pivot_idx = rand() % (R - L + 1) + L;
int pivot = nums[pivot_idx];
int lt = L, gt = R, i= L;
//L,lt-1 <pivot
//lt,i-1 ==pivot
// i gt 未知
// gt+1, R >pivot
while(i<=gt){
if(nums[i]<pivot)swap(nums[i++],nums[lt++]);
else if(nums[i]>pivot)swap(nums[i],nums[gt--]);//由于gt位置的元素由于处于未知区间，因此不能确定 所以收缩区间不能移动i
else i++;
}
int cntGreater = R - gt; // > pivot 的数量（右段）
int cntGE = R - lt + 1; // >= pivot 的数量（右段 + 等号段）
//查看每段的个数
if(k<=cntGreater)return quickSelect(nums,gt+1,R,k);
//处于small里面 k> R-LT+1
if(k>cntGE)return quickSelect(nums,L,lt-1,k-cntGE);
return pivot;
}
int findKthLargest(vector<int>& nums, int k) {
return quickSelect(nums,0,nums.size()-1,k);
}
};查找
二分查找
lower_bound(vector<int> &nums,int target)：寻找数组中第一个大于等于target的位置。
upper_bound(vector<int> &nums,int target)：寻找数组中第一个大于target的位置。
理解：想要理解二分法，就要明白二分法的精髓在于循环不变量也就是不管循环前后。代表的意义均不发生改变。大致可以将二分法分为三种。同时需要保证
[0-left],[left,right],[right,nums.size()-1]前后两个区间的开闭，是由中间[left,right]这个区间决定的。同时这三个区间需要涵盖整个数组。决定了开闭之后。即定义了循环不变量。需要时刻保证循环不变量的正确性。
左闭右闭区间
[left,right]：应用此区间。那么对于左区间即为
[0,left)->等价为[0,left-1],右区间为(right,nums.size()-1]。此时即可定义循环 不变量为：left左边一定小于target.right右边一定大于等于target。
nums[left-1]<targetnums[right+1]>=target当出现
nums[mid]==target时。按照循环不变量的定义此时应该更新right=mid-1。才满足right的右边一定大于等于target最后当循环条件
while(left<=right)不满足后。也就是当left=right+1后退出循环。此时left指向第一个大于等于target元素。左闭右开区间
[left,right)：此区间。对于左区间为
[0,left)，右区间为[right,nums.size()).此时循环不变量为。left左边一定小于target.right以及right右边一定大于等于target.
nums[left-1]<targetnums[right]>=target当出现
nums[mid]==target时，此时按照循环不变量定义。应该更新right=mid.才满足right以及right右边一定大于等于target最后当循环条件
while(left<right)不满足时。也就是当left=right时退出循环。此时left指向第一个大于等于target元素。左开右闭区间
(left,right]:此区间在计算
mid时候，需要写成（left+right+1)/2;否则会死循环。左开右开区间
(left,right)：此区间。对于左区间为
[0,left]，右区间为[right,nums.size()).此时循环不变量为。left以及left左边一定小于target.right以及right右边一定大于等于target.
nums[left]<targetnums[right]>=target当出现
nums[mid]==target时，此时按照循环不变量定义。应该更新right=mid.才满足right以及right右边一定大于等于target最后当循环条件
while(left+1<right)不满足时。也就是当left+1=right时退出循环。此时right指向第一个大于等于target元素。😈注：二分法的最后答案结果，不一定在区间内，有可能在区间外。
🍎四种情况转换（
>,>=,<,<=）查找第一个大于目标值的位置 (
>)：
- 使用
upper_bound。同样也可以使用lower_bound(val+1)查找第一个大于或等于目标值的位置 (
>=)：
- 使用
lower_bound。或者upper_bound(val-1)查找第一个小于目标值的位置 (
<)：
- 使用
lower_bound，然后减一。或者lower_bound(val-1)查找第一个小于或等于目标值的位置 (
<=)：
- 使用
upper_bound，然后减一。或者upper_bound(val - 1)
//左闭右闭区间 [left, right]
/**nums[left-1] < target
nums[right+1] >= target**/
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return left; // 此时 left 指向第一个大于等于 target 的元素或者right+1
}
/**
左闭右开区间 [left, right)
nums[left-1] < target
nums[right] >= target
**/
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid + 1;
else
right = mid;
}
return left; // 此时 left 指向第一个大于等于 target 的元素或者right
}
/**
左开右闭区间 (left, right]
nums[left] < target
nums[right+1] >= target
**/
int binarySearch(vector<int>& nums, int target) {
int left = -1, right = nums.size()-1;
while (left < right) {
int mid = left + (right - left+1) / 2;
if (nums[mid] < target)
left = mid;
else
right = mid-1;
}
return left+1; // 此时 right+1 指向第一个大于等于 target 的元素或者left+1(结束条件为left==right)
}
/**
左开右开区间 (left, right)
nums[left] < target
nums[right] >= target
**/
int binarySearch(vector<int>& nums, int target) {
int left = -1, right = nums.size();
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target)
left = mid;
else
right = mid;
}
return right; // 此时 right 指向第一个大于等于 target 的元素,或者left+1
}高进度
两数相加
主要步骤：正整数需要经过处理将个位放在前面，高位放在后面，便于处理。，从个位开始累加，记录是否进位
初始化：
定义一个空的
vector<int>类型的res用来存储相加后的结果。使用
int carray = 0来表示当前的进位，初始为 0。逐位相加：
使用
for循环遍历A和B的每一位，直到A和B的所有位都处理完毕。如果当前位在
A中存在，则将其加到carray。如果当前位在
B中存在，则将其加到carray。计算当前位的结果（
carray % 10）并将其加入res中。更新
carray为carray / 10，表示进位。
- 处理最后的进位：
- 循环结束后，如果
carray不为 0，则将其加入res，表示最高位的进位。
vector<int> add(vector<int> &A,vector<int> &B){
vector<int> res;
for(int i=0,carray=0;i<A.size()||i<B.size()||carray;i++){
if(i<A.size()) carray+=A[i];
if(i<B.size()) carray+=B[i];
res.push_back(carray%10);
carray/=10;
}
return res;
}两数相减
主要步骤：实现为两个正整数相减，如果有负数，仅需要处理后调用即可。正整数需要经过处理将个位放在前面，高位放在后面，便于处理。
sub函数中一定要保证num1>=num2。可实现一个com函数来判断num1是否大于等于num2
sub函数思路：逐位减法：
- 从低位到高位逐位相减。
- 如果当前位减法结果小于0，需要向高位借1。
- 使用变量
t来表示借位，如果t为1，表示需要借位。处理借位：
- 如果当前位
curr小于0，则需要借位，并加上10。- 更新
t为0或1，表示下一位是否需要借位。移除前导零：
- 最终结果中可能会有前导零，需要移除。
- 如果结果只有一位，不能移除。
//判断当前是否有num1>=num2
bool com(vector<int> &num1,vector<int> &num2){
if(num1.size()!=num2.size())
return num1.size()>num2.size();
else
for(int i=0;i<num1.size();i++)
if(num1[i]!=num2[i])
return num1[i]>num2[i];
return true;
}
vector<int> sub(vector<int> &num1, vector<int> &num2) {
vector<int> res;
int t = 0; // 用于处理借位
for (int i = 0; i < num1.size(); i++) {
int curr = num1[i] - t; // 当前位减去借位
if (i < num2.size()) {
curr -= num2[i]; // 减去对应位的 num2 值
}
t = curr < 0 ? 1 : 0; // 如果当前位小于 0，表示需要借位
res.push_back((curr + 10) % 10); // 保证结果在 0-9 之间
}
// 移除前导零
while (res.size() > 1 && res.back() == 0) {
res.pop_back();
}
return res;
}两数相乘
主要步骤
vector<int> mul(vector<int> &A,int B){
vector<int> res;
for(int i=0,carray=0;i<A.size()||carray;i++){
if(i<A.size()) carrya+=A[i]*B;
res.push_back(carray%10);
carray/=10;
}
return res;
}两数相除
主要思路：用一个
r模拟商了之后的余数。r=r*10+A[i]表示下一位的数相除。最后由于是将商的第一位放在开头位置。我们需要反转一下。由于第一位可能商零，需要移除前导零。
初始化：
- 定义结果向量
res和余数r。逐位处理：
从高位到低位遍历
A的每一位。更新余数
r并计算商，将商加入res。反转结果：
- 反转
res使其按正确顺序排列。移除前导零：
- 移除
res中的前导零，确保结果正确。
vector<int> div(vector<int> &A,int B){
vector<int> res;
int r=0;//定义一个余数
for(int i=A.size()-1;i>=0;i--){
r=r*10+A[i];
res.push_back(r%B);
r/=B;
}
reverse(A.begin(),A.end());
//移除前导零
while(A.size()>1&&A.back()==0)res.pop_back();
}前缀和与差分
前缀和
利用一个额外的数组来记录前
i个数的和。注：前缀和一般定义为从1开始。s[0]=0这样做的好处是可以统一公式。如果left=0，要计算的子数组是一个前缀（从a[0]到a[right]），我们要用s[right+1]减去s[0]。如果不定义s[0]=0，就必须特判left=0的情况了。（画图分析即可）
一维前缀和：
定义：一维前缀和数组
s[i]表示数组a的前i个元素的和。计算公式：
s[i] = s[i-1] + a[i-1]，其中s[0] = 0。（🐶 注意：实际中将前缀和数组扩大1，定义为s[i+1]表示为s[i+1]=a[0]+a[1]+......a[i]。公式为s[i+1]=s[i]+a[i]区间和为[l,r]定义：s[r+1]-s[l]）区间和查询：若要求区间
[l, r]的元素和，可以使用s[r] - s[l-1]二维前缀和（以当前点到最左上角点所构成矩阵中元素的总和）：
- 定义：二维前缀和数组
s[i][j]表示矩阵a中从(0, 0)到(i, j)所有元素的和。- 计算公式：
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j]。- 区间和查询：若要求矩阵中子矩阵
(x1, y1)到(x2, y2)的元素和，可以使用公式sum = s[x2][y2] - s[x2][y1-1] - s[x1-1][y2] + s[x1-1][y1-1]🐰 注意：在实际中，我们通常会将二维的前缀和矩阵多增加一行一列，定义为
s[i+1][j+1]表示左上角为a[0][0]，右下角为a[i][j]的子矩阵元素和（将前缀和矩阵整体向右下移动一行一列），这样做可以避免单独处理第一行和第一列元素和
//一维前缀和
// 一维前缀和
class NumArray {
public:
vector<int> s; // 用于存储前缀和的数组
// 构造函数，初始化前缀和数组
NumArray(vector<int>& nums) {
s.resize(nums.size() + 1, 0); // 前缀和数组大小为nums.size() + 1，并初始化为0
for (int i = 0; i < nums.size(); i++) {
s[i + 1] = s[i] + nums[i]; // 计算前缀和
}
}
//s[i+1]`表示为`s[i+1]=a[0]+a[1]+......a[i]
// 计算区间[left, right]的和
int sumRange(int left, int right) {
return s[right + 1] - s[left]; // 区间和为前缀和数组的差
}
};
class NumMatrix {
public:
vector<vector<long long>> s;
NumMatrix(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
s.resize(m + 1, vector<long long>(n + 1, 0));
// 初始化前缀和数组
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
s[i+1][j+1] = (long long)(s[i ][j+1] + s[i+1][j ] - s[i ][j ] + matrix[i ][j ]);
}
}
// 初始化前缀和数组
/**for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
s[i][j] = (long long)(s[i-1 ][j] + s[i][j-1 ] - s[i-1 ][j-1 ] + matrix[i-1 ][j-1]);
}
}**/
}
//数组下标从0开始，我们初始化的前缀和数组是从1开始的，因此需要将下标都加1才符合前缀和。
int sumRegion(int row1, int col1, int row2, int col2) {
return s[row2 + 1][col2 + 1] - s[row2 + 1][col1] - s[row1][col2 + 1] + s[row1][col1];
}
};
差分
[!NOTE]
以下为一维差分数组
差分数组是一种高效处理区间更新问题的工具。它通过记录数组相邻元素之间的差值，能够在常数时间内完成区间更新操作。
差分和前缀和是相互的逆运算。
假设有一个数组
a，其长度为n。差分数组diff的定义如下：
diff[1] = a[1]
diff[i] = a[i] - a[i-1]（对于2 <= i <= n）
a中每个元素a[i]=diff[1]+diff[2]+diff[3]+.....+diff[i]差分数组作用：用于对原数组进行区间更新。
要对区间
[l, r]的元素全部加上一个值c，只需要进行以下操作：diff[l] += cdiff[r+1] -= c（如果r+1在数组范围内）解释：
diff[l] += c相当于给a数组区间[l,n]的元素均加了c因此我们需要对[r+1,n]的元素减去一个c即diff[r+1] -= c
- 最终累加差分数组
diff可以得到更新后的原数组a。关键点：
差分数组初始化：
差分数组初始化可以理解为，将原来数组看做为元素全为0，因此差分为0，但实际上不为0，因此我们需要再每个
[i,i]区间加上a[i].最终形成的即为差分数组。插入操作：
diff[l] += c, diff[r + 1] -= c最终累加差分数组
diff可以得到更新后的原数组a对于下标从0开始的情况，我们仅需定义
diff数组长度为n+1即可，如果下标从1开始，那么我们需要定义diff数组长度为n+2。两种情况，统一定义为n+2
[!NOTE]
以下为二维差分
二维差分矩阵代表的含义是将原矩阵的增加或减少变为差分矩阵中仅4个点的改变。
二维差分矩阵核心操作：
初始化：初始化将原矩阵看做是都为0，但实际上不是，因此我们需要在
(i,j)到(i,j)区域，也就是每个点插入原矩阵的值a[i][j].插入值的改变：当二维差分矩阵中某一个点发生了变化，那么前缀和（原数组元素）包含该点的均会发生变化。因此我们需要一共操作四个点
diff[x1][y1] += c;
diff[x1][y2 + 1] -= c;
diff[x2 + 1][y1] -= c;
diff[x2 + 1][y2 + 1] += c;又因为在实际中我们会处理各种边界情况，因此一般将
diff数组扩大两行两列，也就是实际上从（1,1）开始
diff[x1+1][y1+1] += c;
diff[x1+1][y2 + 2] -= c;
diff[x2 + 2][y1+1] -= c;
diff[x2 + 2][y2 + 2] += c;如何还原原数组的值？
- 利用差分矩阵还原。差分矩阵前缀和即表示原数组元素
a[i][j]即a[i][j]等于从(0,0)点到(i,j)的前缀和。将所有diff相加即可还原.即diff[i][j] += diff[i][j - 1] + diff[i - 1][j] - diff[i - 1][j - 1];此时的diff[i][j]即为修改过后原数组元素a[i][j]- 利用前缀和，二维前缀和定义为
n+1*n+1可以避免处理边界。此时计算s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+diff[i][j]。由此也可还原。s[i+1][j+1]表示左上角为diff[0][0]，右下角为diff[i][j]的子矩阵元素和.即原数组a[i][j]
位运算
主要包含：
与（&）：有0为0，无0为1
或（|）：有1为1，无1为0
非（~取反）：
~0=1,~1=0异或（^）：相同为0，不同为1
左移（<<）:末尾补0，等同于乘2
右移（>>）:开头补0，等同于除2
- 常用操作：
- 求 x 的第 k 位数字 x >> k & 1
- lowbit(x) = x & -x，返回 x 的最后一位 1
位运算跟集合
| 术语 | 集合 | 位运算 | 集合示例 | 位运算示例 |
|---|---|---|---|---|
| 交集 | ( A | a & b | 1101 & 0111 = 0101 | |
| 并集 | ( A | a | b | 1101 | 0111 = 1111 | |
| 对称差 | ( A | a ⊕ b | ({0, 2, 3} | 1101 ⊕ 0111 = 1010 |
| 差 | ( A | a & ~b | ({0, 2, 3} | 1101 & 1001 = 1001 |
| 差（子集） | ( A | a ⊕ b | ({0, 2, 3} | 1101 ⊕ 0101 = 1000 |
| 包含于 | ( A | a & b = a | a | b = b | ({0, 2} | 0101 & 1101 = 01010101 | 1101 = 1101 |
- 集合跟元素
| 术语 | 集合 | 位运算 | 集合示例 | 位运算示例 |
|---|---|---|---|---|
| 空集 | $$\emptyset$$ | 0 | ||
| 单元素集合 | $${i}$$ | $$1 << i$$ | $${2}$$ | $$1 << 2$$ |
| 全集 | $$U = {0, 1, 2, \cdots, n-1}$$ | $$(1 << n) - 1$$ | $${0, 1, 2, 3}$$ | $$(1 << 4) - 1$$ |
| 补集 | $$C_U S = U \setminus S$$ | $$((1 << n) - 1) \oplus s$$ | $$U = {0, 1, 2, 3} \ C_U {1, 2} = {0, 3}$$ | $$1111 \oplus 0110 = 1001$$ |
| 属于 | $$i \in S$$ | $$ (s >> i) & 1 = 1$$ | $$2 \in {0, 2, 3}$$ | $$(1101 >> 2) & 1 = 1$$ |
| 不属于 | $$i \notin S$$ | $$(s >> i) & 1 = 0$$ | $$1 \notin {0, 2, 3}$$ | $$(1101 >> 1) & 1 = 0$$ |
| 添加元素 | $$S \cup {i}$$ | $$s | (1 << i)$$ | $${0, 3} \cup {2}$$ |
| 删除元素 | $$S \setminus {i}$$ | $$s & \sim (1 << i)$$ | $${0, 2, 3} \setminus {2}$$ | $$1101 & \sim (1 << 2)$$ |
| 删除元素（一定在集合中） | $$S \setminus {i}, i \in S$$ | $$s \oplus (1 << i)$$ | $${0, 2, 3} \setminus {2}$$ | $$1101 \oplus (1 << 2)$$ |
| 删除最小元素 | $$s & (s - 1)$$ |
- 常用的技巧
- 遍历集合
//设元素范围从0~n-1,枚举范围中的元素i，判断i是否在集合s中。
for (int i = 0; i < n; i++) {
if ((s >> i) & 1) { // i 在 s 中
// 处理 i 的逻辑
}
}
//或者遍历集合中元素，不断地计算集合最小元素、去掉最小元素，直到集合为空
for (int t = s; t; t &= t - 1) {
int i = __builtin_ctz(t);
// 处理 i 的逻辑
}- 枚举集合
//设元素范围从0到n-1，从空集枚举到全集U
for (int s = 0; s < (1 << n); s++) {
// 处理 s 的逻辑
}- 枚举非空子集
//设集合为s从大到小枚举 s的所有非空子集 sub
for (int sub = s; sub; sub = (sub - 1) & s) {
// 处理 sub 的逻辑
}- 枚举子集（包含空集）
//如果要从大到小枚举s的所有子集sub(从s枚举到空集）
int sub = s;
do {
// 处理 sub 的逻辑
sub = (sub - 1) & s;
} while (sub != s);- 统计集合中元素个数
for(int t=s;t;t-=t&(-t))
cnt++;双指针
总结：
对于排序后的数组可以使用双向指针。
快慢指针
滑动窗口：使用两个指针
l以及r来维护一个满足题目要求的闭区间窗口[l,r]窗口内元素是连续的。枚举右端点，当右端点移动后，不满足条件时，移动左端点到满足条件为止。思路：以右指针作为驱动，拖着左指针向前走。右指针每次只移动一步，而左指针在内部 while 循环中每次可能移动多步。右指针是主动前移，探索未知的新区域；左指针是被迫移动，负责寻找满足题意的区间。
链表合并
//模板
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}离散化
思路：
步骤：
- 存储所有待离散化的值
vector<int> alls;
将所有值排序
sort(alls.begin(), alls.end());去掉重复元素
alls.erase(unique(alls.begin(), alls.end()), alls.end());二分求出x对应的离散化的值。（找到第一个大于等于x的位置）
int lower_bound(vector<int> &alls,int x){ //定义为左开右开区间。 //nums[left]<x nums[right]>=x int left=-1,right=all.size(); int mid; while(left+1<right){ mid=left+(right-left)/2; if(alls[mid]<x) left=mid; else right=mid; } return right; }
区间合并
思路：
步骤：
- 按区间左端点排序
- 维护一个
st以及ed表示当前维护区间的左右端点。- 如果遇到另一个区间左端点小于等于当前区间
ed则合并，即更新当前维护区间的ed。- 若另一个区间左端点大于当前区间
ed。则将当前区间加入res
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
if (intervals.empty()) return {};
// 排序区间
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
int st = intervals[0][0], ed = intervals[0][1];
for (const auto& interval : intervals) {
if (interval[0] > ed) {
// 当前区间与之前的区间不重叠，保存之前的区间
res.push_back({st, ed});
// 更新起始和结束位置
st = interval[0];
ed = interval[1];
} else {
// 当前区间与之前的区间重叠，更新结束位置
ed = max(ed, interval[1]);
}
}
// 添加最后一个区间
res.push_back({st, ed});
return res;
}
};滑动窗口
- 定长滑动窗口
模板：
- 入：下标为
i的元素进入窗口，更新相关统计量。如果i<k−1则重复第一步。- 更新：更新答案。一般是更新最大值/最小值。
- 出：下标为
i−k+1的元素离开窗口，更新相关统计量。
//模板
int l=0,res=0;
int sum=0;
for(int r=0;r<n;r++){
sum+=arr[r];
//统计不同数量等
if(r<k-1)//窗口长度
continue;
res=max(res,sum);
//移除左边界
//移除数量为0的key等
sum-=arr[l++];
}- 不定长滑动窗口
模板：
- 移动：不断的移动右端点，当不满足条件时，移动左端点。
- 移除左端点：不满足条件时，移动左端点，处理逻辑可能是：统计次数（常用
map），计算总和等等。- 更新结果：更新结果位置不固定，可以在循环内部，也可以在循环外部。处理子数组个数，常用于循环外部。
res+=l
//不定长滑动窗口模板
class Solution {
public:
int findSubArray(vector<int>& nums, int k) {
int n = nums.size(); // 数组/字符串长度
int left = 0; // 左指针 表示当前遍历的区间[left, right]，闭区间
int sums = 0; // 用于统计 子数组/子区间 是否有效，根据题目可能会改成求和/计数
int res = 0; // 保存最大的满足题目要求的 子数组/子串 长度
for (int right = 0; right < n; ++right) { // 右指针遍历数组
sums += nums[right]; //增加当前右边指针的数字/字符的求和/计数
while (sums > k) { // 不符合题意: 此时需要一直移动左指针，直至找到一个符合题意的区间
sums -= nums[left]; // 移动左指针前需要从counter中减少left位置字符的求和/计数
left++; // 真正的移动左指针，注意不能跟上面一行代码写反
}
res = max(res, right - left + 1); // 结束时，我们找到了一个符合题意要求的 子数组/子串。
}
return res; // 返回满足条件的最长子数组长度
}
};树
后序遍历
从底部往上进行归，同时返回当前子树的状态给父节点，例如（当前子树高度，深度，是否为BST，最大值，最小值等等）一般可以使用
pair或者tuple进行返回。例子：98,1123
层序遍历（BFS）模板
一共两种模板，如果需要访问前一个元素，那么可以自定义队列实现，如果不需要，直接使用
queue即可
level = 0
while queue 不空：
level ++;
size = queue.size()
for(int i=0;i<size;i++){
auto temp=queue.front();
queue.pop();
//处理其他的逻辑
//加入左右孩子
if(tmep->left)queue.push(temp->left);
if(temp->right)queue.push(temp->right)''
}2.数据结构模拟
链表
单链表
思路：利用两个数组，
e[N]表示存放该节点的值，ne[N]表示存放该节点指向的下一个节点。idx表示下一个要插入节点下标。h指向第一个节点下标。定义空节点为-1
const int N = 100000;
int head, e[N], ne[N], idx;
void init(){
head=-1;
idx=0;
}
//在头结点插入元素
void add_at_head(int x){
e[idx]=x;
ne[idx]=head;
head=idx++;
}
//在第k个节点后插入
void add_at_k(int k,int x){
e[idx]=x;
ne[idx]=ne[k];
ne[k]=idx;
idx++;
}
//移除第k个元素
void remove(int k){
ne[k]=ne[ne[k]];
}双链表
思路：利用两个数组模拟左右指针。
l[N]表示左指针指向。r[N]表示右指针指向。初始化定义为0表示左边界，1表示右边界。因此实际存放位置从下标2开始。在第k个位置后插入元素，实际上是下标为k-1
const int N = 100000;
int l[N], r[N], e[N], idx;
// 初始化双向链表
void init() {
r[0] = 1; // 0,代表左边界
l[1] = 0; // 1，代表右边界
idx = 2; // 下一个插入的位置
}
// 在位置k后面插入一个数x
void add_at_k(int k, int x) {
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx;
idx++;
}
// 删除位置k的数
void remove(int k) {
l[r[k]] = l[k];
r[l[k]] = r[k];
}栈模拟
朴素栈
思路：利用数组加上一个
idx表示栈帧。定义从-1开始，-1代表为空
const int N = 10000;
int stk[N], idx = -1;
// 将元素压入栈
void push(int x) {
if (idx >= N - 1) {
// 栈满的情况下可以打印错误信息或者抛出异常
return;
} else {
stk[++idx] = x;
}
}
// 从栈顶弹出元素
void pop() {
if (idx >= 0) {
idx--;
}
}
// 获取栈顶元素
int get_top() {
if (idx < 0)
return -1; // 或者抛出异常
return stk[idx];
}单调栈
定义：一种基于栈的衍生物，栈中元素为单调递增或者单调递减。(栈中存储的为下标)
单调递增栈特征：
栈内的元素从栈底到栈顶单调不减。递减栈为单调不增
当遇到新的元素时，如果该元素小于等于栈顶元素，则需要将栈顶元素弹出，直到找到一个比该元素小的元素或栈为空。（递减栈：如果该元素大于等于栈顶元素，则需要将栈顶元素弹出，直到找到一个比该元素大的元素或栈为空。）
使用场景
- 查找数组中每个元素的下一个更大元素或下一个更小元素。
- 最大矩形面积问题。
- 柱状图中最大矩形面积问题。
//单调递增栈
const int N = 10000;
int stk[N], idx = -1;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
// 保持栈的单调递增性质
while (idx >= 0 && stk[idx] >= x) {
idx--;
}
// 将当前数字压入栈
stk[++idx] = x;
}
//递减栈
for (int i = 0; i < n; i++) {
int x;
cin >> x;
// 保持栈的单调递减性质
while (idx >= 0 && stk[idx] <= x) {
idx--;
}
// 将当前数字压入栈
stk[++idx] = x;
}队列
朴素队列
思路：数组+两个指针模拟队头队尾。定义
rear表示队尾元素下一个位置（下一个待插入的元素位置）。front表示队头元素位置。模拟循环队列关键点：
- 判空：
rear==front- 判满：
(rear+1)%N==front
const int N = 100000;
int front = 0, rear = 0, q[N];
// 判断队列是否已满
bool isFull() {
return (rear + 1) % N == front;
}
// 判断队列是否为空
bool isEmpty() {
return rear == front;
}
// 向队尾插入一个数
void enqueue(int x) {
if (!isFull()) {
q[rear] = x;
rear = (rear + 1) % N;
}
}
// 从队头弹出一个数
void dequeue() {
if (!isEmpty()) {
front = (front + 1) % N;
}
}
// 获取队头的值
int getFront() {
if (!isEmpty()) {
return q[front];
}
}单调队列
定义：特殊的队列数据结构，用于保持队列中的元素具有单调性。单调队列主要用于处理滑动窗口问题，其中需要在每个窗口中快速找到最大值或最小值。队列的元素为数组的下标
特征
- 单调递增队列：队列中的元素从队头到队尾单调递增，即队列中的每个元素都小于或等于其后面的元素。
- 单调递减队列：队列中的元素从队头到队尾单调递减，即队列中的每个元素都大于或等于其后面的元素。
使用场景
- 滑动窗口最大值或最小值问题。
- 在固定窗口内快速查找最值。
步骤（以下为单减）：
- 判断队头元素是否在滑动窗口内部。如果不在需要移除
- 判断队尾元素是否是小于等于
nums[i]，如果是，需要删除。
class Solution {
public:
static const int N = 10000;
int front = 0, rear = -1, q[N];
vector<int> maxInWindows(vector<int>& nums, int k) {
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
// 移除不在当前窗口的元素
while (front <= rear && q[front] < i - k+1) front++;
// 移除所有小于当前元素的元素以维持单调递减
while (front <= rear && nums[q[rear]] <= nums[i]) rear--;
// 将当前元素的下标加入队列
q[++rear] = i;
// 当窗口达到大小 k 时，记录最大值
if (i >= k - 1) res.push_back(nums[q[front]]);
}
return res;
}
};字符串匹配
kmp算法
思路：让主串和子串下标从1开始。
kmp模板题，牢记next数组含义，代表模式串以当前下标结尾的子串的最长公共前后缀长度。同时，给出定义，主串与模式串都在前面加一个哨兵空格，可以避免回退时-1next数组长度对应也要+1i与j的下一个元素进行匹配。也就是s[i]==p[j+1]。关键点
- 求
next数组：由于加了哨兵，因此实际上字符串下标从1开始。第一个字符最长公共前后缀长度为0即next[1]=0。求next数组i从2开始，j从0开始（因为要与j+1进行匹配p[i]==p[j+1]）。如果循环结束，当j退回为0，代表此时无法往后退了，j不移动，最长公共前后缀长度为0。如果匹配成功，j往前移动一位(j++)，代表当前以i结尾的最长公共前后缀长度为jkmp匹配过程：与求next数组类似，不过匹配的是主串与模式串（s[i]==p[j+1]）匹配成功j++,不成功退回到j的最长前后缀长度（j=next[j]）。最后如果j移动到末尾，也就是j==m那么代表匹配成功，第一个匹配成功字符位置为（i-j）（如果定义下标从0开始，那么为i-j+1）
//关键点，主串和模式串都加上哨兵，确保第一个字符从1开始。next数组长度也要+1
s.insert(s.begin(),' ');
p.insert(p.begin(),' ');
vector<int> next(m+1,0);
for(int i=2,j=0;i<=m;i++){
while(j&&p[i]!=p[j+1])j=next[j];
if(p[i]==p[j+1])j++;
next[i]=j;
}
for(int i=1,j=0;i<=n;i++){
while(j&&s[i]!=p[j+1])j=next[j];
if(s[i]==p[j+1])j++;
if(j==m){
//匹配成功
return i-j;
}
}
//不带哨兵情况。
next[0]=-1;
//j==-1代表无法再回退了。
for(int i=1,j=-1;i<m;i++){
while(j!=-1&&p[i]!=p[j+1])j=next[j];
if(p[i]==p[j+1])j++;
next[i]=j;
}
for(int i=0,j=-1;i<n;i++){
while(j!=-1&&s[i]!=p[j+1])j=next[j];
if(s[i]==p[j+1]) j++;
if(j==m-1){
return i-m+1;
}
}
next[m+1]//下标从1开始
next[1]=0;
for(int i=1;j=0;i<m;i++){
while(j&&p[i]!=p[j]){
j=next[j];
}
if(p[i]==p[j])
j++;
next[i+1]=j;
}trie树（字符串树）
概念
前缀树或查找树，是一种用于存储字符串数据集的树形数据结构。它能够高效地处理字符串的插入、查找和删除操作
定义
idx=0既表示根节点又表示空节点。根节点不包含任何字母，是所有字符串的起点。- 定义
cnt[N]为每个节点的标记。代表以当前节点（cnt[p]）结束字符串的个数具体过程
- 插入：
- 从根节点开始
p=0- 映射字符到数组下标
u=str[i]-‘a’- 查看该节点是否在字典树中存在，如果不存在将该节点插入树中。
- 移动到下一层节点。
- 最后标记以该节点为结尾的字符串个数加1
- 询问：
- 其他跟插入一样.
- 如果字典树中不存在该节点，返回-1，存在移动节点到该节点
- 返回以当前节点结尾的字符串个数。
// 将字符串str插入到字典树中
void insert(char str[]){
int p = 0; // 初始化当前节点为根节点，根节点的索引为0
for(int i = 0; str[i]; i++){ // 遍历字符串str中的每个字符
int u = str[i] - 'a'; // 将字符转换为0到25的数字，对应字母a到z
// 如果当前节点在字典树中没有指向该字符的子节点，则创建一个新的子节点
if(!son[p][u]){
son[p][u] = ++idx; // 为新创建的节点分配一个唯一的索引
}
p = son[p][u]; // 移动到子节点，继续插入操作
}
cnt[p]++; // 在字符串的最后一个字符对应的节点上增加计数
}
// 在字典树中查询字符串str的出现次数
int query(char str[]){
int p = 0; // 初始化当前节点为根节点
for(int i = 0; str[i]; i++){ // 遍历字符串str中的每个字符
int u = str[i] - 'a'; // 将字符转换为对应的数字
// 如果当前节点没有指向该字符的子节点，则说明字符串不在字典树中
if(!son[p][u]){
return -1; // 返回-1表示字符串未找到
}
p = son[p][u]; // 移动到子节点，继续查询操作
}
// 如果字符串在字典树中，返回该字符串的出现次数
return cnt[p];
}并查集
概念：
主要用于处理一些不相交集合的合并及查询问题。判断两个元素是否属于同一个集合，以及合并两个集合。同时可以计算每个集合中点的个数
定义：
- 用一个数组
p[N]表示元素的祖宗节点。- 用一个数组
size[N]表示集合中点的个数- 每个集合用树表示，根节点为整个集合编号。每个节点存储祖宗节点编号。
核心操作
Find(x)：查找元素所属集合。即查找元素的根节点。同时完成路径压缩优化Union：合并两个集合。将一个集合根节点连接到另一个集合根节点上。关键点
- 初始化每个元素都为根节点，即
p[i]=i,同时初始化集合中点的个数，size[i]=1- 判断根节点：
if（p[x]==x）- 求x的集合编号：
while（p[x]!=x）x=[px];- 合并两个集合：px为x的集合编号，py为y的集合编号。
p[find(x)]=find(y)（将x所在集合链接到y所在集合）,同时将x集合中点的个数加到y集合中,需要进行特殊判断，如果两个点属于同一个集合，则不能相加
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}
// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);哈希表模拟
- 采用数组+链表方式。模拟拉链法。链表同时也采用数组模拟
关键点
- 查找槽位：k=（k%N+N）%N；（加N是防止出现负数的情况）
- 哈希函数N取值：小于长度的最大质数
- 初始化数组值为
-1：代表空节点
模拟哈希表开放寻址法
关键点
- 查找槽位：k=（k%N+N）%N；（加N是防止出现负数的情况）
- 初始化一个常量
null=0x6f6f6f;代表为空情况find函数：返回当前要插入元素的应该插入位置，或者返回查找到该元素的位置。- 数组长度要开到最大值的
3倍
const int N=1e5+3;
int h[N],e[N],ne[N],idx;
void insert(int x){
//计算槽位
int k=(x%N+N)%N;
//插入链表，头插法
e[idx]=x;
ne[idx]=h[k];
h[k]=idx++;
}
bool find(int x){
int k=(x%N+N)%N;
//链表中查找元素
for(int i=h[k];i!=-1;i++){
if(e[i]==x)
return true;
}
return false;
}
fill(h, h + N, -1);//初始化槽中为空节点
//开放地址法
int find(int x){
int k=(x%N+N)%N;
while(h[k]!=null&&h[k]!=x){
k++;
if(k==N)k=0;
}
return k;
}字符串哈希
思路：将字符串看做是一个
P进制的数，P的一般是取131或13331，取这两个值的冲突概率低关键点：
- 取模的数用
2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果h[N]存储字符串前缀哈希值，P[N]存储的是P的i次幂，用于在计算子串哈希值时进行调整- 需要预处理前缀哈希数组
h，以及权重数组``p`- 使用
h[r] - h[l-1] * p[r-l+1]来计算子串的哈希值，这个公式的核心在于将h[l-1]乘以p[r-l+1]，使得其与h[r]的权重一致，从而可以直接求差得到子串的哈希值。
typedef unsigned long long ULL;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
// 初始化
p[0] = 1;
for (int i = 1; i <= n; i ++ )
{
h[i] = h[i - 1] * P + str[i];
p[i] = p[i - 1] * P;
}
// 计算子串 str[l ~ r] 的哈希值
ULL get(int l, int r)
{
return h[r] - h[l - 1] * p[r - l + 1];
}3.图论
图和树的存储
树是一种特殊的图，与图的存储方式相同。对于无向图中的边a，b，存储两条有向边a->b, b->a。因此我们可以只考虑有向图的存储。
- 邻接矩阵：
g[a][b]存储边a->b- 邻接表
定义邻接表的数据结构：
h[N]: 邻接表的头节点数组，h[i]存储顶点i的第一条边的索引。用于存储每个单链表的头节点。该单链表表示k能够走到的所有的点。e[M]: 边数组，用来存储第i条边指向的顶点。w[N]：权重数组，w[i]存储第i条边的权重。ne[M]: 下一条边数组，ne[i]存储与第i条边同起点的下一条边的索引。idx: 边数组的当前索引，用于添加新边。初始化邻接表：
memset(h, -1, sizeof h);初始化头指针数组，将每个节点的头指针设为-1，表示该节点还没有边。添加边：
add(int a,int b)表示添加一条从a指向b的边即a->b。
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a->b
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);DFS
正常图模板
采用邻接表进行存储，因此需要模拟一个邻接表，同时由于遍历仅一次，需要一个
bool类型数组st[N]代表节点是否已被访问。
bool st[N];
int dfs(int u)
{
st[u] = true; // st[u] 表示点u已经被遍历过
//遍历单链表
for (int i = h[u]; i != -1; i = ne[i])
{
int j = e[i];//e[i]表示当前边i指向的顶点
if (!st[j]) dfs(j);
}
}网格图模板
| 重复访问 | 邻居个数 | DFS | BFS | |
|---|---|---|---|---|
| 二叉树 | 否 | ≤3 | 前中后序 | 层序 |
| 网格图 | 是 | ≤8 | 连通块 | 最短路 |
| 一般图 | 是 | 任意 | 连通块、判环等 | 最短路等 |
int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1},dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};// 8个方向
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};//上下左右四个方向的向量，不用写4个dfs
bool st[300][300]; // 访问标记数组
void dfs(int x, int y, vector<vector<char>>& grid) {
if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()||grid[x][y] != '1')//出界或者不是岛屿
return;
grid[x][y]='2';//标记已被访问，也可以用bool类型数组
for (int i = 0; i < 4; ++i) {
dfs(x + dx[i], y + dy[i], grid);
}
}BFS
单源BFS
采用邻接表存储，模拟一个邻接表。需要使用一个队列进行一层一层的遍历搜索。可以使用数组进行模拟
int q[N],hh,tt;
bool st[N];
void bfs(){
s[1]=true;//1号点已经被遍历过了。
q[0]=1;
while(hh<=tt){
int t=q[hh++];//获取队头节点
//遍历单链表
for(int i=h[t];i!=-1;i=ne[i]){
int j=e[i];//节点真实值
if(!st[j]){
st[j]=true;
q.push(j);
}
}
}
}多源BFS
多源BFS和单源的都是类似的，区别在于，多源BFS需要再初始化的时候，将所有的起点都加入到队列中，之后进行更新。有点类似于最短路径的模板。网格图的BFS队列中存储的是
pair<int,int>。代表当前点的下标。同时如果要求距离，可以进行维护一个dist二维数组（每个点到起点的距离），与最短路径类似，初始化起点到自己的距离为0，其他点的距离为0f3f3f3f3f。常见的有两种模板。
- 不需要确定当前遍历到哪一层
- 需要确定当前遍历到了哪一层
while queue 不空：
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未访问过：
queue.push(该节点)level = 0
while queue 不空：
level ++;
size = queue.size()
while (size --) {
cur = queue.pop()
for 节点 in cur的所有相邻节点：
if 该节点有效且未被访问过：
queue.push(该节点)
}拓扑排序
思路：将入度为0的节点加入到队列之中，每次删除当前遍历的单链表节点边，等价于，单链表上节点的入度减一，如果入度为0了，将其加入队列之中。最后检查入队个数是否是图中点的个数。
拓扑排序的基本思路
- 初始化：
- 构建邻接表来表示图。
- 计算每个节点的入度
d[N]表示。- 寻找入度为0的节点：
- 将所有入度为0的节点加入队列。这些节点没有任何前驱，可以作为排序的起点。
- 处理队列：
- 从队列中取出一个节点，加入排序结果。
- 遍历该节点的所有邻接节点，将它们的入度减1。如果某个邻接节点的入度减为0，则将其加入队列。
- 重复以上步骤，直到队列为空。
- 检查结果：
- 如果排序结果中的节点数等于图中的节点数，则拓扑排序成功。否则，图中存在环，无法进行拓扑排序。
bool topsort()
{
int hh = 0, tt = -1;
// d[i] 存储点i的入度
for (int i = 1; i <= n; i ++ )
if (!d[i])
q[ ++ tt] = i;
while (hh <= tt)
{
int t = q[hh ++ ];
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (-- d[j] == 0)
q[ ++ tt] = j;
}
}
// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。
return tt == n - 1;
}最短路径
单源最短
无负权值
朴素dijkstra
主要应用于稠密图（边多），也就是边比较多情况。用于寻找
1号点到n号点的最短路径，如果不存在返回-1主要步骤：
g[N][N];代表存储的边，dist[N];代表存储1号点到每个点的最短距离，st[N]存储每个点的最短路是否已经确定
- 初始化
dist[1]=0,其他dist[v]=0x3f，初始化邻接矩阵设为0x3f。- 找到不在
st集合中，且距离最近的点t- 将点t加入到集合
st中- 用点
t来更新其他的点的最短距离。关键点：
- 时间复杂度
O(n^2)- 初始化邻接矩阵
- 适用于稠密图（边多）
- 能够处理正环路
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定
// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0; i < n - 1; i ++ )
{
int t = -1; // 在还未确定最短路的点中，寻找距离最小的点
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
// 用t更新其他点的距离
for (int j = 1; j <= n; j ++ )
dist[j] = min(dist[j], dist[t] + g[t][j]);
st[t] = true;
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}堆优化dijkstra
应用于稀疏图（边少），利用小跟堆进行优化查询未加入
st集合中距离最小的点，然后更新其他点的距离。基本步骤
初始化距离数组和堆：
使用
memset初始化距离数组dist为无穷大（0x3f3f3f3f），表示初始时所有点到起点k的距离未知，除了起点k到自身距离为0。声明一个小根堆（优先队列），用于存储每个顶点到起点
k的当前最短距离。将起点加入堆：
- 将起点
k的距离（即0）和顶点编号（即k）作为一个pair放入堆中。堆操作：
当堆不为空时，从堆中取出当前距离起点最近的顶点。
如果该顶点的最短路径已经确定过（通过
st数组标记），则跳过该顶点的处理。否则，标记该顶点的最短路径为已确定，然后遍历该顶点所有相邻的顶点。
更新最短路径：
- 对于每个相邻顶点，如果通过当前顶点可以获得更短的路径，则更新该顶点的最短路径，并将新的距离和顶点编号放入堆中，以便后续处理。
终止条件：
当堆为空时，所有可达的顶点的最短路径已经确定。
最终判断目标顶点n的最短路径值是否仍然是初始值
0x3f3f3f3f。如果是，则说明从起点k无法到达目标顶点n，返回-1；否则，返回目标顶点n的最短路径值。关键点
- 时间复杂度：
O(m*logn)- 需要使用邻接表来存储，同时要加上一个权值数组
w，不要忘记头结点的初始化。- 调用内置的优先队列实现小跟堆，同一顶点会有一些冗余数据，因此我们要额外判断当前顶点的最短距离是否已经确定过。如果确定过，那么就需要跳过本次操作，否则将其加入
st集合中。dist数组中保存的即为1号点到其他各顶点的最短距离。- 堆中保存的是
pair对，表示1号顶点到顶点k的距离（临时最短距离）使用场景
- 稀疏图（边少）
- 能否处理正环路
typedef pair<int, int> PII;
int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定
// 求1号点到n号点的最短距离，如果不存在，则返回-1
// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra() {
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
priority_queue<PII, vector<PII>, greater<PII>> heap; // 定义一个小根堆
heap.push({0, 1}); // first 为距离, second 为顶点编号
while (!heap.empty()) {
auto t = heap.top();
heap.pop();
// 获取当前顶点最短路径，以及编号
int var = t.second, distance = t.first;
// 因为堆并不会删除元素，可能会有冗余
if (st[var]) continue; // 代表当前顶点最小距离已经获取过；
st[var] = true;
// 更新到其他点的距离
for (int i = h[var]; i != -1; i = ne[i]) {
int j = e[i]; // 获取边索引 i 指向的顶点
if(st[j])continue;
if (dist[j] > distance + w[i]) {
dist[j] = distance + w[i]; // w[i] 表示当前边索引 i 的权值
heap.push({dist[j], j});
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}有负权值
bellman_ford
适用于带有负权值的图，步骤如下
基本步骤
- 初始化：将起始点的距离设为0，其余点的距离设为无穷大。
- 多次松弛：最多进行
n-1次松弛操作，重复遍历所有边，尝试通过已知的最短路径更新其他点的最短路径。- 返回结果：返回起始点到目标点的最短路径长度或者标记不可达。
关键点：
- 时间复杂度：固定为
O(n*m)- 可能需要加上备分数组，防止串联问题出现。
使用场景
- 图中存在负权边：Bellman-Ford算法可以处理带有负权边的图，而Dijkstra算法则不能直接处理负权边的情况。
const int N ; // 点数的上限
const int M ; // 边数的上限
int n, m; // n 表示点数，m 表示边数
int dist[N]; // dist[x] 存储从点1到点x的最短路距离
int backup[N]; // 备份数组，用于防止串联问题
struct Edge {
int a, b, w; // 边的起点 a，终点 b，权重 w
} edges[M];
// Bellman-Ford 算法求解最短路径
int bellman_ford() {
memset(dist, 0x3f, sizeof dist); // 初始化距离数组，表示距离为无穷大
dist[1] = 0; // 从点1开始，距离为0
// Bellman-Ford 算法的核心循环，进行n-1次松弛操作
for (int i = 0; i < n; i++) {
//memcpy(backup, dist, sizeof dist); // 备份当前的距离数组，防止串联问题
// 遍历所有边，进行松弛操作
for (int j = 0; j < m; j++) {
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (dist[b] > backup[a] + w)
dist[b] = backup[a] + w;
}
}
// 如果 dist[n] 仍然为无穷大，则表示无法从点1到达点n
if (dist[n] > 0x3f3f3f3f / 2) return -1;
return dist[n]; // 返回点1到点n的最短路径长度
}spfa
概念：spfa是对
bellman_ford算法的优化，主要是将Bellman-Ford算法中，每次迭代需要遍历所有的顶点和边进行松弛操作。优化为了通过使用一个队列来维护需要松弛的顶点，从而避免了对所有顶点的重复检查。具体步骤
- 初始化：
创建一个队列（通常是使用队列来实现），用于存储待优化的顶点。
初始化距离数组
dist[]，将起始顶点到所有其他顶点的距离设为无穷大（表示不可达）或者一个很大的数（表示初始状态）。将起始顶点加入队列，并将其距离设为0。
队列操作：
- 当队列不为空时，执行以下操作：
- 弹出队列中的一个顶点，标记该顶点为不在队列中。
- 遍历当前顶点的所有邻接顶点：
- 如果通过当前顶点能够使得到达邻接顶点的路径距离更短（即
dist[j] > dist[t] + w[i]），则更新dist[j]为更小的值，并将邻接顶点j加入队列中（如果尚未在队列中）。循环迭代：
- 反复执行上述步骤，直到队列为空。如果队列为空时仍有顶点的距离未被更新，则说明已经找到了最短路径或者图中存在负权回路。
- 结果输出：
- 如果
dist[n]（或目标顶点的距离）仍为初始值（无穷大或者很大的数），则表示起始顶点无法到达目标顶点，返回-1或者处理无法到达的情况。- 否则，
dist[n]就是起始顶点到目标顶点的最短路径长度。关键点
- 时间复杂度：通常为
O（m）最坏情况为O（m*n）- 可以有负权值，但是不能有负环.（能够检测负环）
使用场景
适用于含有负权边的图：
SPFA算法可以处理负权边，并能检测负权环。适用于大部分情况下的最短路径求解：相比
Bellman-Ford算法，SPFA在实际应用中的性能通常更好，特别是在稀疏图中表现突出。
//用法1，求带有负权值的单源最短路径。
// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa() {
// 初始化距离数组，将所有距离设置为无穷大（使用0x3f3f3f3f表示）
memset(dist, 0x3f, sizeof dist);
dist[1] = 0; // 起点1号点的距离设置为0
// 初始化队列，并将起点1号点加入队列
queue<int> q;
q.push(1);
st[1] = true; // 标记1号点在队列中
// 进行队列处理
while (!q.empty()) {
// 取出队列中的第一个点
int t = q.front();
q.pop();
st[t] = false; // 取消标记，表示t点不在队列中
// 遍历从t点出发的所有边
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i]; // 获取边的终点
// 如果通过t点到j点的距离更短，则更新dist[j]
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i];
// 如果j点不在队列中，则将其加入队列
if (!st[j]) {
q.push(j);
st[j] = true; // 标记j点在队列中
}
}
}
// 如果1号点无法到达n号点，则返回-1
if (dist[n] == 0x3f3f3f3f) return -1;
// 否则返回1号点到n号点的最短距离
return dist[n];
}
//用法2:判断是否有负环
const int N // 最大节点数
const int M // 最大边数
int h[N], w[M], ne[M], e[M], idx; // 邻接表的相关变量
int dist[N], cnt[N]; // dist[x] 表示从1到x的最短距离；cnt[x] 表示从1到x经过多少条边
bool st[N]; // st[x] 表示节点x是否在队列中
int n, m; // n: 节点数, m: 边数
// SPFA算法
bool spfa() {
memset(dist, 0x3f, sizeof(dist)); // 初始化距离为无穷大
memset(h, -1, sizeof(h)); // 初始化邻接表头节点
queue<int> q; // 使用队列
q.push(1); // 将起点1加入队列
dist[1] = 0; // 起点到自身的距离为0
st[1] = true; // 起点在队列中
while (!q.empty()) {
int t = q.front(); // 取出队首节点
q.pop(); // 队列弹出操作
st[t] = false; // 标记当前节点不在队列中
// 遍历邻接边
for (int i = h[t]; i != -1; i = ne[i]) {
int j = e[i]; // j 为当前边的终点
// 松弛操作
if (dist[j] > dist[t] + w[i]) {
dist[j] = dist[t] + w[i]; // 更新最短距离
cnt[j] = cnt[t] + 1; // 更新经过的边数
// 检测是否超过了n条边
if (cnt[j] >= n) {
return true; // 发现负权环
}
// 如果节点j不在队列中，则将其加入队列
if (!st[j]) {
q.push(j);
st[j] = true; // 标记节点j在队列中
}
}
}
}
return false; // 没有发现负权环
}多源汇最短路径（Floyd）
具体步骤
- 初始化
- 将所有点对之间的距离初始化为无穷大（表示不可达），自身到自身的距离初始化为0。
- 更新直接相连的距离：
- 对于每条边的权重，更新相应的距离矩阵。
- 动态规划递推
使用三层循环遍历所有点，以确定通过中间点的路径是否比当前已知路径更短。具体地，对于每对顶点
i和j，以及每个可能的中间顶点k，更新距离矩阵d[i][j]：d[i][j]=min(d[i][j],d[i][k]+d[k][j])这表示如果从i到j经过k比直接从i到j更短，则更新d[i][j]的值。关键点：
- 时间复杂度：
O(n^3)- 适用于稠密图，即顶点数量较少但边数较多的情况。
- 可以处理带有负权边但没有负权回路的图
初始化：
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (i == j) d[i][j] = 0;
else d[i][j] = INF;
// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}最小生成树
普利姆算法（prim）
概念：
prim算法用于解决最小生成树问题，一共有两种，一种是朴素版的prim（稠密图常用），另一种是堆优化的prim（解决稀疏图，代码过于复杂，不常用）具体过程
- 将
dist[i]初始化为0x3f3f3f3f- 添加
n个顶点到集合之中。
t=-1找到集合外距离集合最近的点- 用
t更新集合外其他点到集合的距离- 标记当前点已经加入集合中
st[t]=true;
const int N=510,INF=0x3f3f3f3f;
int g[N][N];//邻接矩阵。存储所有的边
int dist[N];//dist代表到集合的最小距离，存储其他点到当前最小生成树的距离
bool st[N];//标记是否加入到了集合中。
int n,m;
// 如果图不连通，则返回INF(值是0x3f3f3f3f), 否则返回最小生成树的树边权重之和
int prim(){
int res=0;
//初始化距离
memset(dist,0x3f,sizeof dist);
//向集合中加入点，一共加入n个点
for(int i=0;i<n;i++){
//选择集合外距离最短的点
int t=-1;
for(int j=1;j<=n;j++){
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
}
if(i&&dist[t]==INF)return INF;
if(i)res+=dist[t];
//更新其他点到集合的最短距离
for(int j=1;j<=n;j++)
dist[j]=min(dist[j],g[t][j]);
st[t]=true;
}
return res;
}克鲁斯卡尔算法（kruskal)
概念
kruskal用于解决稀疏图的最小生成树问题。只要是稀疏图就用kruskal，不考虑堆优化的prim。使用并查集解决。具体过程
- 将所有的边按从小到大的排序
- 初始化并查集
- 枚举每条边
a,b,w
- 如果
a,b不连通
- 将这条边加入集合中。
关键点
- 时间复杂度：
O(mlogm)
const int N = 1e5 + 100; // 并查集的最大节点数量
int p[N]; // 并查集的父节点数组
struct Edge // 定义存储边的结构体
{
int a, b, w; // a和b是边的两个端点，w是边的权重
// 重载小于运算符，用于边的排序
bool operator< (const Edge &W) const
{
return w < W.w; // 按权重从小到大排序
}
} edges[N];
int find(int x) // 并查集的核心操作，路径压缩
{
if (p[x] != x) p[x] = find(p[x]); // 递归查找父节点，并路径压缩
return p[x]; // 返回祖宗节点
}
int kruskal() // Kruskal算法计算最小生成树
{
sort(edges, edges + m); // 对所有边按权重排序
for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集，每个节点的父节点指向自己
int res = 0, cnt = 0; // res存储最小生成树的总权重，cnt计数已加入的边数
for (int i = 0; i < m; i++)
{
int a = edges[i].a, b = edges[i].b, w = edges[i].w; // 读取边的两个端点和权重
a = find(a), b = find(b); // 查找两个端点的祖宗节点
if (a != b) // 如果两个连通块不连通，则将这两个连通块合并
{
p[a] = b; // 合并两个连通块，将a的祖宗节点指向b的祖宗节点
res += w; // 增加边的权重到最小生成树的总权重中
cnt++; // 增加已加入的边数
}
}
if (cnt < n - 1) return 0x3f3f3f3f; // 如果已加入的边数小于n-1，说明图不连通，返回无穷大
return res; // 返回最小生成树的总权重
}二分图（无向图）
二分图判断
染色法判断二分图
概述
染色法用于判断给定图是否为二分图。
(无向图)具体过程
- 遍历每个点
- 如果该点未被染色
- 进行深度遍历
dfs(i,color)
// 声明点数和邻接表的数组
int n; // n 表示点数
int h[N], e[M], ne[M], idx; // 邻接表存储图的结构
int color[N]; // 表示每个点的颜色，-1 表示未染色，0 表示白色，1 表示黑色
// 参数：u 表示当前节点，c 表示当前点的颜色
// 函数功能：使用 DFS 判断从节点 u 开始的图是否可以被二分染色
bool dfs(int u, int c)
{
color[u] = c; // 给当前节点 u 赋予颜色 c
for (int i = h[u]; i != -1; i = ne[i]) // 遍历邻接表
{
int j = e[i]; // 获取邻接节点 j
if (color[j] == -1) // 如果邻接节点 j 还未染色
{
// 递归对邻接节点 j 进行染色，使用 !c 切换颜色
// 如果递归调用返回 false，说明图不是二分图
if (!dfs(j, !c)) return false;
}
else if (color[j] == c) // 如果邻接节点 j 的颜色与当前节点 u 相同
{
// 说明存在冲突，图不是二分图
return false;
}
}
// 如果没有发现冲突，返回 true
return true;
}
// 函数功能：检查图是否是二分图
bool check()
{
memset(color, -1, sizeof color); // 初始化颜色数组，-1 表示所有节点未染色
bool flag = true; // 标志位，用于记录是否是二分图
for (int i = 1; i <= n; i ++ ) // 遍历所有节点
if (color[i] == -1) // 如果节点 i 尚未染色
// 从未染色的节点开始 DFS，初始颜色为 0
if (!dfs(i, 0))
{
flag = false; // 如果发现图不是二分图，更新标志位
break; // 提前终止检查
}
return flag; // 返回图是否是二分图的结果
}并查集判断
过程
初始化并查集：每个节点初始时是自己的祖宗节点。
遍历每个节点及其邻接节点：
如果节点
i与其邻接节点j在同一集合，说明图中有奇环，返回false。否则，将
i的第一个邻接节点和j合并到同一集合。检查完成后：若无冲突，返回
true，表示图为二分图。
static const int N = 200; // 假设最多有 200 个节点
int p[N]; // 并查集数组，存储每个节点的祖宗节点
// 找到节点 x 的祖宗节点，并进行路径压缩
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
bool isBipartite(vector<vector<int>>& graph) {
// 初始化并查集
int n = graph.size();
for (int i = 0; i < n; i++) p[i] = i;
// 遍历图的每个节点
for (int i = 0; i < n; i++) {
if (graph[i].empty()) continue;
for (auto j : graph[i]) {
// 检查节点 i 和它的邻接节点 j 是否在同一个集合中
if (find(i) == find(j)) return false;
else
// 将节点 i 的第一个邻接节点与节点 j 合并到同一个集合中
p[find(graph[i][0])] = find(j);
}
}
return true;
}
};二分图的最大匹配
匈牙利算法
概述
匈牙利算法计算二分图的最大匹配。
具体过程
- 枚举一侧的点，寻找另一侧点进行匹配
- 遍历该点的邻接链表，试图找到一个没有被匹配的点，与该点匹配。
- 如果邻接表中有点
j没有被匹配，让j点匹配该点xmatch[j]=x- 如果点
j已被匹配，尝试让点j匹配的点k另外寻找一个点匹配。让点j匹配该点x,即match[j]=x- 如果匹配成功返回
true- 不匹配，返回
false过程
- 枚举点：遍历第一个集合中的每个点
x。- 寻找匹配：
- 遍历点
x的所有邻接点j。- 如果 j 未匹配：直接将
j匹配到x。- 如果 j 已匹配：尝试让
j当前匹配的点找到新的匹配，若成功，则将j匹配到x。- 成功返回：如果找到匹配，返回
true；否则，返回false。
int n1, n2; // n1表示第一个集合中的点数，n2表示第二个集合中的点数
int h[N], e[M], ne[M], idx; // 邻接表存储所有边，匈牙利算法中只会用到从第一个集合指向第二个集合的边，所以这里只用存一个方向的边
int match[N]; // 存储第二个集合中的每个点当前匹配的第一个集合中的点是哪个
bool st[N]; // 表示第二个集合中的每个点是否已经被遍历过
bool find(int x)
{
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
if (match[j] == 0 || find(match[j]))//没有匹配的人，或者可以j匹配的人可以更换其他的人。
{
match[j] = x;
return true;
}
}
}
return false;
}
// 求最大匹配数，依次枚举第一个集合中的每个点能否匹配第二个集合中的点
int res = 0;
for (int i = 1; i <= n1; i ++ )
{
memset(st, false, sizeof st);
if (find(i)) res ++ ;
}4.回溯
回溯三问：
- 当前的操作是什么？
- 子问题是什么？
- 下一个子问题是什么？
剪枝操作
- 去除前导0，
if (i !=u&& s[u]==‘0’) retuern ;一般用于字符串- 去重，
if（i!=u&&s[i]==s[i-1]）continue;
子集型回溯
可以分为两种思路进行考虑：
- 从输入角度：，那么仅有两种可能性，本次不选择和本次选择，不选择则直接进行下一层
dfs(u+1)，如果本次选择，那么需要将当前元素加入到路径当中path.emplace_back(nums[i])，进行下一层dfs(u+1).最后进行回溯现场path.pop_back()- 从答案的角度：每次必须要选择一个元素，也就是在
for循环中每次进行挑选一个元素，同时加入路径，可以在for循环中进行剪枝处理。最后需要对路径做回溯处理。避免影响下一条分支。问题
dfs(i)代表什么含义？当前路径中已经处理到的位置，也就是说，进行处理区间[i,n]。- 如何理解输入角度？意思是，每次到达尽头后，返回再进行尝试，加入该元素。
- 回溯遍历产生的
n叉树,其中横向代表我们的for循环遍历，是在当前集合基础上，尝试去加入同一位置不同元素。纵向代表的是递归的过程产生的树枝。- 剪枝？剪枝处理是对于同一树层而言的，因此纵向不需要进行剪枝。
- 结果？结果的话，不同的角度，结果也有所不同，例如，求子集的话，采用输入角度，那么每个叶子节点为结果，如果采用答案视角的话，那么每个节点都是结果。
注意点：
- 在答案视角，每次的未探索区域为
[i,n]，因此进行下一个区域应该是[i+1,n]，不要与输入视角混淆，输入视角为，选不选当前元素。
path[]//保存路径
res[]//返回结果集合
void dfs(int u){
if(path满足条件){//可以是长度足够，亦或者是其他
res.emplace_back(path);
return ;
}
//为探索过的区域进行取值
for(int i=u;i<n;i++){
if(当前选择满足条件){//可能会进行去重等等。
path.emplace_back(nums[i]);//在路径中加入当前选择。
dfs(i+1);//探索下一个未知区域[i+1,n-1]
path.pop_back();//恢复现场,回溯
}
}
}
//输入视角
path[]//保存路径
res[]//返回结果集合
void dfs(int u){
if(path满足条件){//可以是长度足够，亦或者是其他
res.emplace_back(path);
return ;
}
//不选择该元素
dfs(u+1);
//选择该元素,可能还需要进行一些判断，例如字符选择变化
path.emplace_back(nums[i]);//在路径中加入当前选择。
dfs(i+1);//探索下一个未知区域[i+1,n-1]
path.pop_back();//恢复现场,回溯
}组合型回溯
组合型回溯，大致跟子集型回溯类似，不过，他限制了
path的大小为K。同时相较于子集型回溯，我们能够做出更多的剪枝操作。但是相较于子集型回溯，有些额外的要求，例如，可以重复使用元素，不能重复使用元素注意点
- 如果能够重复使用元素，那么在
for循环内，下一层递归应该写成dfs(u)- 不能重复使用元素写成
dfs(u+1)剪枝
- 当剩余元素数量不足以形成有效解时，提前返回。
- 去重：有重复元素时，排序，同时跳过相同元素。
if (i !=u&& nums[i] == nums[i - 1]) continue;
- 原因：去重的前提是要先对数组进行一个排序，这样保证了相同元素挨在一起出现，同时，如果出现相同元素，那么第一个元素能进行搜索的范围永远是最大的，他会将同一层相同元素能够搜索出来的答案包含在内。那么我们仅需要保留第一条分支即可，其他同层相同元素进行剪枝处理。
- 但是对于同一分支的相同元素，是可以出现的，因此不会进行去重。
排列型回溯
排列型回溯与其他回溯不同的是，对于位置不同的
path都算作答案。关键点
dfs(u)对应的含义
- 当前要么枚举第u个位置的元素也就是，选择数字填入
path[u]中。- 记录已经加入path中的数：
- 用一个
bool类型数组st[]记录当前已经加入了path中的数- 每次都是从开头开始重新遍历，因为一个元素可以出现在其他任何位置。全排列每个元素在每个位置上都可能出现
- 回溯：每次递归完成后，需要恢复现场。
重点
去重：
if(i!=0&&nums[i]==nums[i-1]&&!st[i-1]) continue排序：
- 先对数组进行排序，这样相同的元素会挨在一起出现，方便后续的去重操作。
剪枝：
在同一树层上（即同一递归层次上），对于相同的元素，只保留第一个进行搜索的分支，剪掉后面相同元素的分支。这是因为在全排列的情况下，每个元素都会被用到，所以如果第一个相同的元素已经被用来生成了一部分排列，后面相同的元素生成的排列必定会和之前的重复。
在实现上，如果当前元素和前一个元素相同，并且前一个元素刚刚被撤销（即
st[i-1] == false），则当前分支的搜索结果与前一个分支重复，因此应该跳过当前元素。如果不加st[i-1] == false会导致同一分支的相同元素被误剪掉
字符串回溯
字符串型回溯，一般是用于切割字符串
关键点
- 当前操作？选择子串
[u,i]加入到路径path中- 子问题？从下标
>=i的序列中进行子串切割- 下一个子问题？从下标
>=i+1子串中进行切割重点
- 移除前导0，
if (i !=u&& s[u]==‘0’) retuern.出现了前导0，说明本次序列不成功，同层就不需要再进行访问，直接剪枝返回进入下一层
dfs(u)含义：含义是，从[u,n-1]中进行分割子串,换句说法也就是，当前探索的位置区域为[u,n-1]的子串。
去重问题
可排序的数组：
由于数组可排序，先将数组排序。那么相同的数字一定是挨在一起的，那么我们只需要保留第一个数字出现时，搜索的结果即可，因为第一个出现数字搜索的结果，一定是要比后面出现数字搜索结果要大。即
if(i!=x&&nums[i]==nums[i-1]&&!st[i-1])continue加上!st[i-1]的原因是因为。第一个数字搜索完毕后会回溯为false，因此要加上!st[i-1]不可排序的数组：
此时的数组不可进行排序，相同的数字不一定挨在一起，因此，我们对同层元素剪枝时，可以使用
unordered_set来进行去重，第一次遇到某个数字时记录下来，后续在同一层遇到相同数字直接跳过。只需要保留第一次出现的分支即可。即if(st.count(nums[i]))continue总结：
这两种方法的本质都是在保证：对于相同的数字，只保留第一次出现时的搜索分支，因为这个分支一定包含了所有可能的组合。
5.数学问题
质数
质数的判定
采用试除法，原理是因为对于每个
i，n / i也是n的因子，如果i超过sqrt(n)，我们就不需要再检查更大的因子了。关键点
- 时间复杂度 一定为 O(sqrt(n))
bool is_prime(int n)
{
if(n < 2) return false;
for(int i = 2;i <= n / i;i ++)//不要写成i*i<=n可能会造成溢出的情况，写成i<=sqrt(n)速度会很慢
if(n % i == 0)
return false;
return true;
}分解质因数
采用试除法
- 定理1：任何一个大于
1的自然数，要么本身是质数，要么可以表示为有限个质数的乘积，并且这种表示是唯一的（除了因子排列顺序不同之外）- 定理2：一个数中至多有一个因数大于
sqrt(n)，因此我们枚举质因数只需要枚举到<=sqrt(n)。如果存在一个因数大于sqrt(n)。那么其对应的因子一定是小于sqrt(n)- 原理：从最小的质数
2开始，逐次尝试用质数去除目标数，直到目标数变成1。关键点
- 时间复杂度 平均为
O(sqrt(n))
void devide(int n){
for(int i=2;i<=n/i;i++){
if(n%i==0){//i 一定是质数。因为如果 `i` 不是质数，那么它可以被更小的质数分解，之前的步骤已经考虑过这些更小的质数。
int s=0;
while(n%i==0){
s++;
n/=i;
}
printf("%d %d\n",i,s);
}
}
if(n>1)printf("%d %d\n",n,1);
}筛质数
朴素筛法
理解：从2开始筛，每次筛除当前i的倍数。
关键点
- 时间复杂度
O(nloglogn)
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (st[i]) continue;
primes[cnt ++ ] = i;
for (int j = i; j <= n; j += i)
st[j] = true;
}
}线性筛法
理解：线性筛法的核心思想是只利用合数的最小质约数来筛除掉，如果当前的
i%pri_j==0说明了i是pri_j的倍数，由于我们是从小到大记性枚举的pri_j。那么pri_j就是i的最小质约数。如果此时继续标记i的倍数数（等价于m*pri_j），那么i的倍数会被重复的标记。因此我们要保证每一个合数都有他的最小质约数来筛除掉，遇见i%pri_j==0应该break掉关键点
- 时间复杂度为O(n)
int primes[N], cnt; // primes[]存储所有素数
bool st[N]; // st[x]存储x是否被筛掉
void get_primes(int n)
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )//小于等于n/i的原因是因为一个合数中至多有一个>sqrt(n)的因数，因此质因数只需要枚举到<=sqrt(n)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}约数
求约数
试除法，如果有
d|n，那么同时有(d/n)|n。因此我们只需要枚举小的一个即可，即d<=(d/n)，即为d<=sqrt(n)。注：相同的约数只添加一次
关键点
- 时间复杂度
vector<int> get_divisors(int x)
{
vector<int> res;
for (int i = 1; i <= x / i; i ++ )
if (x % i == 0)
{
res.push_back(i);
if (i != x / i) res.push_back(x / i);//不同的约数才添加
}
sort(res.begin(), res.end());
return res;
}公式
- 约数个数：
- 约数之和：
最大公约数
理解：对于求a，b的最大公约数有
d|a,d|b,d|(cx+by)。则有(a,b)=(b,a%b)。证明为：左边有d|a,d|b,d|(cx+by)。对于右边有，a%b可以写成a-(a/b)*b。等价与a-c*b。则有d|b,d|(a-c*b)。对于d|(a-c*b)。由于d|b，在右边加上c*b。有d|（a-c*b+c*b)等价与d|a。因此左右的最大公约数相等。
- 注：
- 最后条件为
(a,0)即求a与0的最大公约数，0可以被任何数整除。因此返回a即可。
int gcd(int a, int b) {
return b ?gcd(b, a % b):a ;
}欧拉函数
求欧拉函数
利用公式即可。欧拉函数的公式为
- p 是 n 的所有不同的质因数
- 思路：将一个整数n分解为质因数。利用公式求即可
关键点
- 时间复杂度
int phi(int x)
{
int res = x;
for (int i = 2; i <= x / i; i ++ )
if (x % i == 0)
{
res = res / i * (i - 1);//此处为res*(1-1/i)除法会有精度限制，变为res*(i-1)/i
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}筛法求欧拉函数
思路：求小于等于n的左右数的欧拉函数。如果为质数，欧拉函数
phi(p)=p-1.。如果不是质数，分为两种情况，i%pj==0。如果成立，那么说明pj为i的最小质因数（我们是从小到大枚举质数）。同时也是i*pj的最小质因数。那么phi(i)=i*(…..)*(1-1/pj)计算过程中包括了(1-1/pj)。phi(i*pj)=pj*i*(…..)。其中等式的后半段为phi(i)。因此phi(i*pj)=phi(i)*pj如果不成立，pj此时一定小于i的所有质因数。说明
pj是i*pj的最小质因数。那么phi*(i)计算过程不包括(1-1/pj)。则phi(i*pj)=pj*i*(….)*(1-1/pj)等价于phi(i*pj)=pj*(1-1/pj)*phi(i)等价与phi(i*pj)=phi(i)*(pj-1)% 欧拉函数的定义 欧拉函数
是指小于等于 n 的正整数中与 n互质的整数个数。对于一个正整数 n，其质因数分解为 ( )，则欧拉函数的计算公式为： % 对于
的欧拉函数
第一种情况： (
== 0) 如果 (
== 0)，说明 ( ) 是 i 的最小质因数，并且 也是 $i \times p_j $ 的最小质因数。 对于 i，有
即在计算过程中已经包括了 (
) 这个因子。 那么对于
： **第二种情况：
** 如果$ i \mod p_j \neq 0$，说明 $p_j $不是 i 的质因数。此时
是 的最小质因数，且 小于 i的所有质因数。 对于
的计算中，未包含 ($ \left(1 - \frac{1}{p_j}\right)$ ) 这一项，因为 ( ) 不是 (i) 的质因数。 那么对于 (
)： 结论
- 当 (
) 时， 。 - 当 (
) 时， 。 关键点：
- 时间复杂度
int primes[N], cnt; // primes[]存储所有素数
int euler[N]; // 存储每个数的欧拉函数
bool st[N]; // st[x]存储x是否被筛掉
void get_eulers(int n)
{
euler[1] = 1;
for (int i = 2; i <= n; i ++ )
{
if (!st[i])//表示当前i没有被筛除，是质数。质数p的欧拉函数为p-1
{
primes[cnt ++ ] = i;
euler[i] = i - 1;
}
for (int j = 0; primes[j] <= n / i; j ++ )
{
int t = primes[j] * i;
st[t] = true;
if (i % primes[j] == 0)//pj是i的最小质因数。同时pj也是pj*i的最小质因数 其中i的欧拉函数计算过程中包括了(1-1/pj) pj*i的欧拉函数为pj*i*(......)其中后半部分和i的欧拉函数计算过程一致。因此pj*i的欧拉函数为pj*phi(i)
{
euler[t] = euler[i] * primes[j];
break;
}
//如果i%pj!=0说明 pj小于i的所有质因数，因此pj是i*pj的最小质因数。 同时phi(i)没有包含(1-1/pj)因此 phi(i*pj)=pj*i*(.....)*(1-1/pj)
//化简为phi(pj*i)=pj*(1-1/pj)*phi(i)==phi(i)*(pj-1);
euler[t] = euler[i] * (primes[j] - 1);
}
}
}快速幂
原理：计算a^b，将指数的b写成2进制的形式，累乘不为0的2进制幂。
原理步骤：
将指数 b 转换为二进制。
从最低位到最高位，逐步计算
并根据二进制位是否为1来累乘结果。 例子：算 a^13 .
- 13 的二进制表示为 1101
a^13=a^8×a^4×a^1- 通过逐步平方计算 a^1, a^2, a^4, a^8，然后根据二进制位进行乘法
关键点
- 时间复杂度
O(logb)
//不需要mod
LL qmi(int a,int k){
LL res=1;
while(k){
if(k&1)
res=(LL)res*a;
k>>=1;
a=(LL)a*a;
}
return res;
}
//需要mod
LL qmi(int a,int k,int p){
LL res=1;
while(k){
if(k&1)
res=(LL)res*a%p;
k>>=1;
a=(LL)a*a%p;
}
return res;
}拓展欧几里得
模板
// 求x, y，使得ax + by = gcd(a, b) 裴蜀定理
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}组合数
递推
使用递推的方式
c[i][j]表示从i个数中选择j个数的方案数。公式为c[i][j]=c[i-1][j]+c[i-1][j-1]选与不选关键点
- 时间复杂度为O(n^2)
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;预处理
组合数的公式为
c[a][b]=a!/b!*(a-b)!，除法有精度损失，我们将除法转换为乘法即可首先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]，如果取模的数是质数，可以用费马小定理求逆元即求
b!和(a-b)!的逆元关键点
- mod为整数，可以使用快速幂来求逆
int qmi(int a, int k, int p) // 快速幂模板
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
// 预处理阶乘的余数和阶乘逆元的余数
fact[0] = infact[0] = 1;//0!为1
for (int i = 1; i < N; i ++ )
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}卢卡斯定理
卢卡斯定理为
C(n, m) = C(n % p, m % p) * C(n / p, m / p) (mod p)
int qmi(int a, int k) // 快速幂模板
{
int res = 1;
while (k)
{
if (k & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
k >>= 1;
}
return res;
}
int C(int a, int b) // 通过定理求组合数C(a, b) (a-b+1)!/b!
{
int res = 1;
for (int i = 1, j = a; i <= b; i ++, j -- )
{
res = (LL)res * j % p;
res = (LL)res * qmi(i, p - 2) % p;
}
return res;
}
int lucas(LL a, LL b)
{
if (a < p && b < p) return C(a, b);
return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}分解质因数法
当我们需要求出组合数的真实值，而非对某个数的余数时，分解质因数的方式比较好用：
- 筛法求出范围内的所有质数
- 通过
C(a, b) = a! / b! / (a - b)!这个公式求出每个质因子的次数。 n! 中p的次数是 n / p + n / p^2 + n / p^3 + ...- 用高精度乘法将所有质因子相乘
关键点
- 高精度相乘，结果为倒序，因此我们要倒序访问。
int primes[N], cnt; // 存储所有质数
int sum[N]; // 存储每个质数的次数
bool st[N]; // 存储每个数是否已被筛掉
void get_primes(int n) // 线性筛法求素数
{
for (int i = 2; i <= n; i ++ )
{
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int get(int n, int p) // 求n！中的次数
{
int res = 0;
while (n)
{
res += n / p;
n /= p;
}
return res;
}
//高精度乘法
vector<int> mul(vector<int> a, int b) {
vector<int> c;
int n = a.size();
for (int i = 0, carry = 0; i < n || carry; i++) {
if (i < n) carry += a[i] * b;
c.push_back(carry % 10);
carry /= 10;
}
return c;
}
void C(int a,int b){
get_primes(a);
//统计质数的数
for(int i=0;i<cnt;i++){
int p=primes[i];
sum[i]= get_(a,p)-get_(b,p)-get_(a-b,p);
}
vector<int> res;//结果数组
res.emplace_back(1);
//构造结果
for(int i=0;i<cnt;i++){
int p=primes[i];
for(int j=0;j<sum[i];j++)
res=mul(res,p);
}
for (int i = res.size() - 1; i >= 0; i--) {
cout << res[i];
}
}6. 动态规划
爬楼梯问题
打家劫舍问题
最大子数组和问题
定义
f[i]为以nums[i]结尾的元素的最大和，可以分为两种情况进行讨论。
- 选择改元素：代表加上当前元素的值，也即
f[i-1]+nums[i]- 不选择该元素：代表以该元素为开头，即
f[i]=nums[i]。即
f[i]=max(f[i-1]+nums[i],nums[i]);最大值为
f中最大值
背包模型
边界条件的总结
大致分为4种
能否构成：
- 初始化：
f[0][0] = true（0 可以构成 0）方案数：
- 初始化：
f[0][0] = 1（0 组成 0 只有一种方案）数字个数：
- 初始化：
f[0][0] = 0（0 组成 0 不需要使用数字）最大值/最小值：
初始化：
f[0][0] = 0（0 组成 0 不需要使用数字）如果是最大值，其他的就初始化为-INF，保证能够比较出正确的答案。
如果是最小值，其他就初始化为INF，保证使用min函数能够比较出正确答案。
最后需要判断一下返回值，如果是极端的情况，返回-1
0-1背包模型
简述：0-1背包模型是背包模型的基础，主要解决问题是物品仅能选择一次的问题。
朴素做法：定义一个二维数组
f[i][j]表示从1-i中选择物品体积不超过j的情况下所能达到的最大值。属性为MAX集合由两部分构成，选择第
i个物品构成的集合f[i][j]，以及不选择第i个物品构成的集合f[i-1][j-v[i]]+w[i]。不选择第i个物品集合最大值相当于，选择1~i-1个物品能达到最大值减去第i个物品的体积，加上第i个物品的价值。状态转移方程即为
f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i])。选择第i个物品需要保证背包容量足够。j>=v[i]最后返回
f[n][m]即为选择1-n体积不超过m所能达到的最大值滚动数组的做法：
观察状态转移方程，发现当前状态仅与上一层的状态有关系，即
f[i][:]状态仅跟f[i-1][:]有关系，因此我们能够利用滚动数组进行优化。需要注意的地方是，我们需要保证，在更新当前状态的时候，上一层的状态未被覆盖更新，也就是f[i-1]还未被更新，所表示的状态仍然是上一层的状态。因此我们可以倒着更新，也就是从末端开始更新。这样就能保证，更新当前状态的时候，上一层的状态（下标小于当前j的位置）一定没有被更新。状态转移方程为f[j]=max(f[j],f[j-v[i]]+w[i])
案例
输入样例 4 5 1 2 2 4 3 4 4 5 输出样例： 8例如以更新第三层为例
更新索引5
i = 3, j = 5(m=5),v[3] = 3, w[3] = 4当前更新第3层索引5dp[5] = max(dp[5], dp[2] + 4)注意，等号右边的dp[5],dp[2]都必须是上一层dp的对应索引值此时第二层为
[0, 2, 4, 6, 6, 6]，第三层[0, 2(未改), 4(未改), 6(未改), 6(未改), 6(正在改)]因为本层更新dp[5]时，只能使用未更新的dp值，这些才是上一层的dp值，即索引较小的最后更新第三层索引5更新完后为
[0, 2(未改), 4(未改), 6(未改), 6(未改), 8(已经改)]
完全背包模型
简述: 完全背包模型解决的问题是一个物品可以选择无限次
朴素做法：定义一个二维数组
f[i][j]表示从1-i中选择物品体积不超过j的情况下所能达到的最大值。属性为MAX该集合由不选，选一个，选两个，选三个……选k个构成。不选择该物品表示为
f[i-1][j]。选择k个物品表示为f[i-1][j-v[i]*k]+w[i]*k。因此f[i][j]=max(f[i-1][j],f[i-1][j-v[i]]+w[i],f[i-1][j-v[i]*2]+w[i]*2,f[i-1][j-v[i]*k]+w[i]*k)。对于f[i][j-v[i]]有f[i][j-v[i]]=max(f[i-1][j-v[i]],f[i-1][j-v[i]*2*]+w[i],……,f[i-1][j-v[i]*k]+(k-1)*w[i])。最后可以转移为f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i])如下图所示滚动数组优化：有状态转移方程可以看出
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);由于此时更新的为f[i][j]，因此max函数内使用的f[i][j]实质上还是使用的是上一层的值，即为f[i-1][j]。因此可以看出当前的f[i][j]更新仅与本层有关系了（因为另一个f[i][j]实质上等于f[i-1][j]）。那我们可以优化为使用一维数组来进行存储。当前的f[i][j]更新时，由于f[i][j-v[i]]下标较小，因此会先进行更新，因此我们要从小到大进行更新。此时的f[i][j-v[i]]存储的即为本层的值。优化后的状态转移方程为f[j]=max(f[j],f[j-v[i]]+w[i])朴素做法：
- 定义一个二维数组
f[i][j]表示从前i个物品中选择，使得总体积不超过j的情况下可以达到的最大价值。- 不选择第
i个物品的情况为f[i-1][j]。- 选择第
i个物品的k个的情况为f[i-1][j-v[i]*k] + w[i]*k。- 因此，状态转移方程为：$$f[i][j]=max(f[i−1][j],f[i−1][j−v[i]]+w[i],f[i−1][j−v[i]×2]+w[i]×2,…,f[i−1][j−v[i]×k]+w[i]×k)$$
- 经过优化后，转移方程可以简化为：
滚动数组优化：
- 由于在更新
f[i][j]时，f[i][j]实际上使用的是上一层的值f[i-1][j]，因此可以将二维数组优化为一维数组。- 更新
f[j]时，需要从小到大进行更新，因为f[j-v[i]]存储的是本层的值。- 优化后的状态转移方程为：
线性DP问题
最长递增子序列（LIS）
定义一个
f[i]表示以nums[i]结尾的递增子序列。属性为max。集合可以划分为i个子集。分别是倒数第二个元素是0,倒数第二个元素时1，是2，……是i-1。因此如果有nums[i]>nums[j]则表示，可以在nums[j]后面加上nums[i]构成一个新的LIS。即f[i]=max{f[i],f[j]+1}变种
- 记录最长递增子序列的个数：定义一个
g[i]代表以nums[i]结尾的最长公共子序列有多少个。- 记录最长递增子序列下标：如果题目要求最后返回最长的递增子序列，那我们需要记录当前数具体是由哪一个状态的下标转移过来的。定义一个
g[i]代表以nums[i]结尾的最长公共子序列是由上一个下标为g[i]转移过来的。注：还原的序列是逆序的
int lengthOfLIS(vector<int>& nums) {
int n=nums.size();
vector<int> f(n,1);//单个元素的LIS为1
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(nums[i]>nums[j]){
f[i]=max(f[i],f[j]+1);
}
return *max_element(f.begin(),f.end());
}最长公共子序列问题（LCS）
定义
f[i][j]为所有由字符串A的前i个字符以及字符串B的前j个字符构成的子序列。属性为MAX。集合可以划分为四个部分，主要考虑第i个字符和第j个字符选不选。总共四个子集，分别是i,j都不选，即f[i-1][j-1]。选i不选j即f[i][j-1]。选j不选i，即f[i-1][j]。以及i,j都选即，f[i-1][j-1]+1。注：选i不选j即f[i][j-1]。选j不选i，即f[i-1][j]。这两种情况的表达式并不能精确的代表选i不选j，以及选j不选i。都是包含的关系，即f[i][j-1]包含选i不选j的情况。f[i-1][j]包含选j不选i的情况。但是由于我们求的是长度的最大值，因此可以重复。同时第一种情况不选i不选j也都包含在f[i][j-1]以及f[i-1][j]这两种情况内，因此可以省去，只比较三种情况。即最后的状态转移方程为f[i][j]=max(f[i][j-1],f[i-1][j],f[i-1][j-1]+1)。由于第三种情况f[i-1][j-1]+1不一定存在，因此需要加上判断A[i]==B[j]
动态规划定义
定义
f[i][j]表示所有由字符串A的前i个字符以及字符串B的前j个字符构成的子序列的长度属性
MAX状态转移方程
考虑以下几种情况：
- 不选
A[i]和B[j]：即f[i-1][j-1]。这种情况包含在1,2情况中，因此可以省略。- 选
A[i]不选B[j]：即f[i][j-1]。- 选
B[j]不选A[i]：即f[i-1][j]。- 选
A[i]和B[j]：如果A[i-1] == B[j-1]，则f[i][j] = f[i-1][j-1] + 1。如有
A[i]==B[j]则f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1] + 1);否则有
f[i][j] = max(f[i-1][j], f[i][j-1]);
小技巧
- 如果转移方程出现了i-1之类的可能会有负数的情况，我们可以将状态数组f整体往右边挪移一位。即
f[i+1][j+1] = max(f[i][j+1], f[i+1][j], f[i][j] + 1);
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int n=text1.size();
int m=text2.size();
vector<vector<int>> f(n+1,vector<int>(m+1,0));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
f[i+1][j+1]=max(f[i][j+1],f[i+1][j]);
if(text1[i]==text2[j])
f[i+1][j+1]=max(f[i+1][j+1],f[i][j]+1);
}
}
return f[n][m];
}
};区间DP问题
定义为
f[i][j]是所有由区间[i,j]字符组成的回文串的子序列的组成方式，属性为max，集合可以划分为三个子集，分别是，如果s[i]==s[j]那么可以表示为f[i+1][j-1]+2。意思是当前最长的回文串子序列长度等于子区间[l+1,r-1]+2。如果不相等，那么表示为max(f[i+1][j],f[i][j-1])。表示为子区间最长回文序列的长度。状态转移方程为f[i][j]=max(f[i][j-1],f[i+1][j],f[i+1][j-1]+2)注意：相等的情况不一定存在。关键点
- 求子序列不要求连续，求子串要求必须是连续的，状态属性修改为
bool。必须子区间为回文子串，当前区间才是。- 区间DP步骤：
- **遍历区间长度 **
- 遍历左端点，（右端点自动出现）
- 状态计算
- 初始化，求最大值最小值，可能会初始化为极端值
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n=s.size();
vector<vector<int>> f(n+1,vector<int>(n+1,0));
for(int i=1;i<=n;i++)
f[i][i]=1;
//枚举区间长度
for(int len=2;len<=n;len++){
for(int i=1;i+len-1<=n;i++){
//枚举区间左端点
int l=i,r=i+len-1;
f[l][r]=max(f[l+1][r],f[l][r-1]);
if(s[l-1]==s[r-1])
f[l][r]=max(f[l][r],f[l+1][r-1]+2);
}
}
return f[1][n];
}
};状态压缩DP问题
相邻有关系
对于前后两个元素有一定的限制关系，例如平方数题目，之类的。我们定义
f[s][i]表示，当前选择状态为s，同时最后一次选择第i个数。以倒数第二次选择的数来进行划分集合，可以划分为, 1,2,3,4….n。假设倒数第二次划分为k，同时第k个数必须满足相邻两个元素的条件。那么f[s][i]= f[s\{i}][k]表示当前的f[s][i]的值等于所有满足相邻元素条件，同时没有选择i，倒数第一次选择为k的方案数之和关键点
- 需要枚举满足条件的k，
- 由于需要表示
n位数是否被选择，每个数状态有，选择或者不选，因此我们需要使用mask=2^n来进行表示- 初始化，仅选择第i个数，同时最后选择为i的方案数为1
- 从集合中取出i，即
s^(1<<(i-1))
相邻无关系
对于前后两个数没有限制关系的，我们定义f[i][s],表示当前挑选i个数，同时选择第i个数后的状态为s。以最后一次挑选数来进行划分集合，可以划分为，1,2,3,4,…..n. 假设最后一次划分为k，可以表示为
f[i][s]=f[i-1][s\{j}]j从1-n。必须满足条件，如果j不在集合中，需要跳过本次循环。关键点
- 需要枚举最后一次选择的数。
子集型枚举
对于需要枚举子集型，一般可以采用回溯，或者进行状态压缩，一般定义
f[i][s]表示选择数量为i，选择状态为s的情况。以最后一次分配情况来进行划分集合，最后一次分配情况是，s的子集，状态划分有p1,p2,p3….pn。因此我们要根据最后一次的情况以及倒数第二次的情况来进行一个专一，例如
f[i][s]=min(f[i][s],max(f[i-1][s^p],sum[p]));。此时就是通过倒数第二次的分配情况与最后一次分配情况做对比来进行转移。关键点
- 对于子集型回溯，我们一般要进行一个预处理，将所有的子集的情况先处理出来。
- 枚举过程，可以是先枚举选择数量，再枚举状态，再枚举子集。
- 例子：以2305公平分发饼干为例
class Solution {
public:
const int INF=0x3f3f3f3f;
//使用状态压缩DP
int distributeCookies(vector<int>& cookies, int k) {
int n=cookies.size();
int mask=1<<n;
vector<int> sum(mask,0);//用于存储每个分配状态对应的不公平程度
vector<vector<int>> f(k+1,vector<int>(mask,INF));
//存储每个状态对应的不公平程度
for(int s=0;s<mask;s++){
for(int j=0;j<n;j++){
if(s&(1<<j))
sum[s]+=cookies[j];
}
}
f[0][0]=0;
//枚举每个小朋友
for(int i=1;i<=k;i++){
for(int s=0;s<mask;s++){
for(int p=s;p;p=s&(p-1)){
f[i][s]=min(f[i][s],max(f[i-1][s^p],sum[p]));
}
}
}
return f[k][mask-1];
}
};划分型DP问题
判断能否划分
定义
f[i]表示为前缀长度为i的序列能否成功进行划分，使用最后一次选择的子数组来进行划分集合。枚举最后一个子数组的左端点L，考虑从f[L]转移到f[i],同时要考虑序列a[L,i]是否满足要求
求划分最大值/最小值
定义
f[i]表示为前i个字符划分成有效子数组的最值。属性为min/max。使用最后一次选择的子数组来划分集合。枚举最后一次子数组的长度来进行。最后一次子数组的左端点会自动出来。即L=i-len+1。关键点
- 对于有些需要判断区间是否是回文串，我们会预处理一个DP数组，
DP[i][j]表示区间i-j是否是回文序列。此时，由于我们使用下标从1开始，因此我们如果得到了左端点L=i-len这个是相对于下标从0开始的。因此在这里我们需要加1，即判断DP[L+1][r]是否是回文。也就是判断区间[i-len+1,i]是否是回文。判断最后一次划分子数组长度为len
约束划分的个数
定义
f[i][j]表示为前i个字符划分为j个子区间的最优值。属性为min/sum/max。使用最后一次选择子数组来划分集合。枚举最后一次子数组的长度。左端点为L=i-len+1。考虑通过f[L-1]转移到f[i]
数位DP问题
引言：数位DP问题，题目一般会给定义区间
[L,R]。同时给定满足条件的数要求。要求返回区间内合法的数目。做法为算出1-R区间内的个数，减去1-L-1区间内的个数。即f(R)-f(L-1)
模板
定义为
f(i,mask,is_limit,is_num)表示构造第i位及其之后数位的合法方案数，其余参数的含义为：
mask表示前面选过的数字集合，换句话说，第i位要选的数字不能在mask中。isLimit表示当前是否受到了n的约束（注意要构造的数字不能超过 n）。若为真，则第i位填入的数字至多为s[i]，否则可以是 9。如果在受到约束的情况下填了 s[i]，那么后续填入的数字仍会受到 n 的约束。例如 n=123，那么 i=0 填的是 1 的话，i=1 的这一位至多填 2isNum表示i前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 1；若为真，则要填入的数字可以从 0 开始。例如 n=123，在 i=0 时跳过的话，相当于后面要构造的是一个 99 以内的数字了，如果 i=1 不跳过，那么相当于构造一个 10 到 99 的两位数，如果 i=1 跳过，相当于构造的是一个 9 以内的数字。易错点理解
添加缓存的条件
对于两种极端的情况，00000，以及前i为都有限制。此两种情况仅会出现一次。那么我们将其加入缓存也可以。
使用缓存的条件
当前状态没有限制，同时当前状态已经被计算过了，并且有些题要求没有前导0，因为，如果没有限制，那么也就意味着前面高位选择数小于n那么后面的数字可以任意的选择。因此可以复用状态选择相同的。例如:n=26 选择1,2，和选择2,1。后面选择任意数字他们的效果是一样的，因此可以复用
为什么
is_num==flase选择数字要从1开始？如果前面未选择数字，那么当前位置，一开始就可以不选，下面选择数字时候，就不能再从0开始计算了，这样会多计算一次，导致重复计算。
步骤：
- 如果有记忆化直接返回
- 是否允许前导0
- 确定上界
- 枚举当前要选择的数字
- 添加记忆化
string num;
int len;
vector<vector<int>> memo;
// DFS 递归函数
int dfs(int i, int mask, bool is_limit, bool is_num) {
if (i == len) {
return is_num ? 1 : 0; // 如果构造了一个合法的数则返回1
}
// 当前状态没有限制，同时已经计算过了。为什么可以复用？因为，如果没有限制，那么也就意味着前面高位选择数小于n那么后面的数字可以任意的选择。因此可以复用状态选择相同的。例如:n=26 选择1,2，和选择2,1。后面选择任意数字他们的效果是一样的，因此可以复用
if (!is_limit&& memo[i][mask] != -1) {
return memo[i][mask];
}
int res = 0;
// 如果前面没有选过数字，当前位可以跳过不选
if (!is_num) {
// 当前位不选数字,由于前面未选择数字当前也未选择，因此is_Num=false,is_limit=false;
res += dfs(i + 1, mask, false, false);
}
// 当前位可以选择的最大数字,如果前面有了限制，那么当前位能够选择的数字为0-nums[i],如果没有限制，那么可以选择0-9
int up = is_limit ? (num[i]-'0') : 9;
// 枚举当前位可以选择的数字，当前位可以选择的数字还要收到is_num的影响，如果前面选择了数字，那么当前为可以任意选，如果没有，那么仅能选择1-9，原因，为0的情况在前面已经计算过了一次，下面如果再从0开始，那么会造成重复计算。
for (int j = 1-is_num; j <= up; ++j) {
// 如果 j 已经在集合中，则跳过
if ((mask >> j) & 1) continue;
// 递归调用 dfs，更新 mask，如果前面有限制，当前选择的数又恰好等于up，则下面选择的数就有限制，当前选择了数字，因此is_Num为true
res += dfs(i + 1, mask | (1 << j), is_limit && j == up, true);
}
if(!is_limit&&is_num)
memo[i][mask] = res;//记忆化当前第i位的选择，同时前i个数状态选择为mask的限制下，满足条件的个数
return res;
}
//调用的函数
int count(string n){
num=n;
len=num.size();
memo=vector<vector<int>> (len+1,vector<int> (11,-1));
return dfs(0,0,true,false);
}状态机DP问题
对于状态机DP问题，一般定义
f[i][j]表示为在序列前缀[:i]在状态j的最优值下。例如股票系列。一般令最后一维表示状态。关键点
- 结尾元素可能不同的取值可能由不同的状态转移方程。例如可被三整除的最大和 ，2771. 构造最长非递减子数组
树形DP问题
树的直径问题
对于求树的直径问题，如果给的是一颗二叉树，那么直接考虑左右子树跟当前根节点之间的联系即可，如果不是，那么一般需要进行建树，类似建图。之后由底向上进行考虑每个节点作为根的最大直径，最大的直径一定是从叶子节点到叶子节点，否则还可以进行分叉。解题方法：考虑最大的直径当当前的节点进行分叉。那么就考虑当前节点的左右子树即可。
- 考虑边权的话，我们叶子节点返回0，可以在为null的是否返回-1，由于返回回来加上1之后就为0了。加上1是因为每个根节点到左右子树之间有一条边，因此要加1
- 由于每个节点都有可能作为出发点，因此我们需要再遍历的过程中去更新答案。
- 定义dfs(i)表示为当前以i为根节点作为分叉的最大直径，即max(left+1,rigt+1)
关键点
- 解题时要根据题目来，比如返回最大的即可。返回不为0的等
- 有些题目可能需要进行建树
int res=0;
int dfs(TreeNode *root){
if(root==nullptr)
return -1;
int lh=dfs(root->left)+1;
int rh=dfs(root->right)+1;
int len=lh+rh;
//此处更新时，可能会有一些限制，比如，相邻不能相同。
res=max(res,len);
return max(lh,rh);//当前根节点作为分叉的最大直径
}
class Solution {
public:
int res=0;
int dfs(int x,vector<vector<int>> &p,string &s){
int x_len=0;
for(int y:p[x]){
int y_len=dfs(y,p,s)+1;
if(s[y]==s[x])continue;//不能写在y_len的前面。
res=max(res,x_len+y_len);
x_len=max(x_len,y_len);
}
return x_len;
}
int longestPath(vector<int>& parent, string s) {
int n=parent.size();
vector<vector<int>> p(n+1);
//初始化邻接表
for(int i=1;i<n;i++){
p[parent[i]].emplace_back(i);
}
dfs(0,p,s);
return res+1;
}
};树上最大独立集
表示为在树上的打家劫舍。主要体现为抢了根节点，不能抢儿子节点，不抢根节点，则可以抢儿子节点，或者不抢。如果是二叉树，那么仅需要考虑两个分支即可，如果为多叉树，需要考虑全部的分支
- 选root：此时不能够选择儿子节点，那么rob=
不抢儿子节点最大值 +root 其中需要求出所有的不抢儿子节点的最大值之和。 - 不选root：此时可以选择儿子节点，也可以不选择儿子节点，因此not_rob=
max(抢儿子，不抢儿子) 如果不抢root那么儿子可以选也可以不选，最大值为所有儿子节点两种选择中的最大值之和。即抢儿子或者不抢儿子。 例子：树上打家劫舍，没有上司的舞会
关键点
- 对于多叉树，我们需要从没有父亲节点的节点出发，同时需要进行建树。
- 判断节点是否有父节点，采用
bool has_parent[N]- 定义
dfs(root)表示当前选或者不选当前root节点的最大值。返回值为{rob，not_rob}
typedef pair<int,int> PII;
class Solution {
public:
PII dfs(TreeNode *root){
if(root==nullptr)
return {0,0};
auto [l_rob,l_not_rob]=dfs(root->left);
auto [r_rob,r_not_rob]=dfs(root->right);
return {l_not_rob+r_not_rob+root->val,max(l_rob,l_not_rob)+max(r_rob,r_not_rob)};
}
int rob(TreeNode* root) {
auto [yes,no] =dfs(root);
return max(yes,no);
}
};7. 贪心
区间贪心
不相交区间
跟区间选点一致。按照区间的右端点进行排序
关键点
- 注意看清题目不相交的定义是什么。
class Solution {
public:
static const bool cmp(vector<int> &p1,vector<int> &p2){
return p1[1]<p2[1];
}
int findLongestChain(vector<vector<int>>& range) {
//将区间按照右端点进行排序。
sort(range.begin(),range.end(),cmp);
int n=range.size();
int res=0;
int ed=-2e9;
for(int i=0;i<n;i++){
//如果当前区间的左端点大于上个选点
if(range[i][0]>ed){
res++;
ed=range[i][1];
}
}
return res;
}
};区间分组
对于区间分组问题，我们希望将每个区间分配到不同的组，使得每个组内的区间都不相交。对于给定的区间
[l, r]，如果它可以放入某个组中，那么该组内的最大右端点ed必须满足ed < l。基于此，我们可以将问题分为两种情况来处理：
- 可以加入已有的组： 如果当前区间的左端点
l大于某个组的最大右端点ed（即ed < l），那么该区间可以放入这个组。为了高效地找到满足条件的组，我们可以使用一个最小堆（优先队列）来维护所有组的最大右端点。每次检查堆顶元素（即最小的最大右端点），如果满足heap.top() < l，则可以将当前区间放入该组，并更新该组的最大右端点为当前区间的右端点r。- 不可以加入任何已有的组： 如果当前区间的左端点
l小于等于堆顶元素（即heap.top() >= l），说明当前区间与所有已有组都有重叠。此时，无法将该区间加入任何已有的组，需要新开一个组，将当前区间的右端点r入堆，即heap.push(r)。
class Solution {
public:
int minGroups(vector<vector<int>>& range) {
//将区间按照左端点进行排序
sort(range.begin(),range.end());
//定义小跟堆
priority_queue<int,vector<int>,greater<int>> heap;//存放每个组中的最大右端点
int n=range.size();
for(int i=0;i<n;i++){
//判断当前组是否能够放入到某个组当中，条件为当前区间的左端点必须大于某个组的右端点，每次检查是否大于最小的最大右端点即可
if(heap.size()==0||heap.top()>=range[i][0])heap.push(range[i][1]);
else{
//将最小组的右端点移除堆。更新最小组的最大右端点
heap.pop();
heap.push(range[i][1]);
}
}
return heap.size();
}
};区间选点
对于区间选点的贪心问题，核心思路是尽可能选择较少的点来覆盖更多的区间。我们可以通过按区间的右端点进行升序排序来实现这一点。排序后，每次选择右端点作为选点，会比选择左端点覆盖更多的区间，从而减少所需的选点数量。
具体来说，可以分为两种情况：
- 当前区间的左端点小于等于上一个选的点（
l <= ed）：这表示当前区间已经被之前选定的点覆盖，因此无需新增选点，直接跳过该区间。- 当前区间的左端点大于上一个选的点（
l > ed）：这表示当前选的点无法覆盖该区间，因此需要选择一个新的点。为了覆盖尽可能多的后续区间，我们选择当前区间的右端点作为新的选点（ed = r）。
class Solution {
public:
// 改进：使用 const 引用以避免不必要的拷贝
static bool cmp(const vector<int>& p1, const vector<int>& p2) {
return p1[1] < p2[1]; // 按照区间的右端点进行升序排序
}
int findMinArrowShots(vector<vector<int>>& points) {
// 对区间按右端点排序，确保每次选的点能尽可能多地覆盖区间
sort(points.begin(), points.end(), cmp);
int n = points.size();
long long res = 0; // 记录需要的最少点数（箭数）
long long ed = -2e15; // 初始化为一个非常小的值，用于表示上一个选定的点（右端点）
for (int i = 0; i < n; i++) {
// 如果当前区间的左端点大于上一个选的点 ed，说明无法被当前的点覆盖
if (points[i][0] > ed) {
res++; // 需要新选一个点
ed = points[i][1]; // 更新当前选的点为新的区间的右端点
}
}
return res;
}
};区间覆盖
思路：对于区间覆盖问题，给定一个目标区间
[st, ed]，需要选择最少的子区间个数去完全覆盖这个区间。优化的策略是按照子区间的左端点进行排序。每次选择能够覆盖当前起点st的子区间中，右端点最大的那个区间。选择后，将st更新为这个区间的右端点。重复这一过程，直到st超过或等于目标区间的右端点ed，即表示目标区间已被完全覆盖。具体的步骤如下：
按照左端点排序：
- 先按照所有子区间的左端点进行升序排序。
选择最大右端点的区间：
初始化起点
st为目标区间的起始点。每次从已排序的子区间中，选择左端点小于等于
st的区间中，右端点最大的那个区间。这个区间能够最大程度地覆盖当前起点st。这一步使用双指针扫描剩余的区间更新起点：
选择一个区间后，将
st更新为这个区间的右端点。每选择一个区间，计数器加一。
检查覆盖
- 如果发现更新过后的st已经能够覆盖ed了，那么返回即可。
class Solution {
public:
int videoStitching(vector<vector<int>>& range, int time) {
// 按照区间的左端点进行排序，左端点相同的情况下按照右端点升序排列
sort(range.begin(), range.end());
int n = range.size(); // 获取区间数量
int res = 0; // 记录所需的最少区间个数
int st = 0; // 当前覆盖的起点
for (int i = 0; i < n; i++) {
int j = i; // j 用于从当前区间开始查找
int r = -2e9; // 记录能够覆盖的最远右端点，初始化为一个很小的值
// 找到所有左端点小于等于当前起点 st 的区间，并选择能够覆盖的最大右端点
while (j < n && range[j][0] <= st) {
r = max(r, range[j][1]); // 更新最大右端点
j++;
}
// 选择一个区间后，更新区间个数计数器
res++;
// 更新起点 st 为刚刚找到的最大右端点
st = r;
// 如果当前起点 st 已经大于或等于目标时间 time，说明已完成覆盖，返回结果
if (st >= time) return res;
}
// 如果无法覆盖整个区间，则返回 -1
return -1;
}
};区间合并
思路：按照区间的左端点进行排序。维护一个区间
[st,ed]。每次判断当前区间[l,r]能否并入上一个区间[st,ed]时，判断依据为如果当前区间的左端点l，如果有l<=ed说明可以并入，那么更新区间的右端点为ed=r。如果是l>ed说明不能并入，则将[st,ed]加入集合中，更新st=l,ed=r。最后遍历结束之后还需要将区间[st,ed]加入到集合中。因为最后一个区间合并之后并没有加入到集合中。具体步骤如下：
- 按照区间的左端点进行排序。
- 区间合并：维护一个当前区间
[st, ed]，表示正在合并的区间范围。对于每一个新区间[l, r]，我们需要判断它是否可以与当前的[st, ed]合并。判断依据是当前区间的左端点l是否小于等于当前区间的右端点ed。- 合并条件：
- 可以合并：如果
l <= ed，说明新区间[l, r]可以并入当前区间[st, ed]，则更新当前区间的右端点ed为max(ed, r)。- 不能合并：如果
l > ed，说明新区间[l, r]与当前区间[st, ed]不重叠，需要将当前区间[st, ed]加入到结果集合中，并开始一个新的区间[st, ed] = [l, r]。即st=l,ed=r- 结束处理：在遍历结束后，最后一个区间
[st, ed]仍需加入到结果集合中。这是因为最后一个区间在遍历过程中可能没有被添加到结果中，因此需要在遍历结束后手动将它加入。
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& range) {
sort(range.begin(),range.end());
vector<vector<int>> res;
int st=range[0][0],ed=range[0][1];
for(auto t:range){
//如果当前这个区间左端点小于等于上一个区间右端点，则合并
if(t[0]<=ed){
ed=max(ed,t[1]);
}else{
//否则不合并,将上个区间加入到集合中
res.push_back({st,ed});
st=t[0];
ed=t[1];
}
}
//最后还需要加入最后一个区间
res.push_back({st,ed});
return res;
}
};