代码随想录Day58
392.判断子序列
题目:392. 判断子序列 - 力扣(LeetCode)
思路:定义重合数记录s与t的比对情况,挨个取出t的字符,与s的字符进行比较,如果相同,重合数就加1,跳到s的下一个字符进行比较,最后判断重合数是否为s字符串长度
尝试(暴力AC)
class Solution {public boolean isSubsequence(String s, String t) {if(s.length()==0) return true;int count = 0;for(int i =0; i<t.length() && count<s.length(); i++){if(s.charAt(count) == t.charAt(i)){count++;}}return count==s.length();}
}
答案
class Solution {public boolean isSubsequence(String s, String t) {int length1 = s.length(); int length2 = t.length();int[][] dp = new int[length1+1][length2+1];for(int i = 1; i <= length1; i++){for(int j = 1; j <= length2; 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];}}}if(dp[length1][length2] == length1){return true;}else{return false;}}
}
小结
dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]。

115.不同的子序列
题目:115. 不同的子序列 - 力扣(LeetCode)
思路:想不到dp数组要如何定义,果断放弃
答案
class Solution {public int numDistinct(String s, String t) {int[][] dp = new int[s.length() + 1][t.length() + 1];for (int i = 0; i < s.length() + 1; i++) {dp[i][0] = 1;}for (int i = 1; i < s.length() + 1; i++) {for (int j = 1; j < t.length() + 1; j++) {if (s.charAt(i - 1) == t.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];}else{dp[i][j] = dp[i - 1][j];}}}return dp[s.length()][t.length()];}
}
小结
dp数组定义跟上一道题类似:dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
dp数组的初始化,根据递推公式来看,是从左上角往下推,所以第一行和第一列一定要初始化

