代码随想录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,提升域名管理的效率
在互联网时代,域名管理是网站运营中非常重要的一环。通过域名,我们能够轻松访问和识别不同的网站。然而,域名的注册和管理也是一项复杂的任务,特别是对于大规模拥有许多域名的企业来说。为了提升域名管理的效率,我们可…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)
文章目录 1.什么是Redis?2.为什么要使用redis作为mysql的缓存?3.什么是缓存雪崩、缓存穿透、缓存击穿?3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
大数据学习(132)-HIve数据分析
🍋🍋大数据学习🍋🍋 🔥系列专栏: 👑哲学语录: 用力所能及,改变世界。 💖如果觉得博主的文章还不错的话,请点赞👍收藏⭐️留言Ǵ…...

AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...

push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

uniapp 开发ios, xcode 提交app store connect 和 testflight内测
uniapp 中配置 配置manifest 文档:manifest.json 应用配置 | uni-app官网 hbuilderx中本地打包 下载IOS最新SDK 开发环境 | uni小程序SDK hbulderx 版本号:4.66 对应的sdk版本 4.66 两者必须一致 本地打包的资源导入到SDK 导入资源 | uni小程序SDK …...