企业官网建设流程全解析

网站空间搭建,怎么建立自己的网站卖东西,企业管理有哪些课程,中文域名有哪些网站题目描述给定两个字符串 text1 和 text2#xff0c;返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 #xff0c;返回 0 。一个字符串的 子序列 是指这样一个新的字符串#xff1a;它是由原字符串在不改变字符的相对顺序的情况下删除某些字符#xff08;…题目描述给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列返回0。一个字符串的子序列是指这样一个新的字符串它是由原字符串在不改变字符的相对顺序的情况下删除某些字符也可以不删除任何字符后组成的新字符串。例如ace是abcde的子序列但aec不是abcde的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。示例 1输入text1 abcde, text2 ace输出3解释最长公共子序列是 ace 它的长度为 3 。示例 2输入text1 abc, text2 abc输出3解释最长公共子序列是 abc 它的长度为 3 。示例 3输入text1 abc, text2 def输出0解释两个字符串没有公共子序列返回 0 。提示1 text1.length, text2.length 1000text1和text2仅由小写英文字符组成。解决方案一这段代码的核心功能是求解两个字符串的最长公共子序列LCS长度采用「类内辅助函数 记忆化递归」的思路实现通过缓存子问题结果避免重复计算将暴力递归的指数级复杂度优化为多项式级别是 LCS 问题的经典高效解法。核心逻辑成员变量作用s_/t_类内备份的两个输入字符串供辅助递归函数dfs直接访问无需频繁传参memo二维记忆化数组n×mn/m分别为s/t的长度memo[i][j] -1表示子问题dfs(i,j)未计算计算后缓存结果替代 Python 的cache装饰器。辅助递归函数dfs(i,j)逻辑参数含义i/j分别表示考虑s[0..i]和t[0..j]的子串范围递归边界i0或j0任一子串遍历完毕LCS 长度为 0记忆化优化若memo[i][j]≠-1直接返回缓存值避免重复递归核心状态转移字符相等s_[i]t_[j]时该字符属于 LCS长度 dfs(i-1,j-1)1前i-1/j-1的 LCS 长度 1字符不等取max(dfs(i-1,j), dfs(i,j-1))删s[i]或删t[j]后的 LCS 最大值结果缓存将计算结果存入memo[i][j]统一返回。主函数longestCommonSubsequence逻辑初始化备份输入字符串到s_/t_初始化memo为n×m的二维数组初始值 - 1启动递归从两个字符串的最后一个字符in-1,jm-1开始计算返回最终 LCS 长度。关键特点效率优化记忆化数组memo将时间复杂度从O(2nm)降至O(n×m)空间复杂度为O(n×m)存储记忆化数组逻辑清晰递归函数聚焦 “当前字符是否相等” 的二选一决策符合 LCS 的动态规划状态转移本质封装性好辅助函数设为类内私有通过成员变量共享状态对外仅暴露简洁的接口。总结核心思路用记忆化递归缓存子问题结果通过 “字符相等 / 不等” 的状态转移求解 LCS 长度关键操作memo数组的缓存是效率核心避免重复计算相同子问题功能效果能高效求解任意两个字符串的 LCS 长度无重复计算、无遗漏符合工程化编程规范。以输入sabcde、tace为例最终返回3LCS 为 ace完全符合预期。函数源码一class Solution { public: // 类内成员变量存储输入字符串记忆化数组替代cache string s_; string t_; vectorvectorint memo; // memo[i][j] 缓存 dfs(i,j) 的结果 // 辅助递归函数dfs(i,j) 表示 s[0..i] 和 t[0..j] 的最长公共子序列长度 int dfs(int i, int j) { // 递归边界任一字符串遍历完LCS长度为0 if (i 0 || j 0) { return 0; } // 记忆化优化已计算过该子问题直接返回缓存值 if (memo[i][j] ! -1) { return memo[i][j]; } int res 0; // 状态转移1当前字符相等LCS长度1 if (s_[i] t_[j]) { res dfs(i - 1, j - 1) 1; } // 状态转移2当前字符不等取“删s[i]”或“删t[j]”的最大值 else { res max(dfs(i - 1, j), dfs(i, j - 1)); } // 缓存结果避免重复计算 return memo[i][j] res; } int longestCommonSubsequence(string s, string t) { int n s.size(), m t.size(); // 初始化类内成员变量 s_ s; t_ t; // 初始化记忆化数组n行m列初始值-1表示未计算 memo.assign(n, vectorint(m, -1)); // 从两个字符串的最后一个字符开始递归 return dfs(n - 1, m - 1); } };解决方案二这段代码的核心功能是用迭代版动态规划DP求解两个字符串的最长公共子序列LCS长度相比递归记忆化版本更高效无递归调用开销是 LCS 问题的最优迭代解法。核心逻辑DP 数组定义dp[i][j]表示text1[0..i-1]前 i 个字符和text2[0..j-1]前 j 个字符的最长公共子序列长度。之所以用i-1/j-1而非i/j是为了让dp[0][j]和dp[i][0]自然表示 “空串与任意子串” 的 LCS 长度值为 0无需额外处理边界。初始化构建(m1)×(n1)的二维数组dp所有元素初始化为 0。这是因为 “空串和任何字符串的 LCS 长度都是 0”对应dp[0][*] 0、dp[*][0] 0天然满足递归边界条件。状态转移核心迭代逻辑双层循环遍历两个字符串的所有字符组合i从 1 到 mj从 1 到 n若text1[i-1] text2[j-1]当前字符属于 LCSdp[i][j] dp[i-1][j-1] 1前 i-1/j-1 个字符的 LCS 长度 1若字符不相等取 “删 text1 第 i 个字符” 或 “删 text2 第 j 个字符” 的最大值即dp[i][j] max(dp[i-1][j], dp[i][j-1])。结果输出dp[m][n]存储了text1完整字符串和text2完整字符串的 LCS 长度直接返回该值即可。关键特点无递归开销迭代方式避免了递归的函数调用栈开销空间 / 时间效率更优边界简化通过dp数组多开一行一列索引 0天然处理空串边界无需额外判断时间复杂度O(m×n)、空间复杂度O(m×n)是 LCS 问题的标准迭代解法。总结核心思路用二维 DP 数组自底向上迭代计算所有子问题避免递归重复计算关键设计DP 数组索引偏移i-1/j-1简化边界处理状态转移逻辑与递归版完全一致功能效果高效求解 LCS 长度是工程中更常用的迭代实现方式。以text1abcde、text2ace为例最终dp[5][3] 3LCS 为 ace与递归版结果一致且执行效率更高。函数源码二class Solution { public: int longestCommonSubsequence(string text1, string text2) { int m text1.size(); int n text2.size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); for (int i 1; i m; i) { for (int j 1; j n; 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[m][n]; } };