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

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.判断子序列 题目链接&#xff1a;力扣链接 讲解链接&#xff1a;代码随想录讲解链接 题意&#xff1a;给定字符串 s 和 t &#xff0c;判断 s 是否为 t 的子序列。 字符串的一个子序列是原始字符串删除一些&#xff08;也可以不…...

c语言中磁盘文件的分类

#include <stdio.h> /*磁盘文件的分类&#xff1a; * 一个文件通常是磁盘上一段命名的存储区计算机的存储在物理上是二进制的&#xff0c; * 所以物理上所有的磁盘文件本质上都是一样的&#xff1a;以字节为单位进行顺序存储 * 从用户或者操作系统使用的角度&#xff08…...

Unity适配微信

使用的是微信开发的插件 GitHub - wechat-miniprogram/minigame-unity-webgl-transform 路径相关&#xff1a; Unity&#xff1a;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初阶】类和对象&#xff08;上&#xff09; 1.面向对象与面向过程的初步认识2.类的引入3. 类的定义4.类的访问限定符及封装4.1访问限定符4.2封装 5.类的作用域6.类的实例化6.类的对象的大小计算7.类的this指针7.1this指针的引入7.2this指针的一些特性 &#x1f4c3;博客主页…...

新版onenet平台安全鉴权的确定与使用

根据onenet官方更新的文档&#xff1a;平台提供开放的API接口&#xff0c;用户可以通过HTTP/HTTPS调用&#xff0c;进行设备管理&#xff0c;数据查询&#xff0c;设备命令交互等操作&#xff0c;在API的基础上&#xff0c;根据自己的个性化需求搭建上层应用。 为提高API访问安…...

容器核心技术-Namespace

一、容器 基于Linux 内核的 Cgroup&#xff0c; Namespace&#xff0c;以及Union FS等技术&#xff0c;对进程进行封装隔离&#xff0c;属于操作系统层面的虚拟化技术&#xff0c;由于隔离的进程独立于宿主和其它的隔离的进程&#xff0c;因此也称其为容器。 1.1 容器主要特性…...

linux写文件如何保证落盘?

3.1.1. sync sync函数只是将所有修改过的块缓冲区排入写队列&#xff0c;然后就返回&#xff0c;它并不等待实际写磁盘操作结束。通常称为 update的系统守护进程会周期性地&#xff08;一般每隔30秒&#xff09;调用sync函数。这就保证了定期冲洗内核的块缓冲区。命令 sync也…...

2023 electron最新最简版打包、自动升级详解

这里我将讲解一下从0搭建一个electron最简版架子&#xff0c;以及如何实现打包自动化更新 之前我有写过两篇文章关于electron框架概述以及 常用api的使用&#xff0c;感兴趣的同学可以看看 Electron桌面应用开发 Electron桌面应用开发2 搭建electron 官方文档&#xff1a;ht…...

ConcurrentHashMap是如何实现线程安全的

目录 原理&#xff1a; 初始化数据结构时的线程安全 put 操作时的线程安全 原理&#xff1a; 多段锁cassynchronize 初始化数据结构时的线程安全 在 JDK 1.8 中&#xff0c;初始化 ConcurrentHashMap 的时候这个 Node[] 数组是还未初始化的&#xff0c;会等到第一次 put() 方…...

MYSQL:索引与锁表范围简述

一、聚簇索引原则 当有主键索引时&#xff0c;选择主键索引&#xff1b;如果没有主键索引&#xff0c;选择第一个的unique索引&#xff1b;如果都没有就选择隐藏生成的ROW_ID。 二、加锁原则 来自知乎MySQL探秘(七):InnoDB行锁算法 - 知乎 (zhihu.com) 在不通过索引条件查询时…...

15 款 PDF 编辑器帮助轻松编辑、合并PDF文档

PDF 编辑器在当今的数字环境中至关重要&#xff0c;因为 PDF 已成为共享和存储信息的首选格式。只需几分钟&#xff0c;可靠的 PDF 编辑器即可让用户能够根据其特定需求修改、定制和定制文档。在本文中&#xff0c;我们全面汇编了 15 款最佳免费 PDF 编辑器&#xff0c;让您可以…...

PS Raw中文增效工具Camera Raw 16

Camera Raw 16 for mac&#xff08;PS Raw增效工具&#xff09;的功能特色包括强大的图像调整工具。例如&#xff0c;它提供白平衡、曝光、对比度、饱和度等调整选项&#xff0c;帮助用户优化图像的色彩和细节。此外&#xff0c;Camera Raw 16的界面简洁易用&#xff0c;用户可…...

Flink源码解析二之执行计划⽣成

JobManager Leader 选举 首先flink会依据配置获取RecoveryMode,RecoveryMode一共两两种:STANDALONE和ZOOKEEPER。 如果用户配置的是STANDALONE,会直接去配置中获取JobManager的地址如果用户配置的是ZOOKEEPER,flink会首先尝试连接zookeeper,利用zookeeper的leadder选举服务发现…...

MySQL遍历所有表所有字段查找字符数据

MySQL遍历所有表所有字段查找字符数据 工作中有一些数据查找&#xff0c;但是在那个库那个表那个字段中并不明确&#xff0c;特别是敏感字符查找&#xff0c;如果数据量并不大&#xff0c;我们可以采用遍历整个库、表中字符来查找相关数据来解决该问题。 我们可以写一个存储过…...

Java中的异常处理机制是怎样的?

Java中的异常处理机制主要包括以下几个部分&#xff1a; 异常类&#xff08;Exception Class&#xff09;&#xff1a;Java中的异常类继承自java.lang.Throwable&#xff0c;主要分为两大类&#xff1a;Error和Exception。Error表示程序无法处理的严重问题&#xff0c;如系统崩…...

高教社杯数模竞赛特辑论文篇-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&#xff0c;第i个数a[i](0<a[i]<2n) 构造一个长为n的整数序列b&#xff0c;满足&#xff1a; 1. 0到n-1在b数组中每个数恰好出现一次 2. 对于&#xff0c; 题目保证一定有解&#xff0c;有多组时可以输出任意一组 思路来源 …...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

AI+无人机如何守护濒危物种?YOLOv8实现95%精准识别

【导读】 野生动物监测在理解和保护生态系统中发挥着至关重要的作用。然而&#xff0c;传统的野生动物观察方法往往耗时耗力、成本高昂且范围有限。无人机的出现为野生动物监测提供了有前景的替代方案&#xff0c;能够实现大范围覆盖并远程采集数据。尽管具备这些优势&#xf…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...