当前位置: 首页 > 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;固件地址下载传送门…...

什么是库存周转?如何用进销存系统提高库存周转率?

你可能听说过这样一句话&#xff1a; “利润不是赚出来的&#xff0c;是管出来的。” 尤其是在制造业、批发零售、电商这类“货堆成山”的行业&#xff0c;很多企业看着销售不错&#xff0c;账上却没钱、利润也不见了&#xff0c;一翻库存才发现&#xff1a; 一堆卖不动的旧货…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

LangFlow技术架构分析

&#x1f527; LangFlow 的可视化技术栈 前端节点编辑器 底层框架&#xff1a;基于 &#xff08;一个现代化的 React 节点绘图库&#xff09; 功能&#xff1a; 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理

在城市的某个角落&#xff0c;一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延&#xff0c;滚滚浓烟弥漫开来&#xff0c;周围群众的生命财产安全受到严重威胁。就在这千钧一发之际&#xff0c;消防救援队伍迅速行动&#xff0c;而豪越科技消防一体化安全管控平台构建的消防“…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

Python爬虫实战:研究Restkit库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...

Java多线程实现之Runnable接口深度解析

Java多线程实现之Runnable接口深度解析 一、Runnable接口概述1.1 接口定义1.2 与Thread类的关系1.3 使用Runnable接口的优势 二、Runnable接口的基本实现方式2.1 传统方式实现Runnable接口2.2 使用匿名内部类实现Runnable接口2.3 使用Lambda表达式实现Runnable接口 三、Runnabl…...