当前位置: 首页 > news >正文

代码随想录算法训练营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.不同的子序列

做题

无思路。

看文章

这道题很难,题解也看了很久。
动规五部曲:

  1. 确定dp数组(dp table)以及下标的含义。

    dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。

  2. 确定递推公式。这一类问题,基本是要分析两种情况:

    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]。

  3. 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。

  4. 确定遍历顺序。

    外部遍历 s,内部遍历 t。

  5. 举例推导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; // 如果矩阵为空&#xff0c;则直接返回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智能体介绍 二、智能体创建三、体验与总结 一、文心智能体平台 文心智能体平台是百度推出的基于文心大模型的智能体&#xff08;Agent&#xff09;平台&#xff0c;支持广大开发者根据自身行业领域、应用场景&#xff0c;选取不同类…...

AppInventor2 表格布局的外面的黑框怎么去掉?

问&#xff1a;表格布局的外面的黑框怎么去掉啊&#xff1f; 答&#xff1a;这个黑框是界面设计的布局位置示意&#xff0c;实际 App 测试时并没有框。 来源&#xff1a;AppInventor2 表格布局的外面的黑框怎么去掉&#xff1f; - App应用开发 - 清泛IT社区&#xff0c;为创新…...

爬楼梯(进阶版)

思路&#xff1a; 没什么难的&#xff0c;就是一个排序的01背包问题&#xff0c;秒了 #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部分事件 添加点击事件 添加点击事件&#xff1a; let options {tooltip: {},xAxis: {type: "category",data: ["d1", "d2", "d3", "d4"],},yAxis: {},series: [{type: "line",data: d1,},{type: &qu…...

备受推崇的公司文件加密文件推荐榜单

迄今为止&#xff0c;加密依然是最有效的用于保护数据、通讯安全的手段之一 在数字化时代&#xff0c;文件加密软件成为了保护个人和企业数据安全的重要工具。随着技术的不断进步&#xff0c;市场上涌现出了众多优秀的文件加密软件。 以下十款文件加密软件因其出色的性能、易…...

QT——QSlider实现,QT滑动控件的使用

目录 简介滑动块调节两种方法滑动条触发信号量理想滑动块运用&#xff08;参考&#xff09; 简介 QT中滑动条的控件叫QSlider&#xff0c;继承自QAbstractSlider类。 主要用途是通过滑块的滑动的方式在一定范围内调节某个值。根据调节的后得到的结果去执行一些处理&#xff0c…...

【网络协议Http】Http中get,post,put,delete区别

Http协议 超文本传输协议&#xff08;Hypertext Transfer Protocol&#xff0c;HTTP&#xff09;是一个简单的请求-响应协议&#xff0c;它通常运行在TCP之上。 【参考】 GET && POST 对比 关于tcp数据包&#xff1a;对于GET方式的请求&#xff0c;浏览器会把http hea…...

软硬中断区别,磁盘块、扇区、页区别与之间的关系

软硬中断&#xff1a; 软中断是执行中断指令产生的&#xff0c;而硬中断是由外设引发的。 硬中断的中断号是由中断控制器提供的&#xff0c;软中断的中断号由指令直接指出&#xff0c;无需使用中断控制器。 硬中断是可屏蔽的&#xff0c;软中断不可屏蔽。 硬中断处理程序要…...

在线思维导图编辑!3个AI思维导图生成软件推荐!

思维导图&#xff0c;一种以创新为驱动的视觉化思考工具&#xff0c;已经渗透到我们日常生活和工作的各个角落。当我们需要整理思绪、规划项目或者梳理信息时&#xff0c;思维导图总能提供极大的帮助。 近些年随着云服务等基础设施的完善&#xff0c;我们可以看到越来越多提供…...

使用 Ubuntu + Docker + Vaultwarden + Tailscale 自建密码管理器

使用 Ubuntu Docker Vaultwarden Tailscale 自建密码管理器 先决条件 一台运行 Ubuntu 系统的服务器。可以是云提供商的 VPS、家庭网络中的树莓派、或者 Windows 电脑上的虚拟机等等 一个 Tailscale 账户。如果还没有 Tailscale 账户&#xff0c;可以通过此链接迅速创建一个…...

YOLOv7添加注意力机制和各种改进模块

YOLOv7添加注意力机制和各种改进模块代码免费下载&#xff1a;完整代码 添加的部分模块代码&#xff1a; ########CBAM class ChannelAttentionModule(nn.Module):def __init__(self, c1, reduction16):super(ChannelAttentionModule, self).__init__()mid_channel c1 // red…...

【OpenGL第一个程序】

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、OpenGL第一个程序 前言 本文介绍了OpenGL入门的第一个程序&#xff0c;有详细的注释&#xff0c;便于大家理解其中的逻辑。 一、OpenGL第一个程序 #inclu…...

GPT-4O神器来袭!自动生成Figma设计稿,移动端开发瞬间加速!

2024年5月29日- 近日&#xff0c;一款基于GPT-4O技术的创新工具成功实现根据产品需求文档&#xff08;PRD&#xff09;自动生成Figma设计稿的功能&#xff0c;为移动端应用开发者带来革命性的便捷。据悉&#xff0c;该功能主要针对移动端应用进行优化&#xff0c;并支持使用高质…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

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

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; 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深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!

一、引言 在数据驱动的背景下&#xff0c;知识图谱凭借其高效的信息组织能力&#xff0c;正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合&#xff0c;探讨知识图谱开发的实现细节&#xff0c;帮助读者掌握该技术栈在实际项目中的落地方法。 …...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

蓝桥杯3498 01串的熵

问题描述 对于一个长度为 23333333的 01 串, 如果其信息熵为 11625907.5798&#xff0c; 且 0 出现次数比 1 少, 那么这个 01 串中 0 出现了多少次? #include<iostream> #include<cmath> using namespace std;int n 23333333;int main() {//枚举 0 出现的次数//因…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...