day55【动态规划子序列】392.判断子序列 115.不同的子序列
文章目录
- 392.判断子序列
- 115.不同的子序列
392.判断子序列
-
题目链接:力扣链接
-
讲解链接:代码随想录讲解链接
-
题意:给定字符串 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 -
思路看代码注释
class Solution {public boolean isSubsequence(String s, String t) {char[] chars = s.toCharArray();char[] chart = t.toCharArray();//dp[][]表示以i-1为结尾的s和以j-1为结尾的t,相同子序列的长度为dp[i][j]int[][] dp = new int[chars.length+1][chart.length+1];//初始化:dp表示以i-1和j-1为结尾,那么dp[0][j]和dp[i][0]是无意义的,初始化为0即可。其他是由前面推导的,也赋值为0就行。for(int i = 1; i <= chars.length; i++) {for(int j = 1; j <= chart.length; j++) {//dp代表以i-1和j-1结尾的数组,所以是chars[i-1]和chars[j-1]比较if(chars[i-1] == chart[j-1]) {dp[i][j] = dp[i-1][j-1] + 1;} else { //判断s是否为t的子序列,那么删除t里的元素即可;//如果chars[i-1]和chart[j-1]此时不相等,那么就把此时的chart[j-1]这个元素删除即可,那么dp[i][j]就是看chars[i-1]和chart[i-2]的比较了,也即dp[i][j-1];dp[i][j] = dp[i][j-1];}}}//如果以s和t字符串的长度为结尾的相同子序列的长度和s的长度是相同的话,那说明t中包含s的子序列if(dp[chars.length][chart.length] == chars.length) {return true;} else {return false;}}
}
115.不同的子序列
-
题目链接:力扣链接
-
讲解链接:代码随想录讲解
-
题意:给你两个字符串 s 和 t ,统计并返回在 s 的 子序列 中 t 出现的个数,结果需要对 10e9 + 7 取模。
示例 1:输入:s = "rabbbit", t = "rabbit"输出:3解释:如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。rabbbitrabbbitrabbbit示例 2:输入:s = "babgbag", t = "bag"输出:5解释:如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。 babgbagbabgbagbabgbagbabgbagbabgbag -
思路 :看代码(自己还有点迷糊)
class Solution {public int numDistinct(String s, String t) {char[] charS = s.toCharArray();char[] charT = t.toCharArray();//代表以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]int[][] dp = new int[charS.length+1][charT.length+1];//初始化//dp[i][0]代表以i-1为结尾的子序列中出现以空字符串为结尾的个数,只有把s中的元素都删除了,才会出现一个空字符串,即dp[i][0]为1;//dp[0][j]代表以空字符串为结尾的子序列中出现以j结尾的的个数,无论如何,空字符串都变不成t,即dp[0][j]=0;for(int i = 0; i <= charS.length; i++) {dp[i][0] = 1;}for(int i = 1; i <= charS.length; i++) {for(int j = 1; j <= charT.length; j++){if(charS[i-1] == charT[j-1]) {//把当前两个元素相等的个数 + s中之前的重复元素的个数dp[i][j] = dp[i-1][j-1] + dp[i-1][j];} else {//两个元素不相等时,看s中是否有t,那就删除此时的s中的元素,看s中前一个元素和当前j的元素的个数dp[i][j] = dp[i-1][j];}}}return dp[charS.length][charT.length]; }
}
相关文章:
day55【动态规划子序列】392.判断子序列 115.不同的子序列
文章目录 392.判断子序列115.不同的子序列 392.判断子序列 题目链接:力扣链接 讲解链接:代码随想录讲解链接 题意:给定字符串 s 和 t ,判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些(也可以不…...
c语言中磁盘文件的分类
#include <stdio.h> /*磁盘文件的分类: * 一个文件通常是磁盘上一段命名的存储区计算机的存储在物理上是二进制的, * 所以物理上所有的磁盘文件本质上都是一样的:以字节为单位进行顺序存储 * 从用户或者操作系统使用的角度(…...
Unity适配微信
使用的是微信开发的插件 GitHub - wechat-miniprogram/minigame-unity-webgl-transform 路径相关: Unity:Application.streamingAssetsPath --> 配置的cdn路径StreamingAssets...
虚拟机本地磁盘在线扩容
背景 虚拟机本地盘对于host物理机来说就是一个LVM卷,虚拟化(libvirt+kvm_qemu)已经支持虚拟机磁盘在线调整,配合物理机lvm管理工具可实现云场景下虚拟机磁盘在线扩容功能。环境检查 (1)虚拟机本地盘信息 <disk type=block device=disk><driver...
ACTIVE_MQ学习
ActiveMq学习①___入门概述https://blog.csdn.net/qq_45905724/article/details/131796502 ActiveMq学习②__安装与控制台https://blog.csdn.net/qq_45905724/article/details/133893214 ActiveMq学习③___Java编码实现ActiveMQ通讯https://blog.csdn.net/qq_45905724/articl…...
【C++初阶】类和对象(上)
【C初阶】类和对象(上) 1.面向对象与面向过程的初步认识2.类的引入3. 类的定义4.类的访问限定符及封装4.1访问限定符4.2封装 5.类的作用域6.类的实例化6.类的对象的大小计算7.类的this指针7.1this指针的引入7.2this指针的一些特性 📃博客主页…...
新版onenet平台安全鉴权的确定与使用
根据onenet官方更新的文档:平台提供开放的API接口,用户可以通过HTTP/HTTPS调用,进行设备管理,数据查询,设备命令交互等操作,在API的基础上,根据自己的个性化需求搭建上层应用。 为提高API访问安…...
容器核心技术-Namespace
一、容器 基于Linux 内核的 Cgroup, Namespace,以及Union FS等技术,对进程进行封装隔离,属于操作系统层面的虚拟化技术,由于隔离的进程独立于宿主和其它的隔离的进程,因此也称其为容器。 1.1 容器主要特性…...
linux写文件如何保证落盘?
3.1.1. sync sync函数只是将所有修改过的块缓冲区排入写队列,然后就返回,它并不等待实际写磁盘操作结束。通常称为 update的系统守护进程会周期性地(一般每隔30秒)调用sync函数。这就保证了定期冲洗内核的块缓冲区。命令 sync也…...
2023 electron最新最简版打包、自动升级详解
这里我将讲解一下从0搭建一个electron最简版架子,以及如何实现打包自动化更新 之前我有写过两篇文章关于electron框架概述以及 常用api的使用,感兴趣的同学可以看看 Electron桌面应用开发 Electron桌面应用开发2 搭建electron 官方文档:ht…...
ConcurrentHashMap是如何实现线程安全的
目录 原理: 初始化数据结构时的线程安全 put 操作时的线程安全 原理: 多段锁cassynchronize 初始化数据结构时的线程安全 在 JDK 1.8 中,初始化 ConcurrentHashMap 的时候这个 Node[] 数组是还未初始化的,会等到第一次 put() 方…...
MYSQL:索引与锁表范围简述
一、聚簇索引原则 当有主键索引时,选择主键索引;如果没有主键索引,选择第一个的unique索引;如果都没有就选择隐藏生成的ROW_ID。 二、加锁原则 来自知乎MySQL探秘(七):InnoDB行锁算法 - 知乎 (zhihu.com) 在不通过索引条件查询时…...
15 款 PDF 编辑器帮助轻松编辑、合并PDF文档
PDF 编辑器在当今的数字环境中至关重要,因为 PDF 已成为共享和存储信息的首选格式。只需几分钟,可靠的 PDF 编辑器即可让用户能够根据其特定需求修改、定制和定制文档。在本文中,我们全面汇编了 15 款最佳免费 PDF 编辑器,让您可以…...
PS Raw中文增效工具Camera Raw 16
Camera Raw 16 for mac(PS Raw增效工具)的功能特色包括强大的图像调整工具。例如,它提供白平衡、曝光、对比度、饱和度等调整选项,帮助用户优化图像的色彩和细节。此外,Camera Raw 16的界面简洁易用,用户可…...
Flink源码解析二之执行计划⽣成
JobManager Leader 选举 首先flink会依据配置获取RecoveryMode,RecoveryMode一共两两种:STANDALONE和ZOOKEEPER。 如果用户配置的是STANDALONE,会直接去配置中获取JobManager的地址如果用户配置的是ZOOKEEPER,flink会首先尝试连接zookeeper,利用zookeeper的leadder选举服务发现…...
MySQL遍历所有表所有字段查找字符数据
MySQL遍历所有表所有字段查找字符数据 工作中有一些数据查找,但是在那个库那个表那个字段中并不明确,特别是敏感字符查找,如果数据量并不大,我们可以采用遍历整个库、表中字符来查找相关数据来解决该问题。 我们可以写一个存储过…...
Java中的异常处理机制是怎样的?
Java中的异常处理机制主要包括以下几个部分: 异常类(Exception Class):Java中的异常类继承自java.lang.Throwable,主要分为两大类:Error和Exception。Error表示程序无法处理的严重问题,如系统崩…...
高教社杯数模竞赛特辑论文篇-2023年A题:定日镜场的优化设计(附获奖论文及MATLAB代码实现)
目录 摘 要 一、 问题重述 1.1 问题背景 1.2 问题重述 二、 模型假设 三、 符号说明...
c语言实现http下载功能,显示进度条和下载速率
#include <stdio.h>//printf #include <string.h>//字符串处理 #include <sys/socket.h>//套接字 #include <arpa/inet.h>//ip地址处理 #include <fcntl.h>//open系统调用 #include <unistd.h>//write系统调用 #include <netdb.h>//…...
Educational Codeforces Round 157 (Rated for Div. 2) D. XOR Construction (思维题)
题目 给定长为n-1(n<2e5)的整数序列a,第i个数a[i](0<a[i]<2n) 构造一个长为n的整数序列b,满足: 1. 0到n-1在b数组中每个数恰好出现一次 2. 对于, 题目保证一定有解,有多组时可以输出任意一组 思路来源 …...
【项目实战】通过多模态+LangGraph实现PPT生成助手
PPT自动生成系统 基于LangGraph的PPT自动生成系统,可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析:自动解析Markdown文档结构PPT模板分析:分析PPT模板的布局和风格智能布局决策:匹配内容与合适的PPT布局自动…...
c#开发AI模型对话
AI模型 前面已经介绍了一般AI模型本地部署,直接调用现成的模型数据。这里主要讲述讲接口集成到我们自己的程序中使用方式。 微软提供了ML.NET来开发和使用AI模型,但是目前国内可能使用不多,至少实践例子很少看见。开发训练模型就不介绍了&am…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
【JVM】Java虚拟机(二)——垃圾回收
目录 一、如何判断对象可以回收 (一)引用计数法 (二)可达性分析算法 二、垃圾回收算法 (一)标记清除 (二)标记整理 (三)复制 (四ÿ…...
第7篇:中间件全链路监控与 SQL 性能分析实践
7.1 章节导读 在构建数据库中间件的过程中,可观测性 和 性能分析 是保障系统稳定性与可维护性的核心能力。 特别是在复杂分布式场景中,必须做到: 🔍 追踪每一条 SQL 的生命周期(从入口到数据库执行)&#…...
从面试角度回答Android中ContentProvider启动原理
Android中ContentProvider原理的面试角度解析,分为已启动和未启动两种场景: 一、ContentProvider已启动的情况 1. 核心流程 触发条件:当其他组件(如Activity、Service)通过ContentR…...
永磁同步电机无速度算法--基于卡尔曼滤波器的滑模观测器
一、原理介绍 传统滑模观测器采用如下结构: 传统SMO中LPF会带来相位延迟和幅值衰减,并且需要额外的相位补偿。 采用扩展卡尔曼滤波器代替常用低通滤波器(LPF),可以去除高次谐波,并且不用相位补偿就可以获得一个误差较小的转子位…...
嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)
目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 编辑编辑 UDP的特征 socke函数 bind函数 recvfrom函数(接收函数) sendto函数(发送函数) 五、网络编程之 UDP 用…...
从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
字符串哈希+KMP
P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...
