最长共同子序列代码
最编程
2024-10-18 07:17:02
...
问题分析:
最长公共子序列指的是,给定两个字符串,我们需要找出它们都包含的最长子序列。这个子序列不要求是连续的,但它的字符顺序必须保持一致。
算法步骤:
-
定义状态(DP 表):
- 我们使用一个二维数组
dp
来存储状态,其中dp[i][j]
表示字符串text1
的前i
个字符和字符串text2
的前j
个字符的最长公共子序列的长度。
- 我们使用一个二维数组
-
状态转移方程:
- 如果
text1[i-1] == text2[j-1]
,即当前两个字符相等,那么dp[i][j] = dp[i-1][j-1] + 1
。这是因为当前的两个字符都可以加入公共子序列中,因此子序列长度加 1。 - 如果
text1[i-1] != text2[j-1]
,即当前字符不相等,那么dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1])
。这是因为我们需要从两个选择中取最大值:要么不考虑text1[i-1]
,要么不考虑text2[j-1]
,来找到更长的子序列。
- 如果
-
初始状态:
-
dp[0][*]
和dp[*][0]
的值均为 0,因为如果任意一个字符串的长度为 0,那么最长公共子序列的长度也必然为 0。
-
-
最终结果:
- 当我们遍历完所有的字符后,
dp[m][n]
(其中m
和n
分别是text1
和text2
的长度)就会存储两个字符串的最长公共子序列的长度。
- 当我们遍历完所有的字符后,
时间复杂度和空间复杂度:
-
时间复杂度:O(m * n),其中 m 和 n 分别是字符串
text1
和text2
的长度。我们需要遍历m * n
个状态来填充 dp 表。 - 空间复杂度:O(m * n),用于存储 dp 表格。
示例解释:
对于输入 text1 = "abcde"
和 text2 = "ace"
,通过动态规划构造 dp 表后,结果为 3,表示它们的最长公共子序列为 "ace"
。
总结起来,这个算法通过构建一个二维数组,逐个字符进行比较,逐步累积最长的公共子序列的长度,从而得到最终的解。
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length();
int n = text2.length();
//dp[i][j] 的含义是字符串 text1 的前 i 个字符与字符串 text2 的前 j 个字符之间的最长公共子序列长度
int[][] dp = new int[m + 1][n + 1];
//更新dp
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
//text1 的前 i-1 个字符与字符串 text2 的前 j-1 个字符的LCS + 1
//是text1 的前 i 个字符与字符串 text2 的前 j 个字符的LCS
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
//text1 的前 i 个字符与字符串 text2 的前 j 个字符的LCS
//从text1 的前 i-1 个字符与字符串 text2 的前 j 个字符的LCS和text1 的前 i 个字符与字符串 text2 的前 j-1 个字符的LCS
//选择更大者
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
}
上一篇: qgis3.32 安装包
推荐阅读
-
最长共同子序列代码
-
[LeetCode] 动态编程 - 5.最长回声子串(含完整 Python/C++ 代码) - 前言
-
用递归解决最长公共子序列问题(LCS)的方法
-
LeetCode问题300:找寻最长上升子序列 - 暴力递归方法(效率低至O(n^3))、动态规划优化(提升到O(n^2))、结合动态规划与二分查找的高效解决方案(达到O(nlogn))
-
最长公共子序列, 1035.
-
如何查找字符串中最长的回文子序列的长度?
-
vue 源代码分析 - diff 算法/双端比较/patchFlag/最长增量子序列
-
日55 最长递增子序列 最长连续递增子序列 最长重复子数组
-
最长斐波那契子序列选择(离散化 + 二分法 + DP)
-
MAX_LEN) {
int pivot = partition(arr, left, right);
quicksort_optimized(arr, left, pivot - 1);
quicksort_optimized(arr, pivot + 1, right);
} else {
// 使用插入排序处理小数组
}
}
```
- 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如:
原序列: 1 4 6 7 6 6 7 6 8 6
- 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6
- 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6
- 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7
- 下次划分得到的子序列:1 4 和 7 8 7
通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。">
改进版快速排序:针对部分有序列的策略与优化技巧" - 随机选枢轴:当数据部分有序时,传统快速排序通过固定枢轴可能导致效率低下。为此,我们采用随机选取枢轴的方法,代码如下: ```c int SelectPivotRandom(int arr[], int low, int high) { srand(time(0)); int pivotPos = (rand() % (high - low)) + low; swap(arr[pivotPos], arr[low]); return arr[low]; } ``` - 优化小数组交换:针对小且部分有序的数组,快速排序不如插入排序高效。因此,当待排序序列长度小于等于10时,我们会切换至插入排序: ```c #define MAX_LEN 10 void quicksort_optimized(int *arr, int left, int right) { int length = right - left; if (length > MAX_LEN) { int pivot = partition(arr, left, right); quicksort_optimized(arr, left, pivot - 1); quicksort_optimized(arr, pivot + 1, right); } else { // 使用插入排序处理小数组 } } ``` - 合并相同值进行分割:在每次划分后,我们将与枢轴相等的元素聚集在一起,以降低后续迭代中的重复处理。例如: 原序列: 1 4 6 7 6 6 7 6 8 6 - 选取枢轴(6)并划分:1 4 6 7 1 6 7 6 8 6 - 划分结果(未处理相等项):1 4 6 6 7 6 7 6 8 6 - 处理相等项后的划分结果:1 4 6 6 6 6 7 8 7 - 下次划分得到的子序列:1 4 和 7 8 7 通过这样的优化,我们可以明显减少迭代次数,从而提高排序效率。