583.两个字符串的删除操作
题目:583. 两个字符串的删除操作 - 力扣(LeetCode)
思路:怎么感觉就是求最长公共子序列
尝试(还是在求最长公共子序列)
class Solution {public int minDistance(String word1, String word2) {char[] char1 = word1.toCharArray();char[] char2 = word2.toCharArray();int[][] dp = new int[word1.length()+1][word2.length()+1];for(int i=1; i<=word1.length(); i++ ){for(int j = 1; j<=word2.length(); j++){if(char1[i-1] == char2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;}else{dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);}}}return word1.length()+word2.length() - 2*dp[word1.length()][word2.length()];}
}
答案
// dp数组中存储需要删除的字符个数
class Solution {public int minDistance(String word1, String word2) {int[][] dp = new int[word1.length() + 1][word2.length() + 1];for (int i = 0; i < word1.length() + 1; i++) dp[i][0] = i;for (int j = 0; j < word2.length() + 1; j++) dp[0][j] = j;for (int i = 1; i < word1.length() + 1; i++) {for (int j = 1; j < word2.length() + 1; j++) {if (word1.charAt(i - 1) == word2.charAt(j - 1)) {dp[i][j] = dp[i - 1][j - 1];}else{dp[i][j] = Math.min(dp[i - 1][j - 1] + 2,Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1));}}}return dp[word1.length()][word2.length()];}
小结
dp[i][j]:以i-1为结尾的字符串word1,和以j-1位结尾的字符串word2,想要达到相等,所需要删除元素的最少次数。
相关文章:
代码随想录Day58
392.判断子序列 题目:392. 判断子序列 - 力扣(LeetCode) 思路:定义重合数记录s与t的比对情况,挨个取出t的字符,与s的字符进行比较,如果相同,重合数就加1,跳到s的下一个字…...
Android Verified Boot (AVB) 与 dm-verity 之间的关系、相同点与差异点
标签: AVB; dm-verity ;Android Android Verified Boot (AVB) 与 dm-verity 之间的关系、相同点与差异点 概述 Android Verified Boot (AVB) 和 dm-verity 是 Android 操作系统中用于确保设备启动过程和运行时数据完整性的两个重要技术。尽管它们有着不同的实现和侧重点,…...
C++学习笔记“类和对象”:多态;
目录 4.7 多态 4.7.1 多态的基本概念 4.7.2 多态案例--计算器类 4.7.3 纯虚函数和抽象类 4.7.4 多态案例二 - 制作饮品 4.7.5 虚析构和纯虚析构 4.7.6 多态案例三-电脑组装 4.7 多态 4.7.1 多态的基本概念 多态是C面向对象三大特性之一 多态分为两类 静志多态: 函数…...
QT Udp广播实现设备发现
测试环境 本文选用pc1作为客户端,pc2,以及一台虚拟机作为服务端。 pc1,pc2(客户端): 虚拟机(服务端): 客户端 原理:客户端通过发送广播消息信息到ip:255.255.255.255(QHostAddress::Broadcast),局域网…...
PyTorch 统计属性-Tensor基本操作
最小 min, 最大 max, 均值 mean,累加 sum,累乘 prod … >>> a torch.arange(0,8).view(2,4).float() >>> a tensor([[0., 1., 2., 3.],[4., 5., 6., 7.]])>>> a.min() ## 最小值:tensor(0.) >>> a.ma…...
波拉西亚战记加速器 台服波拉西亚战记免费加速器
波拉西亚战记是一款新上线的MMORPG游戏,游戏内我们有多个角色职业可以选择,可以体验不同的战斗流派玩法,开放式的地图设计,玩家可以自由的进行探索冒险,寻找各种物资。各种随机事件可以触发,让玩家的冒险过…...
Mocha + Chai 测试环境配置,支持 ES6 语法
下面是一个完整的 Mocha Chai 测试环境配置,支持 ES6 语法。我们将使用 Babel 来转译 ES6 代码。 步骤一:初始化项目 首先,在项目目录中运行以下命令来初始化一个新的 Node.js 项目: npm init -y步骤二:安装必要的…...
华为网络设备攻击防范
畸形报文攻击防范 攻击行为 畸形报文攻击是通过向交换机发送有缺陷的IP报文,使得交换机在处理这样的IP包时会出现崩溃,给交换机带来损失。 畸形报文攻击主要有如下几种: 没有IP载荷的泛洪攻击 IGMP空报文攻击 LAND攻击 Smurf攻击 TCP标…...
RK3588开发笔记-100M网口自协商成1000M网口
目录 前言 一、问题描述 二、原理图连接 三、解决方法 总结 前言 在进行RK3588开发过程中,遇到一个令人困惑的问题:在使用RTL8211F-CG phy芯片出来的100M网口在自协商后连接速率变成了1000M。这篇博客将详细记录这个问题的产生、排查过程以及最终的解决方案,希望能对遇到…...
Python第二语言(十三、PySpark实战)
目录 1.开篇 2. PySpark介绍 3. PySpark基础准备 3.1 PySpark安装 3.2 掌握PySpark执行环境入口对象的构建 3.3 理解PySpark的编程模型 4. PySpark:RDD对象数据输入 4.1 RDD对象概念:PySpark支持多种数据的输入,完成后会返回RDD类的对…...
《阅读的方法》读后感——超越期待的收获
当我翻开这本书的扉页时,未曾料到它会给我带来如此深远的启示和收获。依照推荐序言中的指引,我随意翻阅、精心选读,每一次都如同打开一扇新的窗户,让我窥见不同领域的智慧和美好。 等地铁时、临睡前随便读点什么,有什么…...
算法训练营第五十八天 | LeetCode 392 判断子序列、卡码网模拟美团笔试第一、二、三题(300/500有待提高)
卡码网图论更新了可以去看看,模拟笔试第四题就是深搜/广搜还不太会 LeetCode 392 判断子序列 其实就是最长公共子序列翻版 代码如下: class Solution {public boolean isSubsequence(String s, String t) {int[][] dp new int[s.length() 1][t.lengt…...
Sa-Token鉴权与网关服务实现
纠错: 在上一部分里我完成了微服务框架的初步实现,但是先说一下之前有一个错误,就是依赖部分 上次的学习中我在总的父模块下引入了spring-boot-dependencies(版本控制)我以为在子模块下就不需要再引用了,…...
企事业单位安全生产月活动怎样向媒体投稿?
作为一名单位的信息宣传员,我肩负着将每一次重要活动的精彩瞬间转化为文字,向外界传递我们单位声音的重任。初入此行时,我满怀热情,坚信通过传统的方式——电子邮件投稿,能够有效地将我们的故事传播出去。然而,现实却给我上了生动的一课。 记得在筹备“安全生产月”活动的宣传时…...
MySQL8.0默认TCP端口介绍
1、本文内容 选择题TCP/IPMySQL 8.0 的默认TCP端口show variables查看总结 2、选择题 A、3306 B、33060 C、33062 D、33063 3、TCP/IP TCP/IP(Transmission Control Protocol/Internet Protocol,传输控制协议/网际协议)是指能够在多个不同…...
Javaweb避坑指北(持续更新)
内容较多可按CtrlF搜索 0.目录 1.获取插入数据后自增长主键的值 2.Controller中返回给ajax请求字符串/json会跳转到xxx.jsp 3.ajax请求获得的json无法解析 4.在Controller中使用ServletFileUpload获取的上传文件为null 5.莫名其妙报service和dao里方法的错误 6.ajax请求拿…...
Web前端知道:深入探索与无尽挑战
Web前端知道:深入探索与无尽挑战 Web前端,这个看似简单却实则深不可测的领域,一直以来都吸引着无数开发者投入其中。在这个充满未知与可能的世界里,我们既是探索者,也是挑战者。本文将从四个方面、五个方面、六个方面…...
QT调用vs2019生成的c++动态库
QT调用vs2019生成的c动态库 dll库的创建方法: VS2019创建c动态链接库dll与调用方法-CSDN博客 加减法示范: 头文件 // 下列 ifdef 块是创建使从 DLL 导出更简单的 // 宏的标准方法。此 DLL 中的所有文件都是用命令行上定义的 DLL3_EXPORTS // 符号编…...
C语言TC中有⼏个画线函数?怎么使⽤?
一、问题 C语⾔中画线的函数好像不⽌ line( )⼀个,那么除了 line( ) ,还有哪些画线函数?怎么使⽤? 二、解答 TC中有3种画线的函数,共语法格式如下。 void far line(int x0, int y0, int xl, int y1); void far linet…...
掌握WhoisAPI,提升域名管理的效率
在互联网时代,域名管理是网站运营中非常重要的一环。通过域名,我们能够轻松访问和识别不同的网站。然而,域名的注册和管理也是一项复杂的任务,特别是对于大规模拥有许多域名的企业来说。为了提升域名管理的效率,我们可…...
铭豹扩展坞 USB转网口 突然无法识别解决方法
当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)
LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 题目描述解题思路Java代码 题目描述 题目链接:LeetCode 3309. 连接二进制表示可形成的最大数值(中等) 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...
解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
