局域网电脑做网站服务器,wordpress 5.0主题,html5 网站开发定制,dede被挂网站网站木马115. 不同的子序列
困难
给你两个字符串 s 和 t #xff0c;统计并返回在 s 的 子序列 中 t 出现的个数#xff0c;结果需要对 10^9 7 取模。 算法思想#xff1a;利用动态规划#xff0c;分s[i - 1] 与 t[j - 1]相等#xff0c;s[i - 1] 与 t[j - 1] 不相等两种情况具…115. 不同的子序列
困难
给你两个字符串 s 和 t 统计并返回在 s 的 子序列 中 t 出现的个数结果需要对 10^9 7 取模。 算法思想利用动态规划分s[i - 1] 与 t[j - 1]相等s[i - 1] 与 t[j - 1] 不相等两种情况具体讨论如何匹配。 1、dp数组及其下标含义dp[i][j] 以i-1为结尾的字符串s中包含以j-1为结尾的字符串t 的个数。 2、递推公式 s[i - 1] 与 t[j - 1]相等: dp[i][j] dp[i - 1][j - 1] dp[i - 1][j]s[i - 1] 与 t[j - 1] 不相等: dp[i][j] dp[i - 1][j] 如果s[i-1] t[j-1]dp[i][j]可以有两部分组成。 一部分是用s[i - 1]来匹配那么个数为dp[i - 1][j - 1]。 一部分是不用s[i - 1]来匹配个数为dp[i - 1][j]。 例如 sbagg 和 tbag s[3] 和 t[2]是相同的但是字符串s也可以不用s[3]来匹配. 如果s[i-1] ! t[i-1]那么不能用s[i-1]来匹配模拟在s中删除这个元素dp[i][j] dp[i-1][j] 3、初始化 dp[0][0] 1, dp[i][0] 1s匹配空字符串删除到为空这一种方法,dp[0][j] 0 4、遍历 从前到后从上到下 class Solution:def numDistinct(self, s: str, t: str) - int:dp [[0] * (len(t)1) for _ in range(len(s)1)]for i in range(len(s)):dp[i][0] 1for j in range(1, len(t)):dp[0][j] 0for i in range(1, len(s)1):for j in range(1, len(t)1):if s[i-1] t[j-1]:dp[i][j] dp[i-1][j-1] dp[i-1][j] #用s[i - 1]来匹配和不用else:dp[i][j] dp[i-1][j]# 不能用s[i-1]来匹配模拟在s中删除这个元素return dp[-1][-1]
583. 两个字符串的删除操作
中等
给定两个单词 word1 和 word2 返回使得 word1 和 word2 相同所需的最小步数。
每步 可以删除任意一个字符串中的一个字符。 直接删 算法思想利用动态规划如果word1[i-1] word2[j-1]相等那么不需要删除操作如果不相等那么可以删word1、word2或者都删取最小值。 1、dp数组及其下标含义dp[i][j] 以i-1为结尾的字符串word1和以j-1为结尾的字符串word2 最少需要删除几次可以相等。 2、递推公式 s[i - 1] 与 t[j - 1]相等: dp[i][j] dp[i - 1][j - 1]s[i - 1] 与 t[j - 1] 不相等: dp[i][j] min(dp[i-1][j]1, dp[i][j-1]1,dp[i-1][j-1]2) 如果s[i-1] t[j-1]不需要删。dp[i][j] dp[i - 1][j - 1] 如果s[i-1] ! t[i-1]有三种删除方式删word1/word2/都删取最小值 3、初始化 dp[0][0] 1, dp[i][0] idp[0][j] j 4、遍历 从前到后从上到下 class Solution:def minDistance(self, word1: str, word2: str) - int:dp [[0] * (len(word2)1) for _ in range(len(word1)1)]for i in range(len(word1)1):dp[i][0] ifor j in range(1, len(word2)1):dp[0][j] jfor i in range(1, len(word1)1):for j in range(1, len(word2)1):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1] # 相等的话不需要删else: # 不相等可以删word1\word2\都删 dp[i][j] min(dp[i-1][j]1, dp[i][j-1]1,dp[i-1][j-1]2)return dp[-1][-1]
求最长公共子序列
class Solution(object):def minDistance(self, word1, word2):m, n len(word1), len(word2)# dp 求解两字符串最长公共子序列dp [[0] * (n1) for _ in range(m1)]for i in range(1, m1):for j in range(1, n1):if word1[i-1] word2[j-1]:dp[i][j] dp[i-1][j-1] 1else:dp[i][j] max(dp[i-1][j], dp[i][j-1])# 删去最长公共子序列以外元素return m n - 2 * dp[-1][-1]
72. 编辑距离
中等
给你两个单词 word1 和 word2 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作
插入一个字符删除一个字符替换一个字符 1、dp数组及其下标含义dp[i][j] 以i-1为结尾的字符串word1和以j-1为结尾的字符串word2 最少需要操作几次可以相等。 2、递推公式 s[i - 1] 与 t[j - 1]相等: dp[i][j] dp[i - 1][j - 1]s[i - 1] 与 t[j - 1] 不相等: dp[i][j] min(dp[i-1][j]1, dp[i][j-1]1,dp[i-1][j-1]1) 如果s[i-1] t[j-1]不需要操作。dp[i][j] dp[i - 1][j - 1] 如果s[i-1] ! t[i-1]可以插入、删除、替换 删除删word1: dp[i][j] dp[i - 1][j] 1删word2: dp[i][j] dp[i][j-1] 1 插入相当于删除 替换只需一次操作dp[i][j] dp[i - 1][j - 1] 1 3、初始化 dp[0][0] 1, dp[i][0] idp[0][j] j 4、遍历 从前到后从上到下 class Solution:def minDistance(self, word1: str, word2: str) - int:dp [[0] * (len(word2)1) for _ in range(len(word1)1)]for i in range(len(word1)1):dp[i][0] ifor j in range(len(word2)1):dp[0][j] jfor i in range(1, len(word1)1):for j in range(1, len(word2)1):if word1[i-1] word2[j-1]:# 相等无需操作dp[i][j] dp[i-1][j-1]else: # 不相等进行删除或替换操作取最小值dp[i][j] min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 1return dp[-1][-1]
