当前位置: 首页 > news >正文

网站建设考试试卷百度网站收录入口

网站建设考试试卷,百度网站收录入口,网站制作 北京,做外贸网站动态规划(Dynamic Programming, DP)在字符串数组相关的算法题中应用广泛,尤其是在解决子序列、子串、编辑距离、匹配等问题时。动态规划的核心思想是将问题分解为子问题,并通过存储子问题的解来避免重复计算,从而提高效…

动态规划(Dynamic Programming, DP)在字符串数组相关的算法题中应用广泛,尤其是在解决子序列、子串、编辑距离、匹配等问题时。动态规划的核心思想是将问题分解为子问题,并通过存储子问题的解来避免重复计算,从而提高效率。

文章目录

  • 1143. Longest Common Subsequence
    • 问题描述
    • 解题思路
    • C++ 实现
  • 1092. Shortest Common Supersequence
    • 解题思路
    • C++ 实现

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.

Example 1:

Input: text1 = "abcde", text2 = "ace" 
Output: 3  
Explanation: The longest common subsequence is "ace" and its length is 3.

Example 2:

Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.

Example 3:

Input: text1 = "abc", text2 = "def"
Output: 0
Explanation: There is no such common subsequence, so the result is 0.

问题描述

给定两个字符串 s1s2,找到它们的最长公共子序列的长度。子序列是指从原字符串中删除一些字符(可以不连续)后得到的新字符串。

解题思路

  • 定义状态dp[i][j] 表示 s1 的前 i 个字符和 s2 的前 j 个字符的最长公共子序列长度。
  • 状态转移
    • 如果 s1[i-1] == s2[j-1],则 dp[i][j] = dp[i-1][j-1] + 1
    • 否则,dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  • 初始化dp[0][j] = 0dp[i][0] = 0,表示空字符串的 LCS 长度为 0。
  • 结果dp[m][n],其中 mn 分别是 s1s2 的长度。

C++ 实现

int longestCommonSubsequence(string s1, string s2) {int m = s1.length(), n = s2.length();vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (s1[i - 1] == s2[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];
}

1092. Shortest Common Supersequence

Given two strings str1 and str2, return the shortest string that has both str1 and str2 as subsequences. If there are multiple valid strings, return any of them.

A string s is a subsequence of string t if deleting some number of characters from t (possibly 0) results in the string s.

Example 1:

Input: str1 = "abac", str2 = "cab"
Output: "cabac"
Explanation: 
str1 = "abac" is a subsequence of "cabac" because we can delete the first "c".
str2 = "cab" is a subsequence of "cabac" because we can delete the last "ac".
The answer provided is the shortest such string that satisfies these properties.

Example 2:

Input: str1 = "aaaaaaaa", str2 = "aaaaaaaa"
Output: "aaaaaaaa"

解题思路

这个问题可以转化为求两个字符串的最长公共子序列(LCS),然后通过 LCS 构造最短的公共超序列。

构造最短公共超序列

  • 初始化指针:
    • 使用指针 ij 分别遍历 str1str2
  • 遍历字符串:
    • 如果 str1[i] == str2[j],则将当前字符添加到结果中,并移动两个指针。
    • 否则,将 str1[i]str2[j] 中较小的字符添加到结果中,并移动对应的指针。
  • 处理剩余字符:
    • 如果 str1str2 有剩余字符,将它们全部添加到结果中。

C++ 实现

string shortestCommonSupersequence(string str1, string str2) {int m = str1.length(), n = str2.length();// 动态规划求 LCSvector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (str1[i - 1] == str2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 构造最短公共超序列string result;int i = m, j = n;while (i > 0 && j > 0) {if (str1[i - 1] == str2[j - 1]) {result.push_back(str1[i - 1]);i--;j--;} else if (dp[i - 1][j] > dp[i][j - 1]) {result.push_back(str1[i - 1]);i--;} else {result.push_back(str2[j - 1]);j--;}}// 处理剩余字符while (i > 0) {result.push_back(str1[i - 1]);i--;}while (j > 0) {result.push_back(str2[j - 1]);j--;}// 反转结果reverse(result.begin(), result.end());return result;
}
http://www.cadmedia.cn/news/1760.html

相关文章:

  • 成都b2b网站建设广告营销公司
  • 百度 医疗网站建设网站seo提升
  • 视频制作软件哪个好 前十名网站外链优化方法
  • 企业设计网站公司湖南省人民政府官网
  • seo整站网站推广优化排名深圳网站开发公司
  • 单机游戏网页版东莞网站seo优化托管
  • 贵阳做网站的大公司有哪些最近中国新闻热点大事件
  • 泽成seo网站排名深圳网络推广服务是什么
  • 苏州正规制作网站公司重庆森林百度网盘
  • 潍坊网站制作报价网站排名优化制作
  • app定制网站开发网站推广公司哪家好
  • 惠州水口网站建设百度投诉电话人工服务总部
  • asp 公司网站公众号关键词排名优化
  • 崇明建设小学网站企业网站有哪些平台
  • 无锡网站制作计划广告优化师前景怎样
  • 建网站潞城哪家强?网站优化排名推广
  • 厦门建设网站制作安徽做网站公司哪家好
  • 做网站的公司还市场吗网店推广的重要性
  • 网站赚钱方法优秀的品牌策划案例
  • 福建省建设行业企业资质查询网站seo技术论坛
  • 个人网站建设维护搜索引擎分哪三类
  • 建站网站建设百度免费建网站
  • 成全视频在线观看免费看seo软文是什么意思
  • 优秀自适应网站建设哪家好什么是电商
  • 网站文明专栏建设阿里云域名
  • 国家税务总局网站官网网址seo分析报告
  • 电子科技产品东莞网站建设优化软件有哪些
  • wx5 做网站可以么seo月薪
  • 网站页面布局分析湖北网站seo设计
  • 佛山建设银行社会招聘网站google推广平台怎么做