代码随想录27期|Python|Day51|​动态规划|​115.不同的子序列|​583. 两个字符串的删除操作​|

 115. 不同的子序列

本题是在原来匹配子序列的基础上增加了统计所匹配的子序列个数,也就是dp数组的定义和更新公式和原来的有所区别。

1、dp数组的定义

dp[i][j]表示以i-1和j-1为末尾的字符串中,给定字符串s包含目标字符串t的个数。注意这里不是长度。

2、dp数组的更新

(1)当前字符相等,分两种情况:

1.1、不包含当前t[j-1]和s[i-1]字符时,所能够存在的数量dp[i-1][j-1];

1.2、包含当前t[i-1]字符时,但是不包含s[i-1]字符的时候,所能达到的数量(也就是给定字符串还没有走到i-1位置,但是已经包含j-1位置的t的个数)。

dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

(2)当前字符不相等的时候,只能保留1.2描述的内容。

dp[i]][j] = dp[i-1][j];

3、dp数组初始化

分开行和列来看,dp[i][0]表示目标串是空字符串,也就是给定字符串删除全部元素即可,所以全是1;dp[0][j]表示给定字符串是空字符的时候,这时候目标字符串找不到匹配的,所以全是0.

注意,这里需要考虑0,0的情况,也就是空字符串匹配空字符串,结果是1,所以dp[0][0] = 1。

4、确定遍历顺序

本题遍历顺序是按照子串匹配的顺序遍历。外层for循环走给定字符串s(较长的),内层for循环走目标字符串t(较短的)。

class Solution(object):def numDistinct(self, s, t):""":type s: str:type t: str:rtype: int"""dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]for j in range(len(t) + 1):dp[0][j] = 0for i in range(len(s) + 1):dp[i][0] = 1for 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]else:dp[i][j] = dp[i-1][j]# return int(dp[-1][-1] % (1e10+7))return dp[-1][-1]

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

解法一:所需的步数也就是两个字符串分别达到“最大公共子串”所需要的步数。

1、先求出“不连续”包含的最大子串的长度;

2、返回两个字符串的长度和-2*最大子串长度。

OMG活学活用!

class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""len_1 = len(word1)len_2 = len(word2)dp = [[0] * (len_2+ 1) for _ in range(len_1 + 1)]for i in range(1, len_1+1):for j in range(1, len_2+1):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 len_1 + len_2 - dp[-1][-1] * 2  # 最后返回的值就是两个字符串分别达到“最大公共子串”需要删除的字符个数

解法二:直接用dp指示当前的位置处匹配所需要的最少的步数。

1、dp数组的定义

dp[i][j]表示i-1和j-1位值处的word1和word2,能够匹配到最长字符串所需要删除的字符个数;

2、dp更新

(1)当前字符相等,则保持不变:dp[i][j] = dp[i-1][j-1];

(2)当前字符不相等,则由之前的dp进行推算。这里依然是取两个值,一个是hold word1当前字符,删除word2中的,一个是hold word2中的字符,删除word1的。取最小值然后+1即可。

dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + 1;

3、初始化

初始化比较刁钻。

需要反向来思考:对于其中一个是空字符串,index = 0,那么此时若需要匹配,则需要另一个字符串在相应的位置删除全部的元素。所以需要两个for来初始化i,j = 0的行列。

        for i in range(len_1+1):dp[i][0] = ifor j in range(len_2+1):dp[0][j] = j

4、确定遍历顺序

本质还是字符串匹配的遍历,两层for从小到大遍历。 

class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""len_1 = len(word1)len_2 = len(word2)# 解法二dp = [[0] * (len_2 + 1) for _ in range(len_1 + 1)]for i in range(len_1+1):dp[i][0] = ifor j in range(len_2+1):dp[0][j] = jfor i in range(1, len_1+1):for j in range(1, len_2+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], dp[i][j-1]) + 1return dp[-1][-1]

本题的解法1更加推荐,因为和之前“不连续”最大公共子串可以直接复用,实现也比较简单,也不需要控制边界情况或者考虑初始化细节。

72. 编辑距离

 本题是前几个编辑距离的扩充版,考虑了“非连续”“增删换”等不同的操作以及操作之间的合并

1、确定dp数组含义

dp[i][j]表示在i-1、j-1位置处,word1和word2能够达到最小修改步骤的值;

2、确定dp数组的更新公式

(1)当前字符相等,那么无需步骤来修改,hold上一个匹配的dp值即可:dp[i][j] = dp[i-1][j-1];

(2)当前字符不匹配,则需要逐一讨论“增、删、换”三种操作的表达式,最后取最小值+1即可:

2.1删

删除和之前的表达式完全一致,分别hold住两个word当前位置的index,另一个往前回退一个,也就是dp[i-1][j] + 1和dp[i][j] + 1。

2.2增

增加和删除其实是相同的操作,因为在此字符串位置增加,就相当于在另一个字符的位置删掉一个,所以可以和上面的表达式合并。比如“abc”和“ab”在c位置处,可以选择增加一个c在word2,也可以选择在word1删除一个c,两个操作实际上都是在hold住一个,另一个回退的基础上进行更新的。

2.3换

换操作相当于在现在位置上的字符更新为相同值。不妨反过来想:如果当前字符匹配,则hold住两个字符串上一个index所对应的dp的值,那么现在换了一个元素相当于在相等前,增加了一个步骤,所以dp[i][j] = 1+dp[i-1][j-1]。

3、确定初始化

本题和上一题的初始化相同,因为都涉及对于0行、0列元素的调用,具体的初始化是两个for分别遍历整个0行和0列,dp等于对应的index值。

4、确定遍历顺序

由于dp是分别由前一行、前一列推到而来,所以遍历顺序是从小到大,内外两个for循环。

class Solution(object):def minDistance(self, word1, word2):""":type word1: str:type word2: str:rtype: int"""len_1 = len(word1)len_2 = len(word2)dp = [[0] * (len_2 + 1) for _ in range(len_1 + 1)]for i in range(len_1+1): dp[i][0] = ifor j in range(len_2+1): dp[0][j] = jfor i in range(1, len_1 + 1):for j in range(1, len_2 + 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], dp[i][j-1], dp[i-1][j-1]) + 1  # 合并后的表达式return dp[-1][-1]

Day51完结!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/420575.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

CTF入门教程(非常详细)从零基础入门到竞赛,看这一篇就够了!

一、CTF简介 CTF(Capture The Flag)中文一般译作夺旗赛,在网络安全领域中指的是网络安全技术人员之间进行技术竞技的一种比赛形式。CTF起源于1996年DEFCON全球黑客大会,以代替之前黑客们通过互相发起真实攻击进行技术比拼的方式。…

多个微信是怎么进行管理的?

随着微信逐渐成为企业商务沟通的重要平台,对于业务咨询量较大的行业(例如教育培训、旅游、美容以及医疗等)而言,在利用微信进行营销活动和客户服务的过程中,往往会遭遇多微信管理的困境。 在此情形下,选用工…

企业出海网络方案,助力TikTok直播

在全球贸易蓬勃发展的今天,出海电商已成为引领增长的新动力,政府对此的支持力度也在持续加大,为企业带来了前所未有的出海机遇。越来越多的企业开始进军TikTok直播等业务,而在这一过程中,一个适应全球化运营的出海网络…

RS485网关在工业自动化控制系统中的应用-天拓四方

随着工业自动化控制系统的不断发展,各种现场总线技术在工业领域得到了广泛应用。其中,RS485作为一种半双工的通信方式,因其通信距离远、抗干扰能力强、传输速率高等优点,在工业现场得到了广泛应用。而RS485网关作为连接不同网络之…

“人大金仓”正式更名为“电科金仓”; TDSQL-C支持回收站/并行DDL等功能; BigQuery支持直接查询AlloyDB

重要更新 1. “人大金仓”正式更名为“电科金仓”,完整名称“中电科金仓(北京)科技股份有限公司”,突出金仓是中国电子科技集团有限公司在基础软件领域产品( [1] ) 。据悉人大金仓在上半年营收入为9056万元,净利润约21…

并发编程:Future类

一、Future 类有什么用? Future 类是异步思想的典型运用,主要用在一些需要执行耗时任务的场景,避免程序一直原地等待耗时任务执行完成,执行效率太低。具体来说是这样的:当我们执行某一耗时的任务时,可以将…

使用Python自动抓取亚马逊网站商品信息

全量数据抓取不现实,但可以自动化、小批量采集亚马逊数据,现在可用的工具也非常多,包括Python以及一些专门的爬虫软件,我用过几个比较好入手的,像web scraper、八爪鱼、亮数据。 比如亮数据爬虫,它提供数据…

Dubbo精要

1、为什么需要 Dubbo? 分布式系统中的服务调用和协调问题:在分布式系统中,服务之间的相互依赖会导致复杂的通信和协调问题。Dubbo提供了高效的服务调用和自动注册、发现等功能,使得构建分布式应用程序更加容易。服务治理和服务调…

Ubuntu下使用Cron定时任务

Ubuntu下使用Cron定时任务 文章目录 Ubuntu下使用Cron定时任务概述Cron 工作原理crontab的基本指令使用Cron 定时任务语法用户的crontab 文件系统的crontab 文件cron 任务设置环境变量1. 直接在 crontab 中声明变量2. 将变量声明为命令的一部分3. 从文件加载变量使用环境变量控…

06后夺得都江堰杯2024国际超模大赛四川总决赛冠军

9月8日众人期盼已久的都江堰杯2024国际超模大赛四川总决赛在三遗之城都江堰落下帷幕。国际超模大赛已经举办第12个年头,每年为时尚界、模特界输送无数的优秀时尚模特人才,让世界超模中出现更多的中国面孔。大赛在全球已经布局多个国家及地区,…

MySQL高可用配置及故障切换

目录 引言 一、MHA简介 1.1 什么是MHA(MasterHigh Availability) 1.2 MHA的组成 1.3 MHA的特点 1.4 MHA工作原理 二、搭建MySQL MHA 2.1 实验思路 2.2 实验环境 1、关闭防火墙和安全增强系统 2、修改三台服务器节点的主机名 2.3 实验搭建 1、…

【springsecurity】使用PasswordEncoder加密用户密码

目录 1. 导入依赖2. 配置 PasswordEncoder3. 使用 PasswordEncoder 加密用户密码4. 使用 PasswordEncoder 验证用户密码 1. 导入依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-security</artifac…

利用Tiktok广告资料库提升广告效果

Tiktok广告资料库是一个展示Tiktok广告素材的平台&#xff0c;包含了上千万的热门广告案例&#xff0c;利用Tiktok广告资料库&#xff0c;你可以查看竞争对手广告情况&#xff0c;分析广告市场动态&#xff0c;获取最受欢迎的广告形式&#xff0c;激发创作素材的灵感&#xff0…

异常重试工具

目录 RetryUtils方法main方法测试拓展-函数接口 RetryUtils方法 该Java函数retryOnException用于在指定重试次数内执行某个操作&#xff0c;并在遇到异常时重试。功能如下&#xff1a; 对传入的操作&#xff08;retryCallable&#xff09;进行尝试执行。如果执行成功且结果符…

代码管理工具——git及阿里云云效的使用(包含git的使用及云效自动化部署)

1、做项目开发时都会用到代码管理工具,像是我之前使用过gitHub,Visual Studio等一些代码管理工具&#xff0c;这里介绍的是阿里云云效的使用。 2、首先登录阿里云云效&#xff0c;登录进去之后会看到公司给你开放的一个仓库。 3、进入仓库&#xff0c;点击克隆/下载&#xff0…

docker部署rabbitMQ 单机版

获取rabbit镜像&#xff1a;我们选择带有“mangement”的版本&#xff08;包含web管理页面&#xff09;&#xff1b; docker pull rabbitmq:management 创建并运行容器&#xff1a; docker run -d --name rabbitmq -p 5677:5672 -p 15677:15672 rabbitmq:management --name:…

[数据集][目标检测]汽油检泄漏检测数据集VOC+YOLO格式237张2类别

数据集格式&#xff1a;Pascal VOC格式YOLO格式(不包含分割路径的txt文件&#xff0c;仅仅包含jpg图片以及对应的VOC格式xml文件和yolo格式txt文件) 图片数量(jpg文件个数)&#xff1a;237 标注数量(xml文件个数)&#xff1a;237 标注数量(txt文件个数)&#xff1a;237 标注类别…

TMGM:黄金价格保持在2,500美元左右稳定

美国国库券收益率修剪了早期的涨幅&#xff0c;对美元构成压力。市场参与者正在期待美国消费者价格指数在星期三发布。XAU/USD努力扩大2,500美元以上的涨幅&#xff0c;原因是多头暂停了。 现货黄金交易就在2,500美元的标记附近&#xff0c;星期一没什么变动&#xff0c;并局限…

完整指南:CNStream流处理多路并发框架适配到NVIDIA Jetson Orin (三) 代码编译、各种问题解决、代码修改

目录 1 infer_server编译 1.1 infer_server/CMakeLists.txt修改 1.2 FindLibCompute.cmake编写 1.2 findLibCVCuda.cmake编写 1.3 ./3rdparty/config_lib_aarch64.sh修改 1.4 解决各种编译错误 1.4.1 /usr/include/c/11/bits/algorithmfwd.h:259:5: error: ‘pair’ doe…

OpenCV-轮廓检测

文章目录 一、简介1. 意义2.具体步骤 二、代码实现三、总结 一、简介 1. 意义 在OpenCV中&#xff0c;轮廓检测是图像处理中一个非常重要的环节&#xff0c;它允许我们识别图像中的形状。这个过程通常涉及几个步骤&#xff1a;读取图像、转换为灰度图、应用阈值处理&#xff…