代码随想录算法训练营Day54 | 392.判断子序列、115.不同的子序列 | Python | 个人记录向
本文目录
- 392.判断子序列
- 做题
- 看文章
- 115.不同的子序列
- 做题
- 看文章
- 以往忽略的知识点小结
- 个人体会
392.判断子序列
代码随想录:392.判断子序列
Leetcode:392.判断子序列
做题
借鉴Day53中1143.最长公共子序列的思路,最后改一下判断逻辑即可。
class Solution:def isSubsequence(self, s: str, t: str) -> bool:dp = [[0] * (len(s)+1) for _ in range(len(t)+1)]for i in range(1, len(t)+1):for j in range(1, len(s)+1):if t[i-1] == s[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i][j-1], dp[i-1][j])if dp[len(t)][len(s)] == len(s):return Trueelse:return False
时间复杂度:O(n × m)
空间复杂度:O(n × m)
看文章
思路一致。
115.不同的子序列
代码随想录:115.不同的子序列
Leetcode:115.不同的子序列
做题
无思路。
看文章
这道题很难,题解也看了很久。
动规五部曲:
-
确定dp数组(dp table)以及下标的含义。
dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
-
确定递推公式。这一类问题,基本是要分析两种情况:
s[i - 1] 与 t[j - 1]相等,dp[i][j]可以有两部分组成。
一部分是用s[i - 1]来匹配,那么个数为dp[i - 1][j - 1]。即不需要考虑当前s子串和t子串的最后一位字母,所以只需要 dp[i-1][j-1]。
另一部分是不用s[i - 1]来匹配,个数为dp[i - 1][j],相当于复制直接的结果。s[i - 1] 与 t[j - 1] 不相等,dp[i][j]只有一部分组成,不用s[i - 1]来匹配(就是模拟在s中删除这个元素),即:dp[i - 1][j]。
-
dp数组如何初始化。
dp[i][0]:以i-1为结尾的s可以随便删除元素,出现空字符串的个数。那么dp[i][0]一定都是1,因为也就是把以i-1为结尾的s,删除所有元素,出现空字符串的个数就是1。
dp[0][j]:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数。那么dp[0][j]一定都是0,s如论如何也变成不了t。
-
确定遍历顺序。
外部遍历 s,内部遍历 t。
-
举例推导dp数组。
代码如下:
class Solution:def numDistinct(self, s: str, t: str) -> int:dp = [[0] * (len(t)+1) for _ in range(len(s)+1)]for i in range(len(s)+1):dp[i][0] = 1for i in range(1, len(s)+1):for j in range(1, len(t)+1):if s[i-1] == t[j-1]:dp[i][j] = dp[i-1][j-1] + dp[i-1][j]else:dp[i][j] = dp[i-1][j]return dp[len(s)][len(t)]
以往忽略的知识点小结
- 回到动规五部曲的基本思路,特别是dp数组的含义
个人体会
完成时间:1h30min。
心得:115.不同的子序列比较难,看了好久,需要回归到动规五部曲的基本思路,特别是dp数组的含义。
相关文章:
代码随想录算法训练营Day54 | 392.判断子序列、115.不同的子序列 | Python | 个人记录向
本文目录 392.判断子序列做题看文章 115.不同的子序列做题看文章 以往忽略的知识点小结个人体会 392.判断子序列 代码随想录:392.判断子序列 Leetcode:392.判断子序列 做题 借鉴Day53中1143.最长公共子序列的思路,最后改一下判断逻辑即可。…...
利用oracle默认事务隔离级别(提交读)提升多表联查速度
利用oracle默认事务隔离级别(提交读)提升查询速度) 背景介绍: 数据量大查询缓慢,添加太多条件,使用IN走了全表查询导致查询速度缓慢。 解决方案: 版本一: 新建临时表,在查询是将数据插入到临时表中&#…...
B/S架构+java语言+Mysqladr数 据 库ADR药物不良反应监测系统源码 ADR药物不良反应监测系统有哪些作用?
B/S架构+java语言+Mysqladr数 据 库ADR药物不良反应监测系统源码 ADR药物不良反应监测系统有哪些作用? 药物不良反应(ADR)是指在合格药物以正常用量和用法用于预防、诊断、治疗疾病或调节生理功能时所发生的意外的、与防治目的无关的、不利或…...
Matlab中% note that Wilkinson notation (‘L1~L4~1‘) is used to specify the model
fitrm 函数的输入参数不正确,似乎出错的地方是在定义 fitrm 对象时使用了不正确的参数。 fitrm 函数的语法是这样的: rm fitrm(tbl, model, WithinDesign, withinDesign) 其中: - tbl 是一个表格,包含了待分析的数据。 - mod…...
测试测试测试
一分钟速览新闻点! 京东前副总裁蔡磊回应被指装病:没有时间、精力和能力应对 百度沈抖:主力模型免费的原因很朴素,希望大家别再天天拉表格比价格 蚂蚁集团CTO何征宇:蚂蚁一直在努力优化和提高AI的可靠性、经济性和易…...
动态规划专题
leecode 221 class Solution { public:int maximalSquare(vector<vector<char>>& matrix) {int n matrix.size();if (n 0) return 0; // 如果矩阵为空,则直接返回0 int m matrix[0].size();vector<vector<int>> ans(n, vector<i…...
.net8.0与halcon编程环境构建
1.安装vs2022 2.安装h-12.0.exe ,不要勾选复选框 3.vs2022新建wpf应用程序 4.依赖项添加项目应用,选择halcondotnet.dll 5.安装System.Drawing 安装 HalconDotNet 安装 Rti.HDevEngineDotNet 在工具箱 空白处右键 应用halcon.dll WPF控件也应用halcon.dll 6.xaml申明hal…...
文心智能体平台:快来创建你的Java学习小助理,全方位辅助学习
文章目录 一、文心智能体平台1.1平台介绍1.2智能体介绍 二、智能体创建三、体验与总结 一、文心智能体平台 文心智能体平台是百度推出的基于文心大模型的智能体(Agent)平台,支持广大开发者根据自身行业领域、应用场景,选取不同类…...
AppInventor2 表格布局的外面的黑框怎么去掉?
问:表格布局的外面的黑框怎么去掉啊? 答:这个黑框是界面设计的布局位置示意,实际 App 测试时并没有框。 来源:AppInventor2 表格布局的外面的黑框怎么去掉? - App应用开发 - 清泛IT社区,为创新…...
爬楼梯(进阶版)
思路: 没什么难的,就是一个排序的01背包问题,秒了 #include<bits/stdc.h> using namespace std;int n,m; int main(){cin>>n>>m;vector<int>dp(2000,0);dp[0]1;for(int i0;i<n;i){for(int j1;j<m;j){if(i>…...
echarts-事件
echarts部分事件 添加点击事件 添加点击事件: let options {tooltip: {},xAxis: {type: "category",data: ["d1", "d2", "d3", "d4"],},yAxis: {},series: [{type: "line",data: d1,},{type: &qu…...
备受推崇的公司文件加密文件推荐榜单
迄今为止,加密依然是最有效的用于保护数据、通讯安全的手段之一 在数字化时代,文件加密软件成为了保护个人和企业数据安全的重要工具。随着技术的不断进步,市场上涌现出了众多优秀的文件加密软件。 以下十款文件加密软件因其出色的性能、易…...
QT——QSlider实现,QT滑动控件的使用
目录 简介滑动块调节两种方法滑动条触发信号量理想滑动块运用(参考) 简介 QT中滑动条的控件叫QSlider,继承自QAbstractSlider类。 主要用途是通过滑块的滑动的方式在一定范围内调节某个值。根据调节的后得到的结果去执行一些处理,…...
【网络协议Http】Http中get,post,put,delete区别
Http协议 超文本传输协议(Hypertext Transfer Protocol,HTTP)是一个简单的请求-响应协议,它通常运行在TCP之上。 【参考】 GET && POST 对比 关于tcp数据包:对于GET方式的请求,浏览器会把http hea…...
软硬中断区别,磁盘块、扇区、页区别与之间的关系
软硬中断: 软中断是执行中断指令产生的,而硬中断是由外设引发的。 硬中断的中断号是由中断控制器提供的,软中断的中断号由指令直接指出,无需使用中断控制器。 硬中断是可屏蔽的,软中断不可屏蔽。 硬中断处理程序要…...
在线思维导图编辑!3个AI思维导图生成软件推荐!
思维导图,一种以创新为驱动的视觉化思考工具,已经渗透到我们日常生活和工作的各个角落。当我们需要整理思绪、规划项目或者梳理信息时,思维导图总能提供极大的帮助。 近些年随着云服务等基础设施的完善,我们可以看到越来越多提供…...
使用 Ubuntu + Docker + Vaultwarden + Tailscale 自建密码管理器
使用 Ubuntu Docker Vaultwarden Tailscale 自建密码管理器 先决条件 一台运行 Ubuntu 系统的服务器。可以是云提供商的 VPS、家庭网络中的树莓派、或者 Windows 电脑上的虚拟机等等 一个 Tailscale 账户。如果还没有 Tailscale 账户,可以通过此链接迅速创建一个…...
YOLOv7添加注意力机制和各种改进模块
YOLOv7添加注意力机制和各种改进模块代码免费下载:完整代码 添加的部分模块代码: ########CBAM class ChannelAttentionModule(nn.Module):def __init__(self, c1, reduction16):super(ChannelAttentionModule, self).__init__()mid_channel c1 // red…...
【OpenGL第一个程序】
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、OpenGL第一个程序 前言 本文介绍了OpenGL入门的第一个程序,有详细的注释,便于大家理解其中的逻辑。 一、OpenGL第一个程序 #inclu…...
GPT-4O神器来袭!自动生成Figma设计稿,移动端开发瞬间加速!
2024年5月29日- 近日,一款基于GPT-4O技术的创新工具成功实现根据产品需求文档(PRD)自动生成Figma设计稿的功能,为移动端应用开发者带来革命性的便捷。据悉,该功能主要针对移动端应用进行优化,并支持使用高质…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
令牌桶 滑动窗口->限流 分布式信号量->限并发的原理 lua脚本分析介绍
文章目录 前言限流限制并发的实际理解限流令牌桶代码实现结果分析令牌桶lua的模拟实现原理总结: 滑动窗口代码实现结果分析lua脚本原理解析 限并发分布式信号量代码实现结果分析lua脚本实现原理 双注解去实现限流 并发结果分析: 实际业务去理解体会统一注…...
土地利用/土地覆盖遥感解译与基于CLUE模型未来变化情景预测;从基础到高级,涵盖ArcGIS数据处理、ENVI遥感解译与CLUE模型情景模拟等
🔍 土地利用/土地覆盖数据是生态、环境和气象等诸多领域模型的关键输入参数。通过遥感影像解译技术,可以精准获取历史或当前任何一个区域的土地利用/土地覆盖情况。这些数据不仅能够用于评估区域生态环境的变化趋势,还能有效评价重大生态工程…...
【JavaSE】绘图与事件入门学习笔记
-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角,以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向,距离坐标原点x个像素;第二个是y坐标,表示当前位置为垂直方向,距离坐标原点y个像素。 坐标体系-像素 …...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
