代码随想录算法训练营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设计稿的功能,为移动端应用开发者带来革命性的便捷。据悉,该功能主要针对移动端应用进行优化,并支持使用高质…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
Python爬虫实战:研究feedparser库相关技术
1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验
系列回顾: 在上一篇中,我们成功地为应用集成了数据库,并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了!但是,如果你仔细审视那些 API,会发现它们还很“粗糙”:有…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理
引言 Bitmap(位图)是Android应用内存占用的“头号杀手”。一张1080P(1920x1080)的图片以ARGB_8888格式加载时,内存占用高达8MB(192010804字节)。据统计,超过60%的应用OOM崩溃与Bitm…...

蓝桥杯3498 01串的熵
问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798, 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...