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

代码随想录算法训练营第五十七天 | 392.判断子序列 115.不同的子序列

1. 判断子序列

392. 判断子序列 - 力扣(LeetCode)

dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度。

class Solution {public boolean isSubsequence(String s, String t) {//dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。int ls = s.length();int lt = t.length();int[][] dp = new int[ls + 1][lt + 1];for(int i = 1; i <= ls; i++){for(int j = 1; j <= lt; j++){if(s.charAt(i-1) == t.charAt(j-1))dp[i][j] = dp[i-1][j-1] + 1;elsedp[i][j] = dp[i][j-1];}}return dp[ls][lt] == ls? true: false;}
}

2. 不同的子序列

115. 不同的子序列 - 力扣(LeetCode)

dp[i][j]:s中[0: i-1] 出现 t中 [0: j-1] 个数。(i j 为0 可以理解为空字符串)

可以理解为 字符串 s[i-1] 删除元素 能否变成 t[j-1] 

如果当前位置上的两个元素相等了 bagg ba

那么这个位置的个数等于 bagg ba bagg bag

if(s.charAt(i-1) == t.charAt(j-1))

                    dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; (包含当前组成情况 + 不包含当前组成情况)

既然s[i-1]可以组成 t[j-1],那么还要看s不包含(i-1)的情况(前面可能已经组成了,得加上)

如果当前位置上的两个元素不相等 bagg ba

不相等了,就看s[i]的字串s[i - 1] 的组成个数

class Solution {public int numDistinct(String s, String t) {// dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。int ls = s.length();int lt = t.length();int[][] dp = new int[ls+1][lt+1];for (int i = 0; i < ls + 1; i++) {dp[i][0] = 1; // s[0-1:i-1] 可以构成 t[0-1](空字符串)}for(int i = 1; i <= ls; i++){for(int j = 1; j <= lt; j++){if(s.charAt(i-1) == t.charAt(j-1))dp[i][j] = dp[i-1][j-1] + dp[i-1][j];// 包括s当前元素 + 不包括s当前元素elsedp[i][j] = dp[i-1][j];}}return dp[ls][lt];}
}

 

相关文章:

代码随想录算法训练营第五十七天 | 392.判断子序列 115.不同的子序列

1. 判断子序列 392. 判断子序列 - 力扣&#xff08;LeetCode&#xff09; dp[i][j] 表示以下标i-1为结尾的字符串s&#xff0c;和以下标j-1为结尾的字符串t&#xff0c;相同子序列的长度。 class Solution {public boolean isSubsequence(String s, String t) {//dp[i][j] 表示…...

Kafka日志索引详解以及生产常见问题分析与总结

文章目录 1、Kafka的Log日志梳理1.1、Topic下的消息是如何存储的&#xff1f;1.1.1、 log文件追加记录所有消息1.1.2、 index和timeindex加速读取log消息日志。 1.2、文件清理机制1.2.1、如何判断哪些日志文件过期了1.2.2、过期的日志文件如何处理 1.3、Kafka的文件高效读写机制…...

vue中 css scoped原理

Vue中css的逻辑是先放子组件&#xff0c;然后放父组件&#xff0c;所以同样的css类名&#xff0c;子组件会被父组件覆盖 html 如下 子被父覆盖 scoped是通过给组件加hash值&#xff0c;锁定组件。 父子组件均scoped的情况下&#xff0c;子仍会覆盖 还是被覆盖了 如何避免被…...

tf.compat.v1.global_variables()

tf.global_variables tf.global_variables() 是 TensorFlow 1.x 中的一个函数&#xff0c;它返回图中所有的全局变量。在 TensorFlow 2.x 中&#xff0c;这个函数已经被移除了&#xff0c;取而代之的是 tf.compat.v1.global_variables()。 然而&#xff0c;在 TensorFlow 2.x …...

登录注册实现

一、前端页面注册到Vue 1.创建登录和注册组件 <template><div>login</div></template><script> export default {name: HomeView,data() {return {}},methods: {}, } </script><template><div>register</div></tem…...

Push rejected: Push to origin/master was rejected

Push rejected: Push to origin/master was rejected 原因&#xff1a;推拒绝&#xff1a;推送到起源/主人被拒绝 解决方案如下&#xff1a; 方案1&#xff1a; 1.在Idea打开终端 方案2&#xff1a; 1、在对应项目文件里打开 Git Bash 然后依次输入&#xff1a; git pull …...

在线OJ项目核心思路

文章目录 在线OJ项目核心思路1. 项目介绍2.预备知识理解多进程编程为啥采用多进程而不使用多线程?标准输入&标准输出&标准错误 3.项目实现题目API实现相关实体类定义新增/修改题目获取题目列表 编译运行编译运行流程 4.统一功能处理 在线OJ项目核心思路 1. 项目介绍 …...

Spring MVC:数据绑定

Spring MVC 数据绑定数据类型转换数据格式化数据校验 附 数据绑定 数据绑定&#xff0c;指 Web 页面上请求和响应的数据与 Controller 中对应处理方法上的对象绑定&#xff08;即是将用户提交的表单数据绑定到 Java 对象中&#xff09;。 过程如下&#xff1a; ServletRequest…...

STM32CubeMX学习笔记-USB接口使用(HID按键)

STM32CubeMX学习笔记-USB接口使用&#xff08;HID按键&#xff09; 一、USB简介1.1 USB HID简介 二、新建工程1. 打开 STM32CubeMX 软件&#xff0c;点击“新建工程”2. 选择 MCU 和封装3. 配置时钟4. 配置调试模式 三、USB3.1 参数配置3.2 引脚配置3.3 配置时钟3.4 USB Device…...

C#,数值计算——Ranq2的计算方法与源程序

1 文本格式 using System; namespace Legalsoft.Truffer { /// <summary> /// Backup generator if Ranq1 has too short a period and Ran is too slow.The /// period is 8.5E37. Calling conventions same as Ran, above. /// </summary> …...

C/C++ 数据结构 - 链表

1.单链表 https://blog.csdn.net/qq_36806987/article/details/79858957 1 #include<stdio.h>2 #include<stdlib.h>3 4 /*结构体部分*/5 typedef struct Node6 {7 int data; //数值域8 struct Node *next; //指针域9 }N;10 11 N *Init() //初始化单…...

【算法基础】一文掌握十大排序算法,冒泡排序、插入排序、选择排序、归并排序、计数排序、基数排序、希尔排序和堆排序

目录 1 冒泡排序&#xff08;Bubble Sort&#xff09; 2 插入排序&#xff08;Insertion Sort&#xff09; 3 选择排序&#xff08;Selection Sort&#xff09; 4. 快速排序&#xff08;Quick Sort&#xff09; 5. 归并排序&#xff08;Merge Sort&#xff09; 6 堆排序 …...

javascript二维数组(3):指定数组元素的特定属性进行搜索

js中对数组&#xff0c; var data [{“name”: “《西游记》”, “author”: “吴承恩”, “cat”: “A级书刊”, “num”: 3},{“name”: “《三国演义》”, “author”: “罗贯中”, “cat”: “A级书刊”, “num”: 8},{“name”: “《红楼梦》”, “author”: “曹雪芹”,…...

使用Qt进行HTTP通信的方法

文章目录 1 HTTP协议简介1.1 HTTP协议的历史和发展1.2 HTTP协议的特点1.3 HTTP的工作过程1.4 请求报文1.5 响应报文 2 使用Qt进行HTTP通信2.1 Qt的HTTP通信类2.2 HTTP通信过程 3 JSON3.1 cJSON库简介3.2 cJSON库的设计思想和数据结构3.3 cJSON库的使用方法 1 HTTP协议简介 1.1…...

第45节——页面中修改redux里的数据

一、什么是action 在 Redux 中&#xff0c;Action 是一个简单的 JavaScript 对象&#xff0c;用于描述对应应用中的某个事件&#xff08;例如用户操作&#xff09;所发生的变化。它包含了一个 type 属性&#xff0c;用于表示事件的类型&#xff0c;以及其他一些可选的数据。 …...

软考 系统架构设计师系列知识点之软件架构风格(2)

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之软件架构风格&#xff08;1&#xff09; 这个十一注定是一个不能放松、保持“紧”的十一。由于报名了全国计算机技术与软件专业技术资格&#xff08;水平&#xff09;考试&#xff0c;11月4号就要考试&#xff0c;因此…...

【C++11】Lambda 表达式:基本使用 和 底层原理

文章目录 Lambda 表达式1. 不考虑捕捉列表1.1 简单使用介绍1.2 简单使用举例 2. 捕捉列表 [ ] 和 mutable 关键字2.1 使用方法传值捕捉传引用捕捉 2.2 捕捉方法一览2.3 使用举例 3. lambda 的底层分析 Lambda 表达式 书写格式&#xff1a; [capture_list](parameters) mutabl…...

【网络安全---ICMP报文分析】Wireshark教程----Wireshark 分析ICMP报文数据试验

一&#xff0c;试验环境搭建 1-1 试验环境示例图 1-2 环境准备 两台kali主机&#xff08;虚拟机&#xff09; kali2022 192.168.220.129/24 kali2022 192.168.220.3/27 1-2-1 网关配置&#xff1a; 编辑-------- 虚拟网路编辑器 更改设置进来以后 &#xff0c;先选择N…...

【Docker】Docker的应用包含Sandbox、PaaS、Open Solution以及IT运维概念的详细讲解

前言 Docker 是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的Linux或Windows操作系统的机器上,也可以实现虚拟化,容器是完全使用沙箱机制,相互之间不会有任何接口。 &#x1f4d5;作者简介&#xff1a;热…...

Java Applet基础

Java Applet基础 目录 Java Applet基础 Applet的生命周期 "Hello, World" Applet: Applet 类 Applet的调用 获得applet参数 指定applet参数 应用程序转换成Applet 事件处理 显示图片 播放音频 applet是一种Java程序。它一般运行在支持Java的Web浏览器内。因…...

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

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

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

Kafka入门-生产者

生产者 生产者发送流程&#xff1a; 延迟时间为0ms时&#xff0c;也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于&#xff1a;异步发送不需要等待结果&#xff0c;同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...

莫兰迪高级灰总结计划简约商务通用PPT模版

莫兰迪高级灰总结计划简约商务通用PPT模版&#xff0c;莫兰迪调色板清新简约工作汇报PPT模版&#xff0c;莫兰迪时尚风极简设计PPT模版&#xff0c;大学生毕业论文答辩PPT模版&#xff0c;莫兰迪配色总结计划简约商务通用PPT模版&#xff0c;莫兰迪商务汇报PPT模版&#xff0c;…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...