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

代码随想录|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>主页&#xff1a;&#xff1a;我的代码爱吃辣 &#x1f4c3;<2>知识讲解&#xff1a;Linux——文件系统 ☂️<3>开发环境&#xff1a;Centos7 &#x1f4ac;<4>前言&#xff1a;上期我们了解了文件在内存中得组织方式&#xff0c;那么文件在磁盘中…...

《动手学深度学习 Pytorch版》 7.3 网络中的网络(NiN)

LeNet、AlexNet和VGG的设计模式都是先用卷积层与汇聚层提取特征&#xff0c;然后用全连接层对特征进行处理。 AlexNet和VGG对LeNet的改进主要在于扩大和加深这两个模块。网络中的网络&#xff08;NiN&#xff09;则是在每个像素的通道上分别使用多层感知机。 import torch fr…...

古代有没有电子元器件?

手机&#xff0c;电脑&#xff0c;电视等等电子产品&#xff0c;无时无刻充斥在我们的生活中&#xff0c;如果有一天突然没有了这些功能多样的电子产品&#xff0c;估计大部分人都会一时之间难以适应。 这就好比正在上网&#xff0c;结果突然被人断了网&#xff0c;导致无网络连…...

log4j2或者logback配置模版实现灵活输出服务名

介绍 在我们使用log4j2或者logback打印日志时&#xff0c;输出的内容中通常是一定要加上服务名的。以log4j2为例&#xff1a; <!--输出控制台的配置--> <Console name"Console" target"SYSTEM_OUT"><!-- 输出日志的格式 --><Patter…...

使用HTTP爬虫ip中的常见误区与解决方法

在如今的互联网时代&#xff0c;为了保障个人隐私和实现匿名浏览&#xff0c;许多人选择使用HTTP爬虫ip。然而&#xff0c;由于缺乏了解和使用经验&#xff0c;常常会出现一些误区。本文将为大家介绍使用HTTP爬虫ip过程中常见的误区&#xff0c;并提供相应的解决方法&#xff0…...

MySQL学习笔记3

MySQL的源码编译安装&#xff1a; 1、参考MySQL的源码安装官方文档&#xff1a; 2、源码安装定制选项&#xff1a; 3、源码安装三部曲&#xff1a;配置、编译、安装。 4、软件安装包&#xff1a; mysql-boost-5.7.43.tar.gz 5、安装需求&#xff1a; 安装需求具体配置安装目…...

快速掌握ES6

什么是ES6 ES6&#xff08;ECMAScript 6&#xff09;&#xff0c;也被称为ES2015&#xff0c;是JavaScript的第六个版本&#xff0c;于2015年发布。ES6引入了许多新的语法和功能&#xff0c;旨在提高JavaScript的开发效率和代码质量。 ES6的一些主要特性和改进包括&#xff1…...

电池厂提供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.重载&#xff08;Overload&#xff09;&#xff08;1&#xff09;条件&#xff08;2&#xff09;举例 2.重写&#xff08;Override)&#xff08;1&#xff09;规则&#xff08;2&#xff09;举例 3.重载和重写区别 二、抽象类与接口1.抽象类&…...

Untiy UDP局域网 异步发送图片

同步画面有问题&#xff0c;传图片吧 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 横向滚动列表组件,实现向左滑动

效果&#xff1a; 1.封装组件&#xff1a; <template><div class"scroll-list"><divclass"scroll-list-content":style"{ background, color, fontSize: size }"ref"scrollListContent"><div class"scroll…...

Docker一键安装和基本配置

一键安装脚本 注&#xff1a;该脚本需要root权限 curl -sSL https://get.docker.com/ | sh非root组用户赋权 sudo groupadd docker # 若使用一键安装脚本会自动创建这个组&#xff0c;提示已存在 sudo gpasswd -a ${USER} docker # 将当前用户添加到docker组&#xff0c;也…...

MVC设计思想理解和ASP.NET MVC理解

三层模式 三层模式包括:UI层,业务逻辑层,数据访问层,模型层 MVC设计思想和ASP.NET MVC理解 MVC设计思想: MVC的思想就是把我们的程序分为三个核心的模块,这三个模块的详细介绍如下: 模型(Model) :负责封装与引用程序的业务逻辑相关的数据以及对数据的处理方法。模型层有对…...

大模型应用选择对比

大模型应用选择对比 1、知识库对比&#xff1a;dify、fastgpt、langchatchat 2、agent构建器选择&#xff1a;flowise、langflow、bisheng 3、召回率提升方案...

c++STL概述

目录 STL基本概念 STL六大组件 STL的优点 STL三大组件 容器 算法 迭代器 普通的迭代器访问vector容器元素 算法for_each实现循环 迭代器指向的元素类型是自定义数据类型 迭代器指向容器 常用容器 string容器 string的基本概念 string容器的操作 string的构造函…...

利用容器技术优化DevOps流程

利用容器技术优化DevOps流程 随着云计算的快速发展&#xff0c;容器技术也日益流行。容器技术可以打包和分发应用程序&#xff0c;并实现快速部署和扩展。在DevOps流程中&#xff0c;容器技术可以大大优化开发、测试、部署和运维各个环节。本文将介绍如何利用容器技术优化DevO…...

91 # 实现 express 的优化处理

上一节实现 express 的请求处理&#xff0c;这一节来进行实现 express 的优化处理 让 layer 提供 match 方法去匹配 pathname&#xff0c;方便拓展让 layer 提供 handle_request 方法&#xff0c;方便拓展利用第三方库 methods 批量生成方法性能优化问题 进行路由懒加载&#…...

arcgis拓扑检查实现多个矢量数据之间消除重叠区域

目录 环境介绍&#xff1a; 操作任务&#xff1a; 步骤&#xff1a; 1、数据库和文件结构准备 2、建立拓扑规则 3、一直下一页默认参数后&#xff0c;进行拓扑检查 4、打开TP_CK_Topology&#xff0c;会自动带出拓扑要素&#xff0c;红色区域为拓扑错误的地方&#xff1…...

基于Vue+ELement搭建登陆注册页面实现后端交互

&#x1f389;&#x1f389;欢迎来到我的CSDN主页&#xff01;&#x1f389;&#x1f389; &#x1f3c5;我是Java方文山&#xff0c;一个在CSDN分享笔记的博主。&#x1f4da;&#x1f4da; &#x1f31f;推荐给大家我的专栏《ELement》。&#x1f3af;&#x1f3af; &#x1…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

Vue ③-生命周期 || 脚手架

生命周期 思考&#xff1a;什么时候可以发送初始化渲染请求&#xff1f;&#xff08;越早越好&#xff09; 什么时候可以开始操作dom&#xff1f;&#xff08;至少dom得渲染出来&#xff09; Vue生命周期&#xff1a; 一个Vue实例从 创建 到 销毁 的整个过程。 生命周期四个…...