代码随想录第58天(动态规划):● 392.判断子序列 ● 115.不同的子序列
一、判断子序列
题目描述:

思路和想法:
这道题目还是最长公共子序列的拓展,只是这里进行删除的一定是t字符串,当不相等时,dp[i][j] = dp[i][j - 1];其余基本一致。当最长公共子序列个数等s.size()时,返回true;● 1143.最长公共子序列
#include<string>
#include<vector>
using namespace std;class Solution {
public:bool isSubsequence(string s, string t) {if(s.size() == 0) return true;if(s.size() > t.size()) return false;vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1,0));for (int i = 1; i <= s.size(); i++){for (int j = 1; j <= t.size(); j++){if(s[i - 1] == t[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}else{//删除元素一定是t字符串dp[i][j] = dp[i][j - 1];}if(dp[i][j] == s.size()) return true;}}return false;}
};
二、不同的子序列
题目描述:

思路和想法:
(1)dp[i][j] : 以i - 1为结尾的s中有j - 1为尾的t的个数。
(2)当(s[i - 1] == j[i - 1])时,dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];当(s[i - 1] != j[i - 1])时,dp[i][j] = dp[i - 1][j]。
这里要注意dp数组的定义:
(1)vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1,0));会出现溢出的情况

(2) vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1,0));
#include<vector>
#include<string>
using namespace std;class Solution {
public:int numDistinct(string s, string t) {if(s.size() < t.size()) return 0;vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1,0));//第一行和第一列初始化for (int i = 0; i < s.size(); i++) dp[i][0] = 1; for (int j = 1; j < t.size(); j++) dp[0][j] = 0; for (int i = 1; i <= s.size(); i++){for (int j = 1; j <= t.size(); j++){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[s.size()][t.size()]; }
};
相关文章:
代码随想录第58天(动态规划):● 392.判断子序列 ● 115.不同的子序列
一、判断子序列 题目描述: 思路和想法: 这道题目还是最长公共子序列的拓展,只是这里进行删除的一定是t字符串,当不相等时,dp[i][j] dp[i][j - 1];其余基本一致。当最长公共子序列个数等s.size()时&#x…...
代码随想录第55天(动态规划):● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费
一、最佳买卖股票时机含冷冻期 题目描述: 思路和想法: 这道题相较于之前的题目,注重对状态的分析,这里分为四个状态。 (1)状态一,买入状态 dp[i][0] 操作一:前一天就是持有状态(状…...
字符串装换整数(atoi)-力扣8-java
一、题目描述请你来实现一个 myAtoi(string s) 函数,使其能将字符串转换成一个 32 位有符号整数(类似 C/C 中的 atoi 函数)。函数 myAtoi(string s) 的算法如下:读入字符串并丢弃无用的前导空格检查下一个字符(假设还未…...
毕业5年,从月薪3000到年薪40w,我掌握了那些核心技能?(建议收藏)
大家好,我是静静~~是一枚一线大厂的测试开发工程师很多读者私信问我,自己时间不短了,随着工作年限的不断增长,感觉自己的技术水平与自己的工作年限严重不符。想跳槽出去换个新环境吧,又感觉自己的能力达不到心仪公司的…...
C++中的并行与并发
1.1 并行基础std::thread 用于创建一个执行的线程实例,所以它是一切并发编程的基础,使用时需要包含 <thread> 头文件, 它提供了很多基本的线程操作,例如 get_id() 来获取所创建线程的线程 ID,使用 join() 来加入…...
h2database源码解析-如何更新一条行记录
这里的更新包括两种操作:删、改。更新操作涉及的内容在其他文章里面已经做过介绍了,本文主要是介绍更新的代码流程,以了解更新操作都做了哪些事情。如果有未介绍过的知识点会详细介绍。 目录改(update)如何判读是否加了行锁删(delete)改(upda…...
FyListen——生命周期监听器(设计原理之理解生命周期)
FyListen——生命周期监听器(设计原理之理解生命周期) FyListen 的核心原理有两个: 通过子Fragment对Activity、Fragment进行生命周期监听Java8 接口特性 default 1. 什么是上下文Context 这是一个装饰器模式, ContextImpl 是 …...
Element UI框架学习篇(六)
Element UI框架学习篇(六) 1 删除数据 1.1 前台核心函数 1.1.1 elementUI中的消息提示框语法 //①其中type类型和el-button中的type类型是一致的,有info灰色,success绿色,danger红色,warning黄色,primary蓝色 //②message是你所要填写的提示信息 //③建议都用,因为比双引号…...
Python如何安装模块,python模块安装失败的原因以及解决办法
前言 今天来给刚开始学习python的朋友讲解一下 如何安装python模块, python模块安装失败的原因以及解决办法 很多朋友拿到代码之后,就开始复制粘贴 --> 然后右键进行运行 结果就是报错说 没有这个模块 得安装啥的 Python模块安装 一. 打开命令提示符 win …...
《NFL橄榄球》:洛杉矶闪电·橄榄1号位
洛杉矶闪电(英语:Los Angeles Chargers),又译“洛杉磯衝鋒者”。是一支位于加利福尼亚州洛杉矶郡英格尔伍德的职业美式橄榄球球队,现为美国橄榄球联合会西区成员之一。该队曾于1961年搬迁到圣地亚哥而改叫圣地亚哥电光…...
4.7 Python设置代码格式
随着你编写的程序越来越长,有必要了解一些代码格式设置约定。请花时让你的代码尽可能易于阅读;让代码易于阅读有助于你掌握程序是做什么的,也可以帮助他人理解你编写的代码。为确保所有人编写的代码的结构都大致一致,Python程序员都遵循一些格…...
Zabbix 构建监控告警平台(五)
Zabbix 自动发现Zabbix 自动注册1.Zabbix 自动发现 1.1前言 为了满足监控企业成千上万台服务器,因此我们需要使用Zabbix批量监控来实现。自动发现和自动注册。 1.2zabbix-server (一)1、创建自动发现规则 在“配置”->“自动发现”->“…...
2023关键词:挑战
未失踪人口回归… 好久不见,不经意间拖更2个多月。今天周末,外面淅淅沥沥下着小雨,这种窝在床上的时刻最适合写点东西了。 但是建议大家在办公或者写博客的时候尽量还是端正坐姿,我就是因为喜欢这样靠在床背上,长时间…...
Wifi wpa_supplicant 到驱动的联系
同学,别退出呀,我可是全网最牛逼的 WIFI/BT/GPS/NFC分析博主,我写了上百篇文章,请点击下面了解本专栏,进入本博主主页看看再走呗,一定不会让你后悔的,记得一定要去看主页置顶文章哦。 从framework到wpa_supplicant的适配层,其中framework部分需要了注意的是wifiservic…...
【状态估计】基于二进制粒子群优化 (BPSO) 求解最佳 PMU优化配置研究【IEEE30、39、57、118节点】(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
python 将 .pdf 文件转为 .md
环境准备 pip install aspose-words 代码 doc aw.Document(r"pdf 文件路径\xxx.pdf") doc.save("Output.md") 来源:https://products.aspose.com/words/zh/python-net/conversion/...
【C语言】操作符详解
每天一篇博客,卷死各位。 文章目录前言1. 算术操作符2. 移位进制位的表示移位操作符1. 》--左移操作符2. 《--右移操作符3.位操作符4.赋值操作符5.单目操作符6.关系操作符7. 逻辑操作符8.条件操作符9.逗号操作符总结前言 在c语言学习中操作符尤为重要,而…...
微信小程序 学生选课系统--nodejs+vue
系统分为学生和管理员,教师三个角色 学生小程序端的主要功能有: 1.用户注册和登陆系统 2.查看选课介绍信息 3.查看查看课程分类 4.查看课程详情,在线选课,提交选课信息 5.在线搜索课程信息 6.用户个人中心修改个人资料 7.用户查看…...
leaflet 加载geojson文件并显示图形(示例代码051)
第051个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet中加载geojson文件,将图形显示在地图上。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果; 注意如果OpenStreetMap无法加载,请加载其他来练习 文章目录 示例效果配置方式示例源代码(…...
【Kafka】ZK和Kafka集群的安装和配置
一、集群环境说明1. 虚拟机:192.168.223.101/103/1052. 系统版本:CentOS 7.93. JDK版本:11.0.18.0.14. Zookeeper版本:3.7.15. Kafka版本:2.13-2.8.2备注:无论是ZK,还是Kafka,都需要…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...
WebRTC从入门到实践 - 零基础教程
WebRTC从入门到实践 - 零基础教程 目录 WebRTC简介 基础概念 工作原理 开发环境搭建 基础实践 三个实战案例 常见问题解答 1. WebRTC简介 1.1 什么是WebRTC? WebRTC(Web Real-Time Communication)是一个支持网页浏览器进行实时语音…...
