【算法笔记】刷题记录-week13
水木清研OJ：http://59.110.82.144/
20250519-动态规划
最长公共子序列-模板
- 最长公共子序列的经典思路是比较最后一个元素是否相等
假设一个最优子结构情况，对于一个序列$$Z = {z_1, z_2, \ldots, z_k}$$是$$X = {x_1, x_2, \ldots, x_m}$$和$$Y = {y_1, y_2, \ldots, y_n}$$的最长公共子序列。根据对最后一个元素考虑，我们可以分成三种情况来具体讨论：
（1）$$x_m = y_n = z_k$$
- 将$$x_m$$和$$y_n$$的值作为序列$$Z$$的最后一个元素，如果去掉$$x_m$$和$$y_n$$，那么对于序列$$Z$$的最长公共子序列的长度肯定会减小1，即$$c[i - 1][j - 1] = c[i][j] - 1$$；因此，当$$x_m = y_n$$时的递推公式是：$$c[i][j] = c[i - 1][j - 1] + 1$$；
（2）若$$x_m \neq y_n$$且$$z_k \neq x_m$$，则$Z$是$$X-x_m$$和$Y$的最长公共子序列。
（3）若$$x_m \neq y_n$$且$$z_k \neq y_n$$，则$Z$是$X$和$$Y-y_n$$的最长公共子序列。
则递推式：
对于$$c[i][j]$$数组：指只取$$X$$前$$i$$个元素和只取$$Y$$前$$j$$个元素能够得到的最长公共子序列的值（即存放最优子结构的值）。
由1）可知，如果$$x_i = y_j$$，那么可以从没有$$xi$$和$$yj$$的最优子结构即$$c[i - 1][j - 1]$$转移过来，即
$$
c[i][j] = c[i - 1][j - 1] + 1
$$
由2）3）可知，如果$$x_i \neq y_j$$，那么我们只需要取$$x_i$$和$$y_{j-1}$$最优子结构和$$x_{i-1}$$和$$y_j$$最优子结构的最大长度即可，即
$$
c[i][j] = \max(c[i][j - 1], c[i - 1][j])
$$
int main() |
20250520-动态规划、贪心算法、STL
STL-vector
参考博客：https://blog.csdn.net/weixin_45031801/article/details/134769122
头文件
或者
#include <bits/stdc++.h> |
#include <bits/stdc++.h>头文件，它是一个非标准的头文件，通常由一些编译器（如 GCC）提供。这个头文件包含了大量的标准库头文件，包括<vector>、<iostream>、<algorithm>等等。
初始化
- 方式一：构造一个某类型的空容器:
- vector<数据类型> 函数名; 初始化为空。
vector<int> v1; //构造int类型的空容器 |
方式二：构造一个含有n个val的某类型容器:
- vector<数据类型> 函数名(a,b).定义a个空间，都初始化为b。
vector<int> v2(10, 2); //构造含有10个2的int类型容器 |
方式三：拷贝构造某类型容器的复制品:
- vector<数据类型> 函数名1（函数名2)，把动态数据2复制给动态数组1
vector<int> v3(v2); //拷贝构造int类型的v2容器的复制品 |
方式四：使用迭代器拷贝构造某一段内容:
- vector<数据类型> 函数名1(函数名2.begin(),函数名2.end())把动态数组2复制给动态数组1。
vector<int> v4(v2.begin(), v2.end()); //使用迭代器拷贝构造v2容器的某一段内容 |
- 方式五：迭代器构造函数也可以使用数组来进行构造，传的区间是左闭右开
vector<int> 函数名(a,a+sizeof(a)/sizeof(数据类型))，把普通数组a复制给动态数组。 |
注意：该方式也可用于拷贝其他容器的某一段内容。
string s("hello world"); |
示例代码
|
访问数组元素
使用“下标+[]”的方式遍历容器
|
迭代器（指针）
| 接口名称 | 使用说明 |
|---|---|
| begin() | 返回指向第一个元素的迭代器 |
| end() | 返回指向最后一个元素的下一个位置的迭代器 |
| rbegin() | 返回指向最后一个元素的反向迭代器 |
| rend() | 返回指向第一个元素的前一个位置的反向迭代器 |
示例代码
|
访问操作
| 接口名称 | 接口说明 |
|---|---|
| back() | 返回容器中最后的一个元素的引用 |
| front() | 返回容器中第一个元素的引用 |
int main() |
修改操作
| 接口名称 | 接口说明 |
|---|---|
| push_back() | 在末尾添加一个元素，有效元素个数加1 |
| pop_back() | 删除最后一个元素，有效元素个数减1 |
int main() |
容量操作
| 接口名称 | 接口说明 |
|---|---|
| size() | 返回容器中有效元素个数 |
最长公共子序列-变体
给出两个长度为$n$的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。
注意：
- 第一个序列中的所有元素均不重复。
- 第二个序列中可能有重复元素。
- 一个序列中的某些元素可能不在另一个序列中出现。
序列的个数$n\leq10^6$，故无法像模板题一样用二维数组用于存储状态（数组太大了超出限制了）
编译报错如下
全局变量/静态变量过大： 如果你的程序包含了非常大的全局变量或静态数组，可能会导致它们的地址超出 ARM64 的可寻址范围。
思路
因为公共子序列中值的相同的，所以数组2中公共子序列中的值放到数组1中数组下标仍然相同。所以：求公共子序列因为不用求具体的序列是多少，我们转化为求公共子序列的下标，因为下标是递增的。 所以转化为求最长上升子序列,这个序列是值下表的序列
示例代码
|
lower_bound(begin , end , val , less<type>() )从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。
std::lower_bound
- 作用: 返回第一个 大于等于 (
>=) 指定值的元素的迭代器。 - 如果值存在: 返回该值的第一个位置。
- 如果值不存在: 返回比目标值 大的第一个元素 位置。
- 如果所有元素都小于目标值: 返回
end()迭代器。 - 反向查找小于目标值的元素:
std::lower_bound返回的迭代器减一，即std::lower_bound(vec.begin(), vec.end(), target) - 1。
std::upper_bound
- 作用: 返回第一个 大于 (
>) 指定值的元素的迭代器。 - 如果值存在: 跳过所有相同值，返回比目标值 大的第一个元素 位置。
- 如果值不存在: 返回比目标值 大的第一个元素 位置。
- 如果所有元素都小于等于目标值: 返回
end()迭代器。 - 反向查找小于等于目标值的元素:
std::upper_bound返回的迭代器减一，即std::upper_bound(vec.begin(), vec.end(), target) - 1。
20250522-动态规划
编辑距离
两个字串之间，由一个转换成另一个所需的最少编辑操作次数
$D[i][j]$ 代表着word1的前i个字符转换成word2的前j个字符所需要的最少操作步数，
当我们获得 $$D[i][j-1]$$，$$D[i-1][j]$$ 和 $$D[i-1][j-1]$$ 的值之后就可以计算出 $$D[i][j]$$ 。
增：$$D[i][j-1]$$ 为 A 的前 i 个字符和 B 的前 j - 1 个字符编辑距离的子问题。即对于 B 的第 j 个字符，我们在 A 的末尾添加了一个相同的字符，那么 $$D[i][j]$$ 最小可以为 $$D[i][j-1] + 1$$；
删：$$D[i-1][j]$$ 为 A 的前 i - 1 个字符和 B 的前 j 个字符编辑距离的子问题。我们在 A 的末尾删去了一个字符（第 i 个字符），那么 $$D[i][j]$$ 最小可以为 $$D[i-1][j] + 1$$；
改：$$D[i-1][j-1]$$ 为 A 前 i - 1 个字符和 B 的前 j - 1 个字符编辑距离的子问题。
- 对于 B 的第 j 个字符，我们修改 A 的第 i 个字符使它们相同，那么 $$D[i][j]$$ 最小可以为 $$D[i-1][j-1] + 1$$。
- 特别地，如果 A 的第 i 个字符和 B 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，$$D[i][j]$$ 最小可以为 $$D[i-1][j-1]$$ 。
那么我们可以写出如下的状态转移方程：
- 若 A 和 B 的最后一个字母相同：
$$
D[i][j] = \min(D[i][j - 1] + 1, D[i - 1][j] + 1, D[i - 1][j - 1])
= 1 + \min(D[i][j - 1], D[i - 1][j], D[i - 1][j - 1])
$$
- 若 A 和 B 的最后一个字母不同：
$$
D[i][j] = 1 + \min(D[i][j - 1], D[i - 1][j], D[i - 1][j - 1])
$$
初始化：通过前面的数组之间的关系式，我们可以知道表达式左侧i和j的值最小从1开始，不能为0，因为如果为0的话，表达式右侧数组坐标就会出现负值了。因此我们需要得到$dp[0][j]$和$dp[i][0]$
对于$dp[0][j]$来说，意味着将长度为0的字符串转换为长度为j的字符串，因此执行的操作就是不断的插入值，总共需要j步。因此 $dp[0][j] = j$，同理有 $dp[i][0] = i$
const int N = 1010; |
