【代码训练营】day54 | 392.判断子序列 115.不同的子序列
所用代码 java
判断子序列 LeetCode 392
题目链接:判断子序列 LeetCode 392 - 简单
思路
这题和之前求最长公共子序列一样。
-
dp[i] [j]:以i-1为结尾的字符串s 和 以j-1为结尾的字符串t 组成的相同子序列的长度
-
递推公式:
- 相等
dp[i][j] = dp[i-1][j-1] - 不相等
dp[i][j] = dp[i][j-1]
- 相等
-
初始化:0行0列无意义,初始化为0
-
遍历顺序
-
打印dp
class Solution {public boolean isSubsequence(String s, String t) {int n1 = s.length();int n2 = t.length();int[][] dp = new int[n1+1][n2+1];for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (s.charAt(i-1) == t.charAt(j-1)){dp[i][j] = dp[i-1][j-1] + 1;}else {dp[i][j] = dp[i][j-1];}}
// System.out.println(Arrays.toString(dp[i]));}return dp[n1][n2] == n1;}
}
总结
本题和昨天的最长公共子序列几乎一模一样,甚至更简单一点。因为我们只用判断字符串s是不是子序列就行了,而不用去两个字符串里面找相同的子序列。
不同的子序列 LeetCode 115
题目链接:不同的子序列 LeetCode 115 - 困难
思路
无。
s里面如何删除元素可以得到t?
-
dp[i] [j]:以i-1为结尾的s中有以j-1为结尾的t的个数为dp[i] [j]
-
递推公式:
-
相等
if(s[i-1] == t[j-1])- 使用i-1:
dp[i][j] = dp[i-1][j-1] - 不使用i-1:
dp[i-1][j] - 不用考虑是否使用t,因为t是子串
- 使用i-1:
-
不等
else dp[i][j] = dp[i-1][j]
-
-
初始化:
- 第一行(子串空字符串,所以主串只有全部删完的情况)
dp[i][0] = 1 - 第一列(主串s为空串,所以没有能匹配的情况)
dp[0][j] = 0 dp[0][0] = 1
- 第一行(子串空字符串,所以主串只有全部删完的情况)
-
打印dp
class Solution {public int numDistinct(String s, String t) {int n1 = s.length();int n2 = t.length();int[][] dp = new int[n1+1][n2+1];// 初始化// n1=0, 即空串中包含子序列t的情况为0// n2=0, 即s中包含子序列为空串的情况为1// n1=0,n2=2, 即空串中包含空串的情况为1for (int i = 0; i < n1; i++) {dp[i][0] = 1;}
for (int i = 1; i <= n1; i++) {for (int j = 1; j <= n2; j++) {if (s.charAt(i-1) == t.charAt(j-1)){// 相等的情况,由双方的上一位,加上s的上一位决定(删掉s对应的数)dp[i][j] = dp[i-1][j-1] + dp[i-1][j];}else {// 不相等的情况,由s的上一位觉得(删掉s对应的数)dp[i][j] = dp[i-1][j];}}}return dp[n1][n2];}
}
总结
我们可以打印出来dp数组以便更好的理解该题,上侧还有一种i=0的情况全为0(0,0为1)
Finished:Your input:"babgbag""bag"Output:5Expected:5stdout:1 0 0 0[1, 1, 0, 0][1, 1, 1, 0][1, 2, 1, 0][1, 2, 1, 1][1, 3, 1, 1][1, 3, 4, 1][0, 3, 4, 5]
可以看到s的第一个字母b和t的第一个字母b一样,所以匹配成功,即dp[1][1] = 1,
然后s的第一个字母b和t的第二个字母a不匹配,所以应看s的前一个字母(上一行),即dp[1][2] = 0
最后s的第一个字母b和t的第三个字母g不匹配,所以dp[1][2] = 0
…
我们看s取第二个b的时候,也就是第三行数据,由于t的第一个字母也是b,匹配成功,即dp[3][1]等于双方各删一个值的情况(t删了为空串,匹配,结果为1)加 仅s删一个值的情况(回退一位到s取a,此时s为ba.gbgab,也前面也有传递的结果1),所以dp[3][2]= 2
…
…
我们每次都这样往后推,相等即都删掉一个数,不等即为s删掉一个数,把前面的结果往后利用,就可以得到包含所有子串的数量。
相关文章:
【代码训练营】day54 | 392.判断子序列 115.不同的子序列
所用代码 java 判断子序列 LeetCode 392 题目链接:判断子序列 LeetCode 392 - 简单 思路 这题和之前求最长公共子序列一样。 dp[i] [j]:以i-1为结尾的字符串s 和 以j-1为结尾的字符串t 组成的相同子序列的长度 递推公式: 相等dp[i][j] d…...
【unity3D】创建TextMeshPro(TMP)中文字体(解决输入中文乱码问题)
💗 未来的游戏开发程序媛,现在的努力学习菜鸡 💦本专栏是我关于游戏开发的学习笔记 🈶本篇是unity的TMP中文输入显示乱码的解决方式 创建 TextMeshPro 中文字体遇到的问题描述解决方式Font Asset Creator 面板扩展中文字体文本遇到…...
JAVA开发(JAVA中的异常)
在java开发与代码运行过程中,我们经常会遇到需要处理异常的时候。有时候是在用编辑器写代码,点击保存的时候,编辑器就提示我们某块代码有异常,强制需要处理。有时候是我们启动,运行JAVA代码的时候的,日志里…...
lesson8-Linux多线程
Linux线程概念 线程在进程内部执行,是OS调度的基本单位OS是可以做到让进程进行资源的细粒度划分的物理内存是以4kb为单位的我们的.exe可执行程序本来就是按照地址空间的方式进行编译的页表映射 - 详细图 理解线程 线程在进程的地址空间内运行, 进程内部具有多个执行流的,而线程…...
python的django框架从入门到熟练【保姆式教学】第四篇
在前三篇博客中,我们介绍了Django的模型层、数据库迁移、视图层和URL路由。本篇博客将介绍Django的模板层,讲解如何使用模板来创建美观的Web页面。 模板层(Template) Django的模板层是Django应用程序的另一个核心组件。模板是一…...
Codeforces Round 852 (Div. 2)
A Yet Another Promotion 题意:要买n千克物品,第一天的价格为a,第二天的价格为b。第一天有促销活动,每买m千克物品,可以额外获得1千克物品。问最少花费多少可以获得至少n千克的物品。 思路:分类讨论&…...
【PTA Data Structures and Algorithms (English)】7-2 Reversing Linked List
Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K3, then you must output 3→2→1→6→5→4; if K4, you must output 4→3→2→1→5→6. Input Specif…...
Jetpack Compose 学习汇总
关于 Jetpack Compose 的学习本想只是简单的快速学习一下,结果万万没想到,竟然一下子折腾了好几个月。。。 下面将之前记录的 Jetpack Compose 相关的学习博文进行一个汇总链接整理,方便我以后自己查阅,也希望能帮到一些有正在学…...
【OpenCv】c++ 图像初级操作 | 图像灰度化
文章目录一、图像1、图像信息2、图像种类1)二值图像:2)灰度图:3)彩色图:二、图像转化1、分离彩色图三个通道2、图像灰度化处理一、图像 1、图像信息 Q:图像在计算机中怎么储存? A:…...
VIT(vision transformer)onnx模型解析
背景:transformer在CV领域的应用论文下载链接:https://arxiv.org/abs/2010.11929Pytorch实现代码: pytorch_classification/vision_transformer(太阳花的小绿豆博主实现的代码)有一些大神在研究关于CNNtransformer或者纯用transformer实现。原…...
红黑树的介绍和实现
文章目录1. 红黑树1.1 红黑树的概念1.2 红黑树的性质1.3 红黑树节点的定义1.4 红黑树的插入1.5 红黑树的验证1.6 红黑树与AVL树的比较1. 红黑树 1.1 红黑树的概念 红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以…...
C/C++每日一练(20230310)
目录 1. 用栈实现队列 ★★ 2. 单词搜索 II ★★★ 3. 直线上最多的点数 ★★★ 1. 用栈实现队列 请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push、pop、peek、empty): 实现 MyQueue 类: v…...
Go语言基础知识
常量//定义方式 const a int12;//指定变量类型 const b12;//不指定变量类型,由编译时go自动确认 const(//多行定义方式a12b23 ) //说到const,不得不得不提到的一个参数iota,初始值为0,在用const多行定义的方式中, 如果第一行定义了…...
案例06-没有复用思想的接口和sql--mybatis,spring
目录一、背景二、思路&方案问题1优化问题2优化三、总结四、升华一、背景 写这篇文章的目的是通过对没有复用思想接口的代码例子优化告诉大家,没有复用思想的代码不要写,用这种思维方式和习惯来指导我们写代码。 项目中有两处没有复用思想代码&#…...
如何将项目部署到服务器:从选择服务器到维护应用程序的全流程指南
将项目部署到服务器是一个重要的技能,对于开发人员来说,它是必不可少的。在本文中,我将介绍一些关于如何将项目部署到服务器的最佳实践。一、选择服务器在部署项目之前,你需要先选择一个适合你的服务器。如果你已经有一个可用的服…...
怎么做才能不丢消息?
现在主流的消息队列产品都提供了非常完善的消息可靠性保证机制,可以做到在消息传递的过程中,即使发生网络中断或者硬件故障,也能确保消息的可靠传递、不丢消息。 绝大部分丢消息的原因都是由于开发者不熟悉消息队列,没有正确使用…...
前端基础(十六)_数组对象
数组对象 1、创建数组 // 字面量创建const arr [1, 2, 3, 4, 5, 6]// 构造函数创建const arr2 new Array(1, 2, 3, 4, 5, 6)const arr3 Array(1, 2, 3, 4, 5, 6)2.push (从数组末尾添加元素) a.数组.push(要添加进数组的数组项) b.作用:将要添加的数组项 添加到…...
数据结构-带头双向循环链表
前言: 链表有很多种,上一章结,我复盘了单链表,这一章节,主要针对双链表的知识点进行,整理复盘,如果将链表分类的话,有很多种,我就学习的方向考察的重点,主要…...
3 问 6 步,极狐GitLab 帮助企业构建高效、安全、合规的 DevSecOps 文化
本文来源:about.gitlab.com 作者:Vanessa Wegner 译者:极狐(GitLab) 市场部内容团队 🔒 安全为何重要?此前,我们分享了: 1. 2023年DevOps发展趋势👉重磅!GitLab 提出五大…...
SPA(单页应用)知多少
单页面应用程序将所有的活动局限于一个Web页面中,在该Web页面初始化时加载相应的HTML、JavaScript 和 CSS。一旦页面加载完成,单页面应用不会因为用户的操作而进行页面的重新加载或跳转。取而代之的是利用 JavaScript 动态的变换HTML的内容,从…...
大语言模型应用落地:从RAG到工作流,IT企业智能转型全攻略!
引言检索增强生成(RAG)微调(Fine-Tuning)智能体(Agents)工作流与流程编排(Workflow)企业落地策略与阶段规划落地难点与最佳实践建议结语引言大语言模型(LLM)技…...
s2-pro音色复用效果实测:不同参考音频时长(3s/10s/30s)对合成质量影响
s2-pro音色复用效果实测:不同参考音频时长(3s/10s/30s)对合成质量影响 1. 引言 s2-pro作为Fish Audio开源的专业级语音合成模型镜像,其音色复用功能在实际应用中表现如何?本文将针对一个关键问题展开实测:…...
Java全栈开发面试实战:从基础到进阶的深度解析
Java全栈开发面试实战:从基础到进阶的深度解析 面试官与应聘者的对话 面试官(李明):你好,我是李明,负责这次技术面试。很高兴见到你,先简单介绍一下你自己吧。 应聘者(张晨ÿ…...
终极指南:如何在Foobar2000中安装和配置ESLyric逐字歌词源
终极指南:如何在Foobar2000中安装和配置ESLyric逐字歌词源 【免费下载链接】ESLyric-LyricsSource Advanced lyrics source for ESLyric in foobar2000 项目地址: https://gitcode.com/gh_mirrors/es/ESLyric-LyricsSource 想要在Foobar2000中享受精准的逐字…...
小白程序员必看:收藏这份智能体学习指南,轻松入门大模型时代
智能体(Agent)是人工智能领域的重要概念,能够感知环境并自主行动达成目标。文章从自动驾驶、阿尔法狗等实例引入,阐述了智能体的定义和运作机制。传统智能体发展历经反射、目标导向、模型反射、效用和自主学习等阶段。大模型的出现…...
泛微E9流程表单转PDF/HTML实战:手把手教你集成档案系统(附完整代码)
泛微E9流程表单转PDF/HTML全流程开发指南:从原理到实战 在企业管理数字化转型的浪潮中,OA系统与档案系统的无缝对接已成为提升组织效能的刚需。作为国内主流的协同办公平台,泛微E9的流程表单承载着企业核心业务流程数据,如何将这些…...
NaViL-9B部署案例:中小企业用双24GB显卡替代A100实现降本增效
NaViL-9B部署案例:中小企业用双24GB显卡替代A100实现降本增效 1. 项目背景与价值 在AI大模型应用日益普及的今天,中小企业面临着高昂的硬件投入成本。传统部署方案通常需要A100等高端显卡,单卡价格动辄数万元,让许多企业望而却步…...
基于springboot的旅游景点门票信息系统设计与实现-vue
目录 技术栈选择系统模块划分数据库设计接口设计规范前端实现要点安全措施部署方案开发流程测试计划扩展功能预留 项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作 技术栈选择 后端采用Spring Boot框架,提供RESTful…...
基于springboot框架的校园外卖管理系统的设计与实现
目录需求分析与功能规划技术选型与架构设计数据库设计与建模核心功能实现系统集成与测试部署与运维优化与扩展项目技术支持源码获取详细视频演示 :文章底部获取博主联系方式!同行可合作需求分析与功能规划 明确校园外卖管理系统的核心需求,包…...
基于Vue的沧交食堂食品监管系统[vue]-计算机毕业设计源码+LW文档
摘要:本文阐述了一个基于Vue框架开发的沧交食堂食品监管系统。该系统旨在借助现代Web技术,强化对沧交食堂食品安全的监管力度,提升监管效率与质量。系统涵盖了系统用户管理、新闻数据管理、食品相关业务管理以及评论管理等多方面功能。文章详…...
