算法训练营 day58 动态规划 判断子序列 不同的子序列
算法训练营 day58 动态规划 判断子序列 不同的子序列
判断子序列
392. 判断子序列 - 力扣(LeetCode)
给定字符串 s 和 t ,判断 s 是否为 t 的子序列。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
进阶:
如果有大量输入的 S,称作 S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
-
确定dp数组(dp table)以及下标的含义
dp[i][j]
表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]
。注意这里是判断s是否为t的子序列。即t的长度是大于等于s的。
-
确定递推公式
在确定递推公式的时候,首先要考虑如下两种操作,整理如下:
-
if (s[i - 1] == t[j - 1])
- t中找到了一个字符在s中也出现了
-
if (s[i - 1] != t[j - 1])
- 相当于t要删除元素,继续匹配
if (s[i - 1] == t[j - 1])
,那么dp[i][j] = dp[i - 1][j - 1] + 1
;,因为找到了一个相同的字符,相同子序列长度自然要在dp[i-1][j-1]
的基础上加1(如果不理解,在回看一下dp[i][j]
的定义)if (s[i - 1] != t[j - 1])
,此时相当于t要删除元素,t如果把当前元素t[j - 1]
删除,那么dp[i][j] 的数值就是 看s[i - 1]与 t[j - 2]
的比较结果了,即:dp[i][j] = dp[i][j - 1]
;
-
dp数组如何初始化
从递推公式可以看出
dp[i][j]
都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1]
,所以dp[0][0]和dp[i][0]
是一定要初始化的。这里大家已经可以发现,在定义
dp[i][j]
含义的时候为什么要表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]
。因为这样的定义在dp二维矩阵中可以留出初始化的区间,如图:
如果要是定义的dp[i][j]
是以下标i为结尾的字符串s和以下标j为结尾的字符串t,初始化就比较麻烦了。
dp[i][0]
表示以下标i-1为结尾的字符串,与空字符串的相同子序列长度,所以为0. dp[0][j]同理
。
- 确定遍历顺序
同理从递推公式可以看出dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1],那么遍历顺序也应该是从上到下,从左到右
如图所示:
- 举例推导dp数组
以示例一为例,输入:s = “abc”, t = “ahbgdc”,dp状态转移图如下:
dp[i][j]
表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度,所以如果dp[s.size()][t.size()]
与 字符串s的长度相同说明:s与t的最长相同子序列就是s,那么s 就是 t 的子序列。
图中dp[s.size()][t.size()] = 3
, 而s.size() 也为3。所以s是t 的子序列,返回true。
class Solution {public boolean isSubsequence(String s, String t) {int[][] dp = new int[s.length()+1][t.length()+1];char[] number1 = s.toCharArray();char[] number2 = t.toCharArray();for (int i = 1; i <= number1.length; i++) {for (int j = 1; j <=number2.length; j++) {if (number1[i-1]==number2[j-1]) dp[i][j] = dp[i-1][j-1]+1;else dp[i][j] = dp[i][j-1];System.out.print(dp[i][j]);}System.out.println();}return dp[number1.length][number2.length]==s.length();}
}
不同的子序列
115. 不同的子序列 - 力扣(LeetCode)
给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,“ACE” 是 “ABCDE” 的一个子序列,而 “AEC” 不是)
题目数据保证答案符合 32 位带符号整数范围。
- 确定dp数组(dp table)以及下标的含义
·dp[i][j]
:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]
。
-
确定递推公式
这一类问题,基本是要分析两种情况
-
s[i - 1] 与 t[j - 1]
相等 -
s[i - 1] 与 t[j - 1]
不相等当
s[i - 1] 与 t[j - 1]
相等时,dp[i][j]
可以有两部分组成。一部分是用s[i - 1]来匹配,那么个数为
dp[i - 1][j - 1]
。即不需要考虑当前s子串和t子串的最后一位字母,所以只需要dp[i-1][j-1]
。一部分是不用
s[i - 1]
来匹配,个数为dp[i - 1][j]
。当
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]
只有一部分组成,不用s[i - 1]
来匹配(就是模拟在s中删除这个元素),即:dp[i - 1][j]
所以递推公式为:
dp[i][j] = dp[i - 1][j];
-
dp数组如何初始化
从递推公式
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
; 和dp[i][j] = dp[i - 1][j]
; 中可以看出dp[i][j]
是从上方和左上方推导而来,如图:,那么dp[i][0]
和dp[0][j]
是一定要初始化的。
每次当初始化的时候,都要回顾一下dp[i][j]
的定义,不要凭感觉初始化。
dp[i][0]
表示什么呢?
dp[i][0]
表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数。
那么dp[i][0]
一定都是1,因为也就是把以i-1为结尾的s,删除所有元素,出现空字符串的个数就是1。
再来看dp[0][j],dp[0][j]
:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数。
那么dp[0][j]
一定都是0,s如论如何也变成不了t。
- 确定遍历顺序
从递推公式dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
; 和 dp[i][j] = dp[i - 1][j]
; 中可以看出dp[i][j]
都是根据左上方和正上方推出来的。
所以遍历的时候一定是从上到下,从左到右,这样保证dp[i][j]可以根据之前计算出来的数值进行计算。
- 举例推导dp数组
以s:“baegg”,t:"bag"为例,推导dp数组状态如下:
如果写出来的代码怎么改都通过不了,不妨把dp数组打印出来,看一看,是不是这样的。
class Solution {public int numDistinct(String s, String t) {char[] number1 = s.toCharArray();char[] number2 = t.toCharArray();int[][] dp = new int[number1.length+1][number2.length+1];for (int i = 0; i <=number1.length; i++) {dp[i][0]=1;}for (int i = 1; i <=number1.length ; i++) {for (int j = 1; j <=number2.length ; j++) {if (number1[i-1]==number2[j-1]) dp[i][j]=dp[i-1][j-1]+dp[i-1][j];else dp[i][j] = dp[i-1][j];}}return dp[number1.length][number2.length];}
}
相关文章:
算法训练营 day58 动态规划 判断子序列 不同的子序列
算法训练营 day58 动态规划 判断子序列 不同的子序列 判断子序列 392. 判断子序列 - 力扣(LeetCode) 给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而…...
优思学院|DFMEA是全球制造业的必修课!
DFMEA(Design Failure Mode and Effects Analysis)是一种分析技术,在产品设计的早期阶段识别和解决潜在的失效问题。它通过分析设计的各个方面,识别潜在的失效模式和影响,并提出相应的改进措施,以减少失效的…...
【Day02数据结构 空间复杂度】
最近太忙了都好久没有更新博客了,太难了,抽空水一篇文章,大佬们多多支持. 上篇:时间复杂度分析 目录 前言 一、空间复杂度概念? 二、实例展示 三、.有复杂度要求的算法题练习 1.题目链接:力扣--消失的数字 2.题目链接:力扣--旋转数组 总结: 1…...
多数据库管理工具哪家强?ChatGPT点评,第一位并不是Navicat
SQL逐渐成为职场必备的编程语言,相信大家都不陌生。SQL是一种结构化查询语言,是用于数据库之间通信的编程语言。每个数据库都有着自己独特的访问规则,但大体上是遵循SQL标准。 因此,辗转于不同的数据库之间,开发者或D…...
UnityShader常用函数(UnityShader内置函数、CG和GLSL内置函数等)
空间变换函数函数名描述float4 UnityWorldToClipPos(float3 pos )把世界坐标空间中某一点pos变换到齐次裁剪空间float4 UnityViewToClipPos(float3 pos )把观察坐标空间中某一点pos变换到齐次裁剪空间float3 UnityObjectToViewPos(float3 pos或float4 pos)模型局部空间坐标系中…...
Springboot自定义注解-1
注解用于修饰其他的注解(纪委:管干部的干部) ① Retention:定义注解的保留策略 Retention(RetentionPolicy.SOURCE) //注解仅存在于源码中,在class字节码文件中不包含 Retention(RetentionPolicy.CLASS) …...
经纬度标定及大地坐标系相关概念(一)
经纬度标定及大地坐标系相关概念(一)一、背景二、经纬度的概念三、大地坐标系四、大地坐标系的分类五、各类坐标系介绍5.1 我国地理坐标系5.1.1 北京54坐标系5.1.2 1980西安坐标系5.1.3 2000国家大地坐标系5.2 世界大地坐标系5.1.1 WGS84坐标系5.3 加密坐…...
synchronized关键字原理
synchronized原理 1、基本特点 基于锁策略,可以知道synchronized具有以下特性: 1.开始时候是乐观锁,如果锁冲突频繁就转换为悲观锁 2.开始是轻量级锁,如果锁持有的时间较长,就转换成重量级锁 3.实现轻量级锁的时候…...
面试被问死怎么办?学会这四招,通过的机率提升30%
软件工程师面试很难,难到什么程度呢?有一句话可以来形容: 面试造飞机,上班拧螺丝 没错,面试的时候各种问你原理、机制,而这些在实际工作中却很难用到。于是乎,很多工程师面试的时候就非常害怕…...
Android TV UI开发常用知识
导入依赖 Google官方为Android TV的UI开发提供了一系列的规范组件,在leanback的依赖库中,这里介绍一些常用的组件,使用前需要导入leanback库。 implementation androidx.leanback:leanback:$version常用的页面 这些Fragment有设计好的样式&…...
Xshell 下载及安装
文章目录下载安装连接服务器Xshell 是一个强大的安全终端模拟软件,它支持SSH1, SSH2, 以及Microsoft Windows 平台的TELNET 协议。Xshell 通过互联网到远程主机的安全连接以及它创新性的设计和特色帮助用户在复杂的网络环境中享受他们的工作。 Xshell可以在Windows界…...
【LeetCode】剑指 Offer(12)
目录 题目:剑指 Offer 30. 包含min函数的栈 - 力扣(Leetcode) 题目的接口: 解题思路: 代码: 过啦!!! 写在最后: 题目:剑指 Offer 30. 包含m…...
vue在history模式下打包部署问题解决
引言 项目使用的模板是element-template,由于业务需要,我将路由的hash模式更改为了history模式,然后在打包部署项目时就出现了问题 个人发现是资源的访问路径有问题,在部署之后发现每次访问的js资源路径前都会自动携带上我路由的…...
Java中常见性能优化策略的总结
文章目录1. 代码优化2. 数据库层面优化SQL调优架构层面的调优连接池调优3. 网络优化4. 缓存缓存分类使用场景选型考虑什么时候更新缓存?如何保障更新的可靠性和实时性?缓存是否会满,缓存满了怎么办?缓存是否允许丢失?丢…...
c++日志库log4cplus使用
项目中需要打印log,方便程序调试和问题定位分析。C实现的log4cplus日志库是一种易于使用的C 日志记录API,可提供线程安全,灵活且任意粒度的日志管理和配置控制。 下面介绍一下在linux中安装log4cplus库过程 下载地址:https://gi…...
什么是接口测试,我们如何实现接口测试?
1. 什么是接口测试 顾名思义,接口测试是对系统或组件之间的接口进行测试,主要是校验数据的交换,传递和控制管理过程,以及相互逻辑依赖关系。其中接口协议分为HTTP,WebService,Dubbo,Thrift,Socket等类型,测试类型又主…...
随机森林在sklearn中的实现
目录 一.集成算法 二.sklearn中的集成算法模块ensemble 三.RandomForestClassifier(随机森林分类器) 四.重要参数 1.基评估器参数 2.随机森林参数 五.重要属性和接口 六.Bagging的另一个必要条件 七.RandomForestRegressor(随机森林回归器) 八.机器学习中调参的基本思…...
[论文总结] 深度学习在农业领域应用论文笔记11
深度学习在农业上的应用笔记11 最近发表的相关论文数量不多,质量普遍也不尽如人意,尤其是《Computers and Electronics in Agriculture》这个期刊。这些论文的方法都很简单,只是强行将深度学习应用于某个问题上,而没有考虑到农业…...
Android 9.0 SystemUI 状态栏屏蔽弹出的悬浮式通知
1.概述 在9.0的系统ROM产品定制化开发中,在systemui的状态栏中,会在有闹钟 wifi连接等特殊弹窗通知的时候,会在接收到系统通知时,弹窗悬浮式弹窗通知,然后过几秒中, 就消失了,所以像这样的悬浮式通知,在有些产品中是不需要的,要求屏蔽掉,这就需要按照悬浮式流程来分析…...
商简智能计划与排程SPS在纺织行业中的应用
企业背景 某织造、染色及后整理一体化工艺的纺织面料企业,主要从事户外功能运动服装、内衣、泳衣、汽车内饰等面料的研发和销售,年产值在20亿左右,是迪卡侬运动面料最优质供应商之一。 纺织行业特点 印染具有典型的流程行业特性,…...
549、RocketMQ详细入门教程系列 -【消息队列之 RocketMQ(三)】 2023.02.28
目录一、Spring 整合 RocketMQ1.1 消息生产者1.2 消息消费者1.3 Spring 配置文件1.4 运行实例程序二、参考链接一、Spring 整合 RocketMQ 不同于 RabbitMQ、ActiveMQ、Kafka 等消息中间件,Spring 社区已经通过多种方式提供了对这些中间件产品集成,例如通…...
如何使用SpringBoot ⽇志?
Spring Boot自定义日志的打印:在一个类中先获取到打印日志对象(日志框架提供的日志对象,而日志框架默认已经集成到Spring Boot里了,springboot默认使用 slf4jlogback);注意:得到日志对象Logger ->来自于slf4j2、使用目志对象提…...
山东大学数字图像处理实验:MATLAB的图像显示方法
文章目录MATLAB 学习实验目的实验原理及方法实验内容MATLAB的图像显示方法实验目的实验内容MATLAB 学习 实验目的 了解 MATLAB 的基本功能及操作方法。掌握典型离散信号的 Matlab 产生和显示。 实验原理及方法 在 MATLAB 中, 序列是用矩阵向量表示, 但它没有包含采样信息, …...
Java缓存面试题——Redis解决方案
文章目录1、什么是缓存击穿?该如何解决2、什么是缓存穿透?该如何解决3、什么是缓存雪崩?该如何解决4、什么是BigKey?该如何解决bigkey的危害发现bigkey解决bigkey5、redis过期策略都有哪些?6、讲一讲Redis缓存的数据一…...
Flink:The generic type parameters of ‘Collector‘ are missing 类型擦除
类型擦除问题处理报错日志描述问题描述报错解决其他方法方法一:TypeInformation方法二:TypeHint报错日志描述 报错日志: The generic type parameters of Collector are missing. In many cases lambda methods dont provide enough informa…...
MySQL查询操作
系列文章目录前言一、简单查询SELECT子句SELECT后面之间跟列名DISTINCT,ALL列表达式列更名WHERE子句WHERE子句中可以使用的查询条件比较运算BETWEEN...AND...集合查询:IN模糊查询LIKE空值比较:IS NULL多重条件查询SELECT 的基本结构ORDER BY子句排序聚集…...
Redis-day01-note
Redis-day01-note 文章目录**Redis-day01-note****安装****配置文件详解****数据类型****字符串类型(string)**列表数据类型(List)****与python交互**Redis介绍特点及优点 1、开源的,使用C编写,基于内存且支持持久化 2、高性能的…...
嵌入式C基础知识(19)
时序在前面我们说到当处理器要向外设芯片写数据时,需要先将所需访问的外设的地址放在地址总线上,然后,由译码器将地址总线上的数据转换成片选信号,片选信号则使能目标外设芯片,接下来处理器写数据到数据总线上…...
java 2(程序流程控制)【含例题详解】
java ——程序流程控制 ✍作者:电子科大不知名程序员 🌲专栏:java学习指导 各位读者如果觉得博主写的不错,请诸位多多支持;如果有错误的地方,欢迎在评论区指出 目录java ——程序流程控制分支结构if-elsesw…...
基于Conda完成创建多版本python环境
文章目录基于Conda完成创建多版本python环境基于Conda完成创建多版本python环境 通过cmd打开conda环境 d:\ProgramData\Anaconda3\Scripts\activate创建python3.7的环境 conda create -n py3.7 python3.7产生错误 Collecting package metadata (repodata.json): failed Unav…...
35岁的测试被裁,公司地位还不如00后...
国内的互联网行业发展较快,所以造成了技术研发类员工工作强度比较大,同时技术的快速更新又需要员工不断的学习新的技术。因此淘汰率也比较高,超过35岁的基层研发类员工,往往因为家庭原因、身体原因,比较难以跟得上工作…...
vue H5跳转小程序报错:config:fail,Error: 系统错误,错误码:63002,invalid signature
微信开发者工具下载地址与更新日志 错误码:63002,invalid signature 无效的签名 附录5 微信网页开发 /JS-SDK说明文档 微信 JS 接口签名校验工具 全局返回码说明 排查步骤 确认签名算法正确,可用 http://mp.weixin.qq.com/debug/cgi-bin/sand…...
来面试阿里测开工程师,HR问我未来3-5年规划,我给HR画个大饼。
在面试的过程中是不是经常被面试官问未来几年的职业规划?你会答吗?是不是经常脑袋里一片空白,未来规划?我只是想赚更多的钱啊,哈哈哈,今天我来教大家,如何给面试官画一个大饼,让他吃的不亦乐乎…...
【2373. 矩阵中的局部最大值】
来源:力扣(LeetCode) 描述: 给你一个大小为 n x n 的整数矩阵 grid 。 生成一个大小为 (n - 2) x (n - 2) 的整数矩阵 maxLocal ,并满足: maxLocal[i][j] 等于 grid 中以 i 1 行和 j 1 列为中心的 3 …...
Read book Netty in action(Chapter VII)--ChannelHandler和ChannelPipeline
序言 我们曾经学过了ByteBuf – netty的数据容器,还有ChannelHandler和ChannelPipeline,这一把将他们组合起来,这些组件的交互正是Netty的灵魂所在! ChannelHanlder家族 在详细地学习ChannelHanlder之前,我们将在Ne…...
react的严格模式 和 解决react useEffect执行两次
useEffect执行两次 这个问题,主要是刚接触react的时候发的问题,当时也没总结。现在回过头来再总结一次!!! 文章目录useEffect执行两次前言一、为什么useEffect执行两次1.React的严格模式(模版创建项目&…...
C++中的STL
一、概念 STL,英文全称 standard template library,中文可译为标准模板库或者泛型库,其包含有大量的模板类和模板函数,是 C 提供的一个基础模板的集合,用于完成诸如输入/输出、数学计算等功能。 STL 最初由惠普实验室…...
【沐风老师】3dmax一键窗户生成器插件使用方法详解
3dmax一键窗户生成器插件教程 3dMax一键窗户生成器是一个在3dMax中自动创建3D窗户模型的脚本。它有28种风格的窗户样式,可以在Archviz项目中灵活应用,同时为3D艺术家节省大量时间。 【适用版本】 适用3dMax 2018.2及更高版本 【安装方法】 1.解压缩包&…...
【图像处理】数字图像处理基础(分辨率,像素,显示...)
Table of Contents1.数字图像处理基础1.1 图像表示1.1.1 图像成像模型1.1.2 数字图像的表示a.图像采样b.图像灰度的量化c.算比特数1.2 分辨率1.2.1 空间分辨率1.2.2 灰度分辨率1.3 像素间的关系1.3.1 像素邻域a.4邻域b.4对角邻域c.8邻域1.3.2 像素邻接1.3.3 像素连通1.3.4 像素…...
UE实现相机飞行效果CesiumForUnreal之DynamicPawn飞行原理浅析
文章目录 1.实现目标2.实现过程2.1 FlyTo实现原理与代码2.2 DynamicPawn飞行原理3.参考资料1.实现目标 基于CesiumForUnreal的Dynamic Pawn实现飞行效果GIF动图: 2.实现过程 实现原理较为简单,基于CesiumForUnreal插件中DynamicPawn中的Camera实现相关功能。其中FlyTo直接通…...
AIGC被ChatGPT带火!底层基础算力有望爆发式增长
ChatGPT火爆全球的背后,可以窥见伴随人工智能技术的发展,数字内容的生产方式向着更加高效迈进。ChatGPT属于AIGC的具体应用,而AIGC是技术驱动的数字内容新生产方式。AIGC类产品未来有望成为5G时代新的流量入口,率先受益的有望是AI…...
【链表OJ题(一)】移除链表元素
📝个人主页:Sherry的成长之路 🏠学习社区:Sherry的成长之路(个人社区) 📖专栏链接:数据结构 🎯长路漫漫浩浩,万事皆有期待 文章目录链表OJ题(一)1. 移除…...
【解锁技能】学会Python条件语句的终极指南!
文章目录前言一. python条件语句的介绍1.1 什么是条件语句1.2 条件语句的语法1.3 关于内置函数bool()二. 分支语句之单分支三. 多分支语句3.1 二分支语句3.2 多分支语句3.3 嵌套循环总结前言 🏠个人主页:欢迎访问 沐风晓月的博客 🧑个人简介&…...
如何通过rem实现移动端的适配?
一、rem、em、vw\vh的区别: rem:参照HTML根元素的font-size em:参照自己的font-size vw/vh:将视口宽高平分100等份,数值就是所占比例 <!DOCTYPE html> <html lang"en"><head><meta…...
【论文阅读】-姿态识别
记录论文阅读,希望能了解我方向的邻域前沿吧 粗读 第一篇 ATTEND TO WHO YOU ARE: SUPERVISING SELF-ATTENTION FOR KEYPOINT DETECTION AND INSTANCE-AWARE ASSOCIATION 翻译:https://editor.csdn.net/md?not_checkout1&spm1001.2014.3001.5352…...
3.1 模拟栈+表达式求值
模拟栈 题目链接 栈的数组模拟非常简单,不详细描述 设置一个指针指向栈顶第一个元素即可 STL中stack实现已经更新在STL_Stack #include<iostream> #include<string>using namespace std;const int N1e51; int m; string s; int stack[N]; int p;//指针…...
【Python语言基础】——Python 创建表
Python语言基础——Python 创建表 文章目录 Python语言基础——Python 创建表一、Python 创建表一、Python 创建表 创建表 如需在 MySQL 中创建表,请使用 “CREATE TABLE” 语句。 请确保在创建连接时定义数据库的名称。 实例 创建表 “customers”: import mysql.connector…...
外贸建站,为什么别人的询盘更多更精准?
大多企业进行外贸建站的目的就是想要获得更多的精准询盘,但是具体该如何做,大多企业都没有方向,要么就是在网上看各种不系统的文章学着操作,要么就找个建站公司做好网站就不管了,而最终结果都不甚理想。那么怎样才能让…...
Gateway集成Netty服务
Gateway和Netty都有盲区的感觉; 一、Netty简介 Netty是一个异步的,事件驱动的网络应用框架,用以快速开发高可靠、高性能的网络应用程序。 传输服务:提供网络传输能力的管理; 协议支持:支持常见的数据传输…...
SpringMVC控制层private方法中出现注入的service对象空指针异常
一、现象 SpringMVC中controller里的private接口中注入的service层的bean为null,而同一个controller中访问修饰符为public和protected的方法不会出现这样的问题。 controller中的方法被AOP进行了代理,普通Controller如果没有AOP,private方法…...