常用算法里的细节

👨‍💻 关于作者：会编程的土豆

“不是因为看见希望才坚持，而是坚持了才看见希望。”

你好，我是会编程的土豆，一名热爱后端技术的Java学习者。

📚正在更新中的专栏：

• 《数据结构与算法》😊😊😊

• 《leetcode hot 100》🥰🥰🥰🤩🤩🤩

• 《数据库mysql》

💕作者简介：后端学习者

LCS模版（最长公共子序列（Longest Common Subsequence））

仅求长度

• 若字符相等：dp[i][j] = dp[i-1][j-1] + 1

• 若字符不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

int longestCommonSubsequence(string text1, string text2) { int n = text1.size(), m = text2.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (text1[i - 1] == text2[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[n][m]; }

这里注意因为i，j记录的是前s的i个字符和t的前j个字符中的公共子序列，由于字符下标是从0开始的，所以实际上i只记录到下标为i-1的数，j也是同理；所以if对比的时候记得是对比s[i-1]==t[j-1];记得要减一；

回溯具体子序列

在 DP 填表完成后，从右下角(n, m)倒推回去

string getLCS(string text1, string text2) { int n = text1.size(), m = text2.size(); vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); // 1. 填表 for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (text1[i - 1] == text2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); } } // 2. 回溯构建 LCS 字符串 string lcs; int i = n, j = m; while (i > 0 && j > 0) { // 如果字符相等，它是LCS的一部分，往左上移动 if (text1[i - 1] == text2[j - 1]) { lcs.push_back(text1[i - 1]); i--; j--; } // 如果不相等，走向数值较大的那个方向 else if (dp[i - 1][j] > dp[i][j - 1]) { i--; } else { j--; } } reverse(lcs.begin(), lcs.end()); return lcs; }

LIS（最长上升子序列（Longest Increasing Subsequence, LIS））

这个是求一个字符串中或者数组中最长上升的那个子序列；

元素可以一样的用upper_bound

vector<int>tail; for (int i = 0; i < arr.size(); i++) { int x = arr[i]; auto it = upper_bound(tail.begin(), tail.end(), x); if (it == tail.end()) { tail.push_back(x); } else *it = x; } cout << tail.size() << endl;

这个是求arr数组的最长可以一样元素的最长子序列；

元素不可以一样的用lower_bound

vector<int>tailb; for (int i = 0; i < arr.size(); i++) { int x = arr[i]; auto it = lower_bound(tailb.begin(), tailb.end(), x); if (it == tailb.end()) { tailb.push_back(x); } else *it = x; } cout << tailb.size() << endl;

这个是求arr数组的最长子序列，必须严格递增；

注意里面的操作都是关于tail数组的操作，tail数组就是记录最长子序列元素的数组，而且是保证里面的每个值尽可能小；