安平网站建设,网上营销的概念,网站建设哪个平台好,云服务器是虚拟技术吗编辑距离题目描述设 AA 和 BB 是两个字符串。我们要用最少的字符操作次数#xff0c;将字符串 AA 转换为字符串 BB。这里所说的字符操作共有三种#xff1a;删除一个字符#xff1b;插入一个字符#xff1b;将一个字符改为另一个字符。A, BA,B 均只包含小写字母。输入格式第…编辑距离题目描述设 AA 和 BB 是两个字符串。我们要用最少的字符操作次数将字符串 AA 转换为字符串 BB。这里所说的字符操作共有三种删除一个字符插入一个字符将一个字符改为另一个字符。A, BA,B 均只包含小写字母。输入格式第一行为字符串 AA第二行为字符串 BB字符串 A, BA,B 的长度均小于 20002000。输出格式只有一个正整数为最少字符操作次数。输入输出样例输入 #1复制sfdqxbwgfdgw输出 #1复制4说明/提示对于 100 \%100% 的数据1 \le |A|, |B| \le 20001≤∣A∣,∣B∣≤2000。思路第一步确定dp数组的含义以i-1结尾和j-1结尾的串相同所要操作的最小次数第二步寻找状态转移方程寻找状态转移方程的时候我们先要知道删除和增添操作所产生的效果是一样的例如abcde和abc要变成相同的字符串我们可以在串一删除也可以在串二中增添也可以串一增添串二删除同时操作所以我们可以找到:if(a1[i]a2[j])dp[i][j]dp[i-1][j-1]//相等的情况else //不相等的情况需要进行操作dp[i][j]mindp[i][j-1]1dp[i-1][j],dp[i-1][j-1]//分别对应删除串2删除串1和替换操作第三步初始化dp[0][i]i,dp[i][0]i;code#includestdio.h
#includestring.h
#includestdlib.h
#includemath.h
int min_(int x,int y,int z)
{if(yx)yx;if(zy)zy;return z;
}
int main()
{char s1[2005],s2[2005];scanf(%s,s1);scanf(%s,s2);int dp[2005][2005];int nstrlen(s1),mstrlen(s2);//初始化for(int i0;in;i){dp[i][0]i;}for(int i0;im;i){dp[0][i]i;}//dp过程for(int i1;in;i){for(int j1;jm;j){if(s1[i-1]s2[j-1])dp[i][j]dp[i-1][j-1];//相等则不用删除和替换操作else{dp[i][j]min_(dp[i][j-1]1,dp[i-1][j]1,dp[i-1][j-1]1);//不相等的情况删除和替换}}}printf(%d,dp[n][m]);
}最长递增子序列题目描述给你一个整数数组 nums 找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列删除或不删除数组中的元素而不改变其余元素的顺序。例如[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。示例 1输入nums [10,9,2,5,3,7,101,18]输出4解释最长递增子序列是 [2,3,7,101]因此长度为 4 。示例 2输入nums [0,1,0,3,2,3]输出4示例 3输入nums [7,7,7,7,7,7,7]输出1提示1 nums.length 2500-104 nums[i] 104 思路:第一步找dp数组的含义i(包括i)的最小上升子序列第二步找状态转移方程if(nums[i]nums[j])dp[i]max(dp[j]1,dp[i];第三步初始化因为所有的位置自身也是一个序列。所以dp全部初始化为1;code:class Solution
{
public:int lengthOfLIS(vectorint nums){vectorint dp(2505,1);//全部初始化为1int nnums.size();int ans0;if(n1)return n;//特判一下数组长度为1和0for(int i1;in;i){for(int j0;ji;j){if(nums[i]nums[j])//此时为递增{dp[i]max(dp[j]1,dp[i]);}}if(ansdp[i])ansdp[i];}return ans;}
}; 最长连续递增序列题目描述给定一个未经排序的整数数组找到最长且 连续递增的子序列并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 rl r确定如果对于每个 l i r都有 nums[i] nums[i 1] 那么子序列 [nums[l], nums[l 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。示例 1输入nums [1,3,5,4,7]输出3解释最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的因为 5 和 7 在原数组里被 4 隔开。 示例 2输入nums [2,2,2,2,2]输出1解释最长连续递增序列是 [2], 长度为1。提示1 nums.length 104-109 nums[i] 109思路:第一步找dp数组的含义dp数组i包括i之前的字符最大连续序列的个数第二步找状态转移方程:if(a[i]a[i-1])dp[i]dp[i]1,dp[i-1];第三步初始化code:class Solution
{
public:int findLengthOfLCIS(vectorint nums) {int nnums.size(),ans0;vectorintdp(n,1);if(n1)return 1;for(int i1;in;i){if(nums[i-1]nums[i]){dp[i]dp[i-1]1;}ansmax(ans,dp[i]);}return ans;}
};最长重复子数组题目描述给定两个字符串 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 仅由小写英文字符组成。思路第一步确定dp数组的含义dp[i][j]:下标i - 1为结尾的A和以下标j - 1为结尾的B最长重复⼦数组长度。第二步找状态转移方程if(a1[i]a2[j])dp[i][j]dp[i-1][j-1]else dp[i][j]dp[i-1][j],dp[i][j-1]第三步初始化因为空串不会和另一个串有公共子数组所以我们初始化为0即可code:class Solution
{
public:int findLength(vectorint nums1, vectorint nums2) {int dp[1005][1005]{0},n,m,ans-1;nnums1.size();mnums2.size();if(n1)return 0; for(int i1;in;i){for(int j1;jm;j){if(nums1[i-1]nums2[j-1]){dp[i][j]dp[i-1][j-1]1;}ansmax(ans,dp[i][j]);}}return ans;}
};最长公共子序列题目描述给定两个字符串 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 仅由小写英文字符组成。思路第一步我们确定dp[i][j]的含义长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共⼦序列。第二步找状态转移方程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]);第三步初始化同最大子数组一样全部初始化为0code:class Solution
{
public:int longestCommonSubsequence(string text1, string text2) {int dp[1005][1005]{0};int ntext1.size();int mtext2.size();for(int i1;in;i){for(int j1;jm;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];}
};
