代码随想录|392.判断子序列,115.不同的子序列(需要二刷)
392.判断子序列
先用双指针做
class Solution {public boolean isSubsequence(String s, String t) {//双指针int m=s.length();int n=t.length();int slow=0;int i=0;int j=0;while(i<m&&j<n){if(s.charAt(i)==t.charAt(j)){i++;System.out.println(i);}j++;}return i==m?true:false;}
}
再用动规
1.确定dp数组(dp table)以及下标的含义
dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。注意要判断s是否为t的子序列。即t的长度是大于等于s的
2.确定递推公式
if (s[i - 1] == t[j - 1]),那么dp[i][j] = dp[i - 1][j - 1] + 1;,因为找到了一个相同的字符
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];
3.dp初始化
dp[i][j]都是依赖于dp[i - 1][j - 1] 和 dp[i][j - 1],dp[0][0]表示两个空字符串相同子序列的长度,dp[i][0]表示下标为i-1的字符串s与空字符串t的相同子序列的长度,所以dp[0][0],dp[i][0]都初始化为0
4.遍历顺序
根据递推公式可知是从前往后的
5.推导dp

代码实现
class Solution {public boolean isSubsequence(String s, String t) {//动规int m=s.length();int n=t.length();int[][] dp=new int[m+1][n+1];for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s.charAt(i-1)==t.charAt(j-1)){//比较的是下标i-1和j-1对应的字符dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=dp[i][j-1];}}}return dp[m][n]==m?true:false;}
}
115.不同的子序列(需要二刷)
这里要明确,我们要求的是s中有多少个t
1.确定dp数组(dp table)以及下标的含义
dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
2.确定递推公式
当s[i - 1] 与 t[j - 1]相等时,dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j]。例如: s:bagg 和 t:bag ,s[3] 和 t[2]是相同的,但是字符串s也可以不用s[3]来匹配,即用s[0]s[1]s[2]组成的bag。当然也可以用s[3]来匹配,即:s[0]s[1]s[3]组成的bag。
所以当s[i - 1] 与 t[j - 1]相等时,dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
当s[i-1]与t[j-1]不相等时,s中只要一部分能组成t,不用s[i-1]来匹配(就是模拟在s中删除这个元素即:dp[i-1][j])所以递推公式:dp[i][j]=dp[i-1][j]
3.dp初始化
从递推公式dp[i][j]=dp[i-1][j]和dp[i][j]=dp[i-1][j-1]+dp[i-1][j]来看,dp[0][0]应该是1,空字符串s,可以删除0个元素,变成空字符串t。,dp[i][0]表示以i-1为结尾的字符串s中能匹配出多少个空字符串t,所以dp[i][0]一定都是1,因为也就是把以i-1为结尾的s,删除所有元素,出现空字符串的个数就是1;dp[0][j]表示空字符串s能匹配出以j-1为结尾的字符串t的个数,所以dp[0][j]一定都是0,s如论如何也变成不了t。
4.遍历顺序从前往后
5.推导dp

