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

代码随想录第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.不同的子序列

一、判断子序列 题目描述&#xff1a; 思路和想法&#xff1a; 这道题目还是最长公共子序列的拓展&#xff0c;只是这里进行删除的一定是t字符串&#xff0c;当不相等时&#xff0c;dp[i][j] dp[i][j - 1]&#xff1b;其余基本一致。当最长公共子序列个数等s.size()时&#x…...

代码随想录第55天(动态规划):● 309.最佳买卖股票时机含冷冻期 ● 714.买卖股票的最佳时机含手续费

一、最佳买卖股票时机含冷冻期 题目描述: 思路和想法&#xff1a; 这道题相较于之前的题目&#xff0c;注重对状态的分析&#xff0c;这里分为四个状态。 &#xff08;1&#xff09;状态一&#xff0c;买入状态 dp[i][0] 操作一&#xff1a;前一天就是持有状态&#xff08;状…...

字符串装换整数(atoi)-力扣8-java

一、题目描述请你来实现一个 myAtoi(string s) 函数&#xff0c;使其能将字符串转换成一个 32 位有符号整数&#xff08;类似 C/C 中的 atoi 函数&#xff09;。函数 myAtoi(string s) 的算法如下&#xff1a;读入字符串并丢弃无用的前导空格检查下一个字符&#xff08;假设还未…...

毕业5年,从月薪3000到年薪40w,我掌握了那些核心技能?(建议收藏)

大家好&#xff0c;我是静静~~是一枚一线大厂的测试开发工程师很多读者私信问我&#xff0c;自己时间不短了&#xff0c;随着工作年限的不断增长&#xff0c;感觉自己的技术水平与自己的工作年限严重不符。想跳槽出去换个新环境吧&#xff0c;又感觉自己的能力达不到心仪公司的…...

C++中的并行与并发

1.1 并行基础std::thread 用于创建一个执行的线程实例&#xff0c;所以它是一切并发编程的基础&#xff0c;使用时需要包含 <thread> 头文件&#xff0c; 它提供了很多基本的线程操作&#xff0c;例如 get_id() 来获取所创建线程的线程 ID&#xff0c;使用 join() 来加入…...

h2database源码解析-如何更新一条行记录

这里的更新包括两种操作&#xff1a;删、改。更新操作涉及的内容在其他文章里面已经做过介绍了&#xff0c;本文主要是介绍更新的代码流程&#xff0c;以了解更新操作都做了哪些事情。如果有未介绍过的知识点会详细介绍。 目录改(update)如何判读是否加了行锁删(delete)改(upda…...

FyListen——生命周期监听器(设计原理之理解生命周期)

FyListen——生命周期监听器&#xff08;设计原理之理解生命周期&#xff09; FyListen 的核心原理有两个&#xff1a; 通过子Fragment对Activity、Fragment进行生命周期监听Java8 接口特性 default 1. 什么是上下文Context 这是一个装饰器模式&#xff0c; 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模块安装失败的原因以及解决办法 很多朋友拿到代码之后&#xff0c;就开始复制粘贴 --> 然后右键进行运行 结果就是报错说 没有这个模块 得安装啥的 Python模块安装 一. 打开命令提示符 win …...

《NFL橄榄球》:洛杉矶闪电·橄榄1号位

洛杉矶闪电&#xff08;英语&#xff1a;Los Angeles Chargers&#xff09;&#xff0c;又译“洛杉磯衝鋒者”。是一支位于加利福尼亚州洛杉矶郡英格尔伍德的职业美式橄榄球球队&#xff0c;现为美国橄榄球联合会西区成员之一。该队曾于1961年搬迁到圣地亚哥而改叫圣地亚哥电光…...

4.7 Python设置代码格式

随着你编写的程序越来越长&#xff0c;有必要了解一些代码格式设置约定。请花时让你的代码尽可能易于阅读&#xff1b;让代码易于阅读有助于你掌握程序是做什么的,也可以帮助他人理解你编写的代码。为确保所有人编写的代码的结构都大致一致&#xff0c;Python程序员都遵循一些格…...

Zabbix 构建监控告警平台(五)

Zabbix 自动发现Zabbix 自动注册1.Zabbix 自动发现 1.1前言 为了满足监控企业成千上万台服务器&#xff0c;因此我们需要使用Zabbix批量监控来实现。自动发现和自动注册。 1.2zabbix-server &#xff08;一&#xff09;1、创建自动发现规则 在“配置”->“自动发现”->“…...

2023关键词:挑战

未失踪人口回归… 好久不见&#xff0c;不经意间拖更2个多月。今天周末&#xff0c;外面淅淅沥沥下着小雨&#xff0c;这种窝在床上的时刻最适合写点东西了。 但是建议大家在办公或者写博客的时候尽量还是端正坐姿&#xff0c;我就是因为喜欢这样靠在床背上&#xff0c;长时间…...

Wifi wpa_supplicant 到驱动的联系

同学,别退出呀,我可是全网最牛逼的 WIFI/BT/GPS/NFC分析博主,我写了上百篇文章,请点击下面了解本专栏,进入本博主主页看看再走呗,一定不会让你后悔的,记得一定要去看主页置顶文章哦。 从framework到wpa_supplicant的适配层,其中framework部分需要了注意的是wifiservic…...

【状态估计】基于二进制粒子群优化 (BPSO) 求解最佳 PMU优化配置研究【IEEE30、39、57、118节点】(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

python 将 .pdf 文件转为 .md

环境准备 pip install aspose-words 代码 doc aw.Document(r"pdf 文件路径\xxx.pdf") doc.save("Output.md") 来源&#xff1a;https://products.aspose.com/words/zh/python-net/conversion/...

【C语言】操作符详解

每天一篇博客&#xff0c;卷死各位。 文章目录前言1. 算术操作符2. 移位进制位的表示移位操作符1. 》--左移操作符2. 《--右移操作符3.位操作符4.赋值操作符5.单目操作符6.关系操作符7. 逻辑操作符8.条件操作符9.逗号操作符总结前言 在c语言学习中操作符尤为重要&#xff0c;而…...

微信小程序 学生选课系统--nodejs+vue

系统分为学生和管理员&#xff0c;教师三个角色 学生小程序端的主要功能有&#xff1a; 1.用户注册和登陆系统 2.查看选课介绍信息 3.查看查看课程分类 4.查看课程详情&#xff0c;在线选课&#xff0c;提交选课信息 5.在线搜索课程信息 6.用户个人中心修改个人资料 7.用户查看…...

leaflet 加载geojson文件并显示图形(示例代码051)

第051个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+leaflet中加载geojson文件,将图形显示在地图上。 直接复制下面的 vue+openlayers源代码,操作2分钟即可运行实现效果; 注意如果OpenStreetMap无法加载,请加载其他来练习 文章目录 示例效果配置方式示例源代码(…...

【Kafka】ZK和Kafka集群的安装和配置

一、集群环境说明1. 虚拟机&#xff1a;192.168.223.101/103/1052. 系统版本&#xff1a;CentOS 7.93. JDK版本&#xff1a;11.0.18.0.14. Zookeeper版本&#xff1a;3.7.15. Kafka版本&#xff1a;2.13-2.8.2备注&#xff1a;无论是ZK&#xff0c;还是Kafka&#xff0c;都需要…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...