当前位置: 首页> 娱乐> 八卦 > 浏览器网站大全_电子商务专业就业前景如何_国内十大4a广告公司_百度竞价点击神器下载安装

浏览器网站大全_电子商务专业就业前景如何_国内十大4a广告公司_百度竞价点击神器下载安装

时间:2025/7/11 8:41:29来源:https://blog.csdn.net/2301_80630236/article/details/144129547 浏览次数:0次
浏览器网站大全_电子商务专业就业前景如何_国内十大4a广告公司_百度竞价点击神器下载安装

115.不同的子序列

给你两个字符串 st ,统计并返回在 s子序列t 出现的个数,结果需要对 10^9 + 7 取模。

示例 1:

输入:s = "rabbbit", t = "rabbit"
输出:3
解释:
如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
rabbbit
rabbbit
rabbbit

示例 2:

输入:s = "babgbag", t = "bag"
输出:5
解释:
如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 
babgbag
babgbag
babgbag
babgbag
babgbag

提示:

  • 1 <= s.length, t.length <= 1000
  • st 由英文字母组成

思路:

这道题的确有点难,我们首先设置dp[i][j]s中前i个元素与t前j个元素相匹配的个数,然后我们还要对j=0i=0的情况进行判断,如果t为空指针那么s可以找到一个与其相匹配的,那么个数就是1,如果s为空,那么个数就为0,最后进行遍历,当满足s[i-1] = t[i-1]时那么dp[i][j]就为前一个个数加上如果前一个数没匹配上的个数,如果不满足就只是没匹配上的个数,最后返回dp[a1][a2]的值就行了。

解答:

int numDistinct(char* s, char* t) {int a1 = strlen(s);int a2 = strlen(t);unsigned long long** dp = malloc((a1+1)*sizeof(unsigned long long*));for(int i = 0;i <= a1;i++){dp[i] = malloc((a2+1)*sizeof(unsigned long));}for(int i = 0;i <= a1;i++){dp[i][0] = 1;}for(int i = 1;i <= a2;i++){dp[0][i] = 0;}for(int i = 1;i <= a1;i++){for(int j = 1;j <= a2;j++){if(s[i-1] == t[j-1]){dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}else{dp[i][j] = dp[i-1][j];}}}return dp[a1][a2];
}

583.两个字符串的删除操作

给定两个单词 word1word2 ,返回使得 word1word2 相同所需的最小步数

每步 可以删除任意一个字符串中的一个字符。

示例 1:

输入: word1 = "sea", word2 = "eat"
输出: 2
解释: 第一步将 "sea" 变为 "ea" ,第二步将 "eat "变为 "ea"

示例 2:

输入:word1 = "leetcode", word2 = "etco"
输出:4

提示:

  • 1 <= word1.length, word2.length <= 500
  • word1word2 只包含小写英文字母

思路:

这道题跟上面差不多,都是对两个字符串进行操作,这道题中的dp[i][j]的含义指的是在第i个元素和第j个元素时需要删除操作需要几步,同样也分为相等和不等两种情况,但是这道题的初始化要注意,当i=0j=0这两种情况下,相当于有一个空字符串,所以我们需要初始化它们,最后返回dp[a1][a2]就可以得到答案了。

解答:

int minDistance(char* word1, char* word2) {int a1 = strlen(word1);int a2 = strlen(word2);int** dp = calloc(a1+1,sizeof(int*));for(int i = 0;i <= a1;i++){dp[i] = calloc(a2+1,sizeof(int));}for(int i = 0;i <= a1;i++){dp[i][0] = i;}for(int j = 0;j <= a2;j++){dp[0][j] = j;}for(int i = 1;i <= a1;i++){for(int j = 1;j <= a2;j++){if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = fmin(fmin(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);}}}return dp[a1][a2];
}

72.编辑距离

给你两个单词 word1word2请返回将 word1 转换成 word2 所使用的最少操作数

你可以对一个单词进行如下三种操作:

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

示例 1:

输入:word1 = "horse", word2 = "ros"
输出:3
解释:
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2:

输入:word1 = "intention", word2 = "execution"
输出:5
解释:
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示:

  • 0 <= word1.length, word2.length <= 500
  • word1word2 由小写英文字母组成

思路:

我们使用动态规划定义dp[i][j]表示将word1[0...i-1]转化为word2[0...j-1]的最小操作数。初始化时,dp[i][0] = i表示删除操作,dp[0][j] = j表示插入操作。对于每个dp[i][j],如果word1[i-1]word2[j-1]相同,dp[i][j] = dp[i-1][j-1],否则dp[i][j] = fmin(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。最终dp[a1][a2]就是答案,表示将整个word1转化为word2所需的最小操作次数。

解答:

int minDistance(char* word1, char* word2) {int a1 = strlen(word1);int a2 = strlen(word2);int** dp = calloc(a1+1,sizeof(int*));for(int i = 0;i <= a1;i++){dp[i] = calloc(a2+1,sizeof(int));}for(int i = 0;i <= a1;i++){dp[i][0] = i;}for(int j = 0;j <= a2;j++){dp[0][j] = j;}for(int i = 1;i <= a1;i++){for(int j = 1;j <= a2;j++){if(word1[i-1] == word2[j-1]){dp[i][j] = dp[i-1][j-1];}else{dp[i][j] = fmin(dp[i-1][j-1],fmin(dp[i-1][j],dp[i][j-1]))+1;}}}return dp[a1][a2];
}

反思

今天的难度还算适中,整体并不难,但是有些题目你不看解析想不到。

关键字:浏览器网站大全_电子商务专业就业前景如何_国内十大4a广告公司_百度竞价点击神器下载安装

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: