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

研习代码 day47 | 动态规划——子序列问题3

一、判断子序列

        1.1 题目

        给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

        字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace""abcde"的一个子序列,而"aec"不是)。

进阶:

如果有大量输入的 S,称作 S1, S2, ... , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?

示例 1:

输入:s = "abc", t = "ahbgdc"
输出:true

示例 2:

输入:s = "axc", t = "ahbgdc"
输出:false

提示:

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • 两个字符串都只由小写字符组成。

        1.2 题目链接

        392.判断子序列

        1.3 解题思路和过程想法

        (1)解题思路

        双指针遍历:用两个指针分别遍历两个字符串,若是两指针所指相同,则两指针同时往后;否则,将指向“母字符串”的指针向后移动;最后判断指向“子字符串”的指针是否到达其串后侧位置

        动态规划:用两层循环结构对比两字符串的元素,外层遍历“子串”,内层遍历“母串”。若是两指针所指的前一元素相同——s[i-1] == t[j-1],则更新“以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度dp[i][j] ——dp[i][j] = dp[i-1][j-1]+1;若是二者不相等,则dp[i][j]等于前值,不做更新——dp[i][j] = dp[i][j-1];最后判断dp[len(s)][len(t)]==lens(s)即可。

        (2)过程想法

        一题多解才能融会贯通所学的知识

        1.4 代码

        1.4.1 双指针遍历
class Solution:def isSubsequence(self, s: str, t: str) -> bool:# 利用双指针分别指向两个字符串point_s , point_t = 0, 0# 遍历字符串 t while point_s < len(s) and point_t < len(t):# 若匹配,则两指针都向后移一位if  s[point_s] == t[point_t]:point_s += 1# 否则,只有指针 t 向后移point_t += 1# 若指针 s  到达最后,则表明匹配成功return point_s == len(s)
        1.4.2 动态规划
class Solution:def isSubsequence(self, s: str, t: str) -> bool:m,n = len(s),len(t)dp = [[0] * (n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = dp[i][j-1]if dp[m][n] == m:return Trueelse:return False

二、不同的子序列

        1.1 题目

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

示例 1:

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

示例 2:

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

提示:

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

        1.2 题目链接

        115.不同的子序列

        1.3 解题思路和过程想法

        (1)解题思路

        当前的匹配情况会受到之前元素的情况所影响,且影响的方式是类似的,考虑采用动态规划的策略。数组:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]

        递推关系:若二者元素相匹配,当前情况取决于 用或不用 当前的元素,
                                  dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
                         若二者元素不匹配,当前情况的结果与不用当前元素的情况相同
                                 dp[i][j] = dp[i-1][j]

图片来源:代码随想录,红色文字是自己加的


        初始化:由上述递推关系可知当前位置的填写是基于左上方和正上方的元素,所以需要提前对首行首列进行初始赋值
                        # 首行:没有母串,直接赋值 0
                                dp[0][j] = 0
                        # 首列:没有子串,即空子串,赋值1
                                dp[i][0] = 1

        (2)过程想法

        递推关系的式子着实是没想到,,,

        1.4 代码

class Solution:def numDistinct(self, s: str, t: str) -> int:long,short = len(s),len(t)# 以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]# 以母串位置为行坐标,以子串位置为列坐标dp = [[0]*(short+1) for _ in range(long+1)]# 递推关系:若二者元素相匹配,当前情况取决于 用或不用 当前的元素# 若匹配,则dp[i][j] = dp[i-1][j-1] + dp[i-1][j]# 初始化:由上述递推关系可知当前位置的填写是基于左上方和正上方的元素,所以需要提前对首行首列进行初始赋值for j in range(short+1):    # 首行:没有母串,直接赋值 0dp[0][j] = 0for i in range(long+1):     # 首列:没有子串,即空子串,赋值1dp[i][0] = 1for i in range(1,long+1):for j in range(1,short+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 dp[long][short]

相关文章:

研习代码 day47 | 动态规划——子序列问题3

一、判断子序列 1.1 题目 给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不删除&#xff09;字符而不改变剩余字符相对位置形成的新字符串。&#xff08;例如&#xff0c;"ace"是"abcde&…...

L1-017:到底有多二

题目描述 一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比值。如果这个数是负数&#xff0c;则程度增加0.5倍&#xff1b;如果还是个偶数&#xff0c;则再增加1倍。例如数字-13142223336是个11位数&#xff0c;其中有3个2&#xff0c;并且是负数&#xff0c;也是…...

Python多线程使用(二)

使用多个线程的时候容易遇到一个场景&#xff1a;多个线程处理一份数据 使用多线程的时候同时处理一份数据&#xff0c;在threading中提供了一个方法&#xff1a;线程锁 Demo&#xff1a;下订单 现在有多笔订单下单&#xff0c;库存减少 from threading import Thread from t…...

记录一次docker搭建tomcat容器的网页不能访问的问题

tomcat Tomcat是Apache软件基金会的Jakarta项目中的一个重要子项目&#xff0c;是一个Web服务器&#xff0c;也是Java应用服务器&#xff0c;是开源免费的软件。它是一个兼容Java Servlet和JavaServer Pages&#xff08;JSP&#xff09;的Web服务器&#xff0c;可以作为独立的W…...

GPT3年终总结

User You 程序员年度绩效总结 ChatGPT ChatGPT 程序员年度绩效总结通常包括以下几个方面&#xff1a; 目标达成情况&#xff1a; 回顾年初设定的目标&#xff0c;评估在项目完成、技能提升等方面的达成情况。 工作贡献&#xff1a; 强调在项目中的个人贡献&#xff0c;包括…...

Kafka生产者发送消息的流程

Kafka 生产者发送消息的流程涉及多个步骤&#xff0c;从消息的创建到成功存储在 Kafka 集群中。以下是 Kafka 生产者发送消息的主要步骤&#xff1a; 1. 创建消息 生产者首先创建一个消息&#xff0c;消息通常包含一个键&#xff08;可选&#xff09;和一个值&#xff0c;以及…...

基于SSM的数学竞赛网站设计与实现

末尾获取源码 开发语言&#xff1a;Java Java开发工具&#xff1a;JDK1.8 后端框架&#xff1a;SSM 前端&#xff1a;Vue 数据库&#xff1a;MySQL5.7和Navicat管理工具结合 服务器&#xff1a;Tomcat8.5 开发软件&#xff1a;IDEA / Eclipse 是否Maven项目&#xff1a;是 目录…...

01-使用Git操作本地库,如初始化本地库,提交工作区文件到暂存区和本地库,查看版本信息,版本切换命令等

Git的使用 概述 Git是一个分布式版本控制工具, 通常用来管理项目中的源代码文件(Java类、xml文件、html页面等)进行管理,在软件开发过程中被广泛使用 Git可以记录文件修改的历史记录并形成备份从而实现代码回溯, 版本切换, 多人协作, 远程备份的功能Git具有廉价的本地库,方便…...

排序算法介绍(二)冒泡排序

0. 简介 冒泡排序&#xff08;Bubble Sort&#xff09;是一种简单的排序算法。它重复地遍历要排序的数列&#xff0c;一次比较两个元素&#xff0c;如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换&#xff0c;也就是说该数列已经排…...

搜索引擎高级用法总结: 谷歌、百度、必应

搜索引擎高级用法总结: 谷歌、百度、必应 google search 基本搜索 逻辑与:and逻辑或: or逻辑非: -完整匹配:“关键词”通配符:* ?高级搜索 intext:后台登录 将只返回正文中包含 后台登录 的网页 intitle intitle:后台登录 将只返回标题中包含 后台登录 的网页,intitle…...

com.intellij.openapi.application.ApplicationListener使用

一般监听期通过如下代码生效 <applicationListeners> <!-- <listener class"com.itheima.taunt.MyApplicationListener"--> <!-- topic"com.intellij.openapi.application.ApplicationListener"…...

常见js hook脚本

一.js hook 过无限debugger var _constructor constructor; Function.prototype.constructor function(s) {if (s "debugger") {console.log(s);return null;}return _constructor(s); }//去除无限debugger Function.prototype.__constructor_back Function.pro…...

Java——SpringLayout弹簧布局

import java.awt.*;import javax.swing.*;public class a {public static void main(String[] args) {new a();}public a() {JFrame JF new JFrame("弹簧布局");// 创建JFrame窗口//设置JPanel的布局管理器为SpringLayoutJPanel JP new JPanel(new SpringLayout())…...

正则表达式及文本三剑客grep sed awk

目录 正则表达式 1.元字符 2.表示次数 3.位置锚定 4.分组或其他 grep sed 语法&#xff1a; 常用选项 脚本格式 例&#xff1a; 查找11点56到12点10的日志 修改文件&#xff0c;找到文件并给其后缀加上er 提取IP地址 提取版本号 提取文件权限 awk 工作原理&…...

python爬虫之创建属于自己的ip代理池

在后续需求数据量比较大的情况下&#xff0c;自建一个ip代理池可以帮助我们获得更多的数据。 下面我来介绍一下整个过程 1.找到目标代理网站 https://www.dailiservers.com/go/webshare https://proxyscrape.com/ https://spys.one/ https://free-proxy-list.net/ http://fr…...

又添三位“信伙伴”,亚信安慧AntDB数据库与南京一鸣、广东鸿数、北京数见完成兼容互认

近日&#xff0c;亚信安慧AntDB数据库与南京一鸣科技有限公司&#xff08;简称&#xff1a;南京一鸣&#xff09;学生工作管理与服务平台软件、广东鸿数科技有限公司&#xff08;简称&#xff1a;广东鸿数&#xff09;隐私数据保护系统V5.0、北京数见科技有限公司&#xff08;简…...

Linux --- 进程控制

目录 1. 进程创建 1.1. 内核数据结构的处理 1.2. 代码的处理 1.3. 数据的处理&#xff1a; 方案一&#xff1a;fork创建子进程的时候&#xff0c;直接对数据进行拷贝处理&#xff0c;让父子进程各自私有一份 方案二&#xff1a;写实拷贝(copy on write) 1.4. fork常规用…...

SVG-椭圆弧-参数转换-计算公式-标准解读

文章目录 1.简介2.基本参数2.1.椭圆的表达2.2.参数变换2.3.注意事项 3.参考资料4.总结 1.简介 为了与其他路径段表示法保持一致&#xff0c; SVG 路径中的圆弧是根据曲线上的起点和终点定义的。椭圆弧的这种端点参数化。优点是它允许与其它路径一致的语法&#xff0c;其中所有…...

利用 LD_PRELOAD劫持动态链接库,绕过 disable_function

目录 LD_PRELOAD 简介 程序的链接 动态链接库的搜索路径搜索的先后顺序&#xff1a; 利用LD_PRELOAD 简单的劫持 执行id命令 反弹shell 引申至 PHP 绕过disable_function 方法1&#xff1a;使用蚁剑的扩展工具绕过disable_function 方法2&#xff1a;利用 mail 函数…...

网件R8500 trojan

一 将路由器刷机成改版梅林 路由器首页的Firmware:380.70_0-X7.9.1是梅林改版 380.xx 梅林原版固件 380.xx_x 梅林改版固件 必须是改版梅林才支持trojan&#xff0c;所以要确保是梅林改版固件 点击上传文件&#xff0c;选择下载好的改版固件&#xff0c;固件地址下载传送门…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

深度学习习题2

1.如果增加神经网络的宽度&#xff0c;精确度会增加到一个特定阈值后&#xff0c;便开始降低。造成这一现象的可能原因是什么&#xff1f; A、即使增加卷积核的数量&#xff0c;只有少部分的核会被用作预测 B、当卷积核数量增加时&#xff0c;神经网络的预测能力会降低 C、当卷…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...