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

福利站wordpressseo教程下载

福利站wordpress,seo教程下载,上海网络推广优化公司,php 修改 wordpress动态规划day45:编辑距离|115. 不同的子序列、583. 两个字符串的删除操作、72. 编辑距离(动规终极好题) 115. 不同的子序列583. 两个字符串的删除操作72. 编辑距离(动规终极好题) 115. 不同的子序列 给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中…

动态规划day45:编辑距离|115. 不同的子序列、583. 两个字符串的删除操作、72. 编辑距离(动规终极好题)

  • 115. 不同的子序列
  • 583. 两个字符串的删除操作
  • 72. 编辑距离(动规终极好题)

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 由英文字母组成
class Solution {
public:int numDistinct(string s, string t) {vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t>(t.size()+1));for(int i=0;i<=s.size();i++)dp[i][0]=1;for(int i=1;i<=t.size();i++)dp[0][i]=0;for(int i=1;i<=s.size();i++)for(int j=1;j<=t.size();j++){if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+dp[i-1][j];elsedp[i][j]=dp[i-1][j];}return dp[s.size()][t.size()];}
};

本题关键:递推公式的推导

首先,dp [i] [j]的含义是以 s[i-1] 为结尾的序列中,有多少个以 t[j-1] 为结尾的序列。

据此,我们分两种情况来讨论:

  • 第一种,当s[i-1]与t[j-1]不相等那么s有没有s[i-1],效果其实都是一样的,即dp[i] [j]=dp[i-1] [j]。

  • 第二种,当s[i-1]与t[j-1]相等时,此时s[i-1]显然时有用的。当我们使用s[i-1]时,由于末尾元素相等,我们稍加思索,可以得出:dp[i] [j]=dp[i-1] [j-1];当我们不使用s[i-1]时,则和第一种一样,d[i] [j]=dp[i-1] [j]。那么它们是求和还是求最大值呢?显然是求和了,即:

			if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+dp[i-1][j];elsedp[i][j]=dp[i-1][j];

另外,uint64_t等效于unsigned long 且uint64_t 表示数据范围则是0 ~2^64-1,int16_t
表示数据范围为-264~264-1。

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 只包含小写英文字母
class Solution {
public:int minDistance(string word1, string word2) {int len1=word1.size();int len2=word2.size();vector<vector<int>> dp(len1+1,vector<int>(len2+1));for(int i=0;i<=len1;i++)dp[i][0]=i;for(int j=1;j<=len2;j++)dp[0][j]=j;for(int i=1;i<=len1;i++)for(int j=1;j<=len2;j++){if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1);}return dp[len1][len2];}
};

在上一题的基础上,这道题还是很容易想出来的。递推公式的逻辑是当末尾元素相等时,就等效于把末尾元素去掉,即dp[i] [j]=dp[i-1] [j-1];当末尾元素不相等时,那么末尾元素必要删一个,分两种情况,然后取最小值即可。

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 由小写英文字母组成
class Solution {
public:int minDistance(string word1, string word2) {int len1=word1.size();int len2=word2.size();vector<vector<int>> dp(len1+1,vector<int>(len2+1));for(int i=0;i<=len1;i++)dp[i][0]=i;for(int j=1;j<=len2;j++)dp[0][j]=j;for(int i=1;i<=len1;i++)for(int j=1;j<=len2;j++){if(word1[i-1]==word2[j-1])dp[i][j]=dp[i-1][j-1];elsedp[i][j]=min(min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);}return dp[len1][len2];}
};

难点还是在递归公式,要分两种情况讨论:

  • 当word1[i-1]==word2[j-1]时此时末尾元素相等,说明这两个元素时不需要操作的,则dp [i] [j]=dp [i-1] [j-1]
  • 当word1[i-1]!=word2[j-1]时,又要分3种情况讨论:
    • :若删 word1,则dp [i] [j]=dp [i-1] [j]+1;若删 word2,则dp [i] [j]=dp [i] [j-1]+1
    • 从问题的本质上讲,增和删时一致的,即 word2 增其实是等效于 word1 删。也就是说,实现增和删效果的代码本质上是一致的,所以不用另写!
    • 替换:两个末尾元素都参与替换了,显然dp [i] [j]=dp [i-1] [j-1]+1
http://www.zhongyajixie.com/news/43770.html

相关文章:

  • 网站开发技术包括推广网上国网
  • 个人网站名字可以用哪些郑州网站建设公司排名
  • 网站备案号注销查询系统中国今日新闻
  • php 做网站 python2022年最火的关键词
  • seo网站建站外贸网站平台有哪些
  • 找人做淘宝网站深圳市社会组织总会
  • 国外做的好看的网站百度西安分公司地址
  • 网站建设哪个公司好网络营销课程心得体会
  • 做网站推广有用吗河北seo基础教程
  • 西安有哪些做网站的公司上海网站seo策划
  • 黄冈论坛网站有哪些现在推广引流什么平台比较火
  • 口碑好的o2o网站建设什么软件可以发布推广信息
  • 哈尔滨网站建设排行手机百度极速版app下载安装
  • 温州微网站制作电话营销策略的概念
  • 苏州做网站的专业公司哪家好云南网络推广服务
  • 温州做网站找哪家好外链网
  • 做网站设计师工资多少淘宝推广费用多少钱一天
  • 多语言网站建设应注意哪些事项互动营销公司
  • 上海公司做网站的价格网络营销岗位
  • 个人域名备案网站名称淘宝流量网站
  • 平面设计主要学哪些软件优化设计电子课本下载
  • wordpress页面多打开空白页seo网络营销公司
  • 哪家网站建设做的好软件开发培训
  • 买东西的网站都有哪些推广引流最快的方法
  • c2c网站建设原创文章代写平台
  • 北京网站建设 网络安全怎么宣传自己的店铺
  • 网站开发需求方案模板网络营销的产品策略
  • 宝鸡网站建设网站2020做seo还有出路吗
  • 青岛网站建设 百度网络营销论文毕业论文
  • 网站更多分享怎么做网站推广宣传语