代码实现
class Solution {public int numDistinct(String s, String t) {int m=s.length();int n=t.length();int[][] dp=new int[m+1][n+1];//初始化for(int i=0;i<=m;i++){dp[i][0]=1;}// for (int j = 1; j < t.size(); j++) dp[0][j] = 0; //默认就是初始化为0//递推for(int i=1;i<=m;i++){for(int j=1;j<=n;j++){if(s.charAt(i-1)==t.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+dp[i-1][j]; //如s=bagg,t=bag}else{dp[i][j]=dp[i-1][j];//}}}return dp[m][n];}
}
相关文章:
代码随想录|392.判断子序列,115.不同的子序列(需要二刷)
392.判断子序列 先用双指针做 class Solution {public boolean isSubsequence(String s, String t) {//双指针int ms.length();int nt.length();int slow0;int i0;int j0;while(i<m&&j<n){if(s.charAt(i)t.charAt(j)){i;System.out.println(i);}j;}return im?…...
Linux——文件系统
✅<1>主页::我的代码爱吃辣 📃<2>知识讲解:Linux——文件系统 ☂️<3>开发环境:Centos7 💬<4>前言:上期我们了解了文件在内存中得组织方式,那么文件在磁盘中…...
《动手学深度学习 Pytorch版》 7.3 网络中的网络(NiN)
LeNet、AlexNet和VGG的设计模式都是先用卷积层与汇聚层提取特征,然后用全连接层对特征进行处理。 AlexNet和VGG对LeNet的改进主要在于扩大和加深这两个模块。网络中的网络(NiN)则是在每个像素的通道上分别使用多层感知机。 import torch fr…...
古代有没有电子元器件?
手机,电脑,电视等等电子产品,无时无刻充斥在我们的生活中,如果有一天突然没有了这些功能多样的电子产品,估计大部分人都会一时之间难以适应。 这就好比正在上网,结果突然被人断了网,导致无网络连…...
log4j2或者logback配置模版实现灵活输出服务名
介绍 在我们使用log4j2或者logback打印日志时,输出的内容中通常是一定要加上服务名的。以log4j2为例: <!--输出控制台的配置--> <Console name"Console" target"SYSTEM_OUT"><!-- 输出日志的格式 --><Patter…...
使用HTTP爬虫ip中的常见误区与解决方法
在如今的互联网时代,为了保障个人隐私和实现匿名浏览,许多人选择使用HTTP爬虫ip。然而,由于缺乏了解和使用经验,常常会出现一些误区。本文将为大家介绍使用HTTP爬虫ip过程中常见的误区,并提供相应的解决方法࿰…...
MySQL学习笔记3
MySQL的源码编译安装: 1、参考MySQL的源码安装官方文档: 2、源码安装定制选项: 3、源码安装三部曲:配置、编译、安装。 4、软件安装包: mysql-boost-5.7.43.tar.gz 5、安装需求: 安装需求具体配置安装目…...
快速掌握ES6
什么是ES6 ES6(ECMAScript 6),也被称为ES2015,是JavaScript的第六个版本,于2015年发布。ES6引入了许多新的语法和功能,旨在提高JavaScript的开发效率和代码质量。 ES6的一些主要特性和改进包括࿱…...
电池厂提供excel电池曲线zcv到mtk电池曲线zcv转换
#encoding:utf8 #电池厂提供excel电池曲线zcv到mtk电池曲线zcv转换 import pandas as pd import openpyxl import math # 读取Excel文件 df pd.read_excel("a55-zcv.xlsx") for j in range(0,10): if(j<3): offset0 #T0~T2 if(j3): offset…...
重写和重载、抽象类和接口
文章目录 前言一、重载与重写1.重载(Overload)(1)条件(2)举例 2.重写(Override)(1)规则(2)举例 3.重载和重写区别 二、抽象类与接口1.抽象类&…...
Untiy UDP局域网 异步发送图片
同步画面有问题,传图片吧 using System.Text; using System.Net.Sockets; using System.Collections; using System.Collections.Generic; using UnityEngine; using UnityEngine.Events; using System.Net; using System; using System.Threading.Tasks; using Sy…...
移动端H5封装一个 ScrollList 横向滚动列表组件,实现向左滑动
效果: 1.封装组件: <template><div class"scroll-list"><divclass"scroll-list-content":style"{ background, color, fontSize: size }"ref"scrollListContent"><div class"scroll…...
Docker一键安装和基本配置
一键安装脚本 注:该脚本需要root权限 curl -sSL https://get.docker.com/ | sh非root组用户赋权 sudo groupadd docker # 若使用一键安装脚本会自动创建这个组,提示已存在 sudo gpasswd -a ${USER} docker # 将当前用户添加到docker组,也…...
MVC设计思想理解和ASP.NET MVC理解
三层模式 三层模式包括:UI层,业务逻辑层,数据访问层,模型层 MVC设计思想和ASP.NET MVC理解 MVC设计思想: MVC的思想就是把我们的程序分为三个核心的模块,这三个模块的详细介绍如下: 模型(Model) :负责封装与引用程序的业务逻辑相关的数据以及对数据的处理方法。模型层有对…...
大模型应用选择对比
大模型应用选择对比 1、知识库对比:dify、fastgpt、langchatchat 2、agent构建器选择:flowise、langflow、bisheng 3、召回率提升方案...
c++STL概述
目录 STL基本概念 STL六大组件 STL的优点 STL三大组件 容器 算法 迭代器 普通的迭代器访问vector容器元素 算法for_each实现循环 迭代器指向的元素类型是自定义数据类型 迭代器指向容器 常用容器 string容器 string的基本概念 string容器的操作 string的构造函…...
利用容器技术优化DevOps流程
利用容器技术优化DevOps流程 随着云计算的快速发展,容器技术也日益流行。容器技术可以打包和分发应用程序,并实现快速部署和扩展。在DevOps流程中,容器技术可以大大优化开发、测试、部署和运维各个环节。本文将介绍如何利用容器技术优化DevO…...
91 # 实现 express 的优化处理
上一节实现 express 的请求处理,这一节来进行实现 express 的优化处理 让 layer 提供 match 方法去匹配 pathname,方便拓展让 layer 提供 handle_request 方法,方便拓展利用第三方库 methods 批量生成方法性能优化问题 进行路由懒加载&#…...
arcgis拓扑检查实现多个矢量数据之间消除重叠区域
目录 环境介绍: 操作任务: 步骤: 1、数据库和文件结构准备 2、建立拓扑规则 3、一直下一页默认参数后,进行拓扑检查 4、打开TP_CK_Topology,会自动带出拓扑要素,红色区域为拓扑错误的地方࿱…...
基于Vue+ELement搭建登陆注册页面实现后端交互
🎉🎉欢迎来到我的CSDN主页!🎉🎉 🏅我是Java方文山,一个在CSDN分享笔记的博主。📚📚 🌟推荐给大家我的专栏《ELement》。🎯🎯 …...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
三分算法与DeepSeek辅助证明是单峰函数
前置 单峰函数有唯一的最大值,最大值左侧的数值严格单调递增,最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值,最小值左侧的数值严格单调递减,最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...
【网络安全】开源系统getshell漏洞挖掘
审计过程: 在入口文件admin/index.php中: 用户可以通过m,c,a等参数控制加载的文件和方法,在app/system/entrance.php中存在重点代码: 当M_TYPE system并且M_MODULE include时,会设置常量PATH_OWN_FILE为PATH_APP.M_T…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
windows系统MySQL安装文档
概览:本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容,为学习者提供全面的操作指导。关键要点包括: 解压 :下载完成后解压压缩包,得到MySQL 8.…...
什么是VR全景技术
VR全景技术,全称为虚拟现实全景技术,是通过计算机图像模拟生成三维空间中的虚拟世界,使用户能够在该虚拟世界中进行全方位、无死角的观察和交互的技术。VR全景技术模拟人在真实空间中的视觉体验,结合图文、3D、音视频等多媒体元素…...
