当前位置: 首页 > 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;并支持使用高质…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

sshd代码修改banner

sshd服务连接之后会收到字符串&#xff1a; SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢&#xff1f; 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头&#xff0c…...