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

代码随想录打卡第四十四天

代码随想录–动态规划部分

day 44 动态规划第11天


文章目录

  • 代码随想录--动态规划部分
  • 一、力扣1143--最长公共子序列
  • 二、力扣1035--不相交的线
  • 三、力扣53--最大子数组和
  • 四、力扣392--判断子序列


一、力扣1143–最长公共子序列

代码随想录题目链接:代码随想录

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

思路和力扣718基本一样的,只不过是数组变成了字符串,在操作上没有区别,因为字符串也是字符的数组

定义二维的dp数组,用来记录 以text1[i-1]和text2[j-1]为结尾的最长子序列长度

但是不连续,所以要注意当text1[i-1]和text2[j-1]不相等时,dp[i][j]不能简单的赋值0,而是要取dp[i-1][j]和dp[i][j-1]的较大值

因为未来可能又有一样的值,需要在此数字基础上加一

代码如下:

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));int result = 0;for(int i = 1; i <= text1.size(); i ++)for(int j = 1; j <= text2.size(); j ++){if(text2[j-1] == text1[i-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}return dp[text1.size()][text2.size()];}
};

二、力扣1035–不相交的线

代码随想录题目链接:代码随想录

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足:

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线(非水平线)相交。
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。
以这种方法绘制线条,并返回可以绘制的最大连线数。

乍一看没什么思路,但是分析一下问题就能发现这个题是做过的

两个要求:一是元素相等,二是直线不相交

元素相等好判断,不相交怎么判断呢

实际上就是从两个数组里找到一个最长相同子序列,随意举例都没法推翻这个概念

那么就和上题一模一样了

代码如下:

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));for(int i = 1; i <= nums1.size(); i ++)for(int j = 1; j <= nums2.size(); j ++){if(nums2[j-1] == nums1[i-1]) dp[i][j] = dp[i-1][j-1] + 1;else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}return dp[nums1.size()][nums2.size()]; }
};

三、力扣53–最大子数组和

代码随想录题目链接:代码随想录

给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

定义dp数组为dp[i]代表以nums[i]为结尾的最大连续子序列和

那么递推公式应该是dp[i]=max(dp[i-1] + nums[i], nums[i])

先看一眼加上第i个会不会更大,如果还不如单独的i大,那当然是要从i重新开始计数

最后取dp的最大值即可

代码如下:

class Solution {
public:int maxSubArray(vector<int>& nums) {vector<int> dp(nums.size(), 0);dp[0] = nums[0];int result = dp[0];for(int i = 1; i < nums.size(); i ++){dp[i] = max(dp[i-1] + nums[i], nums[i]);if(dp[i] > result) result = dp[i];}return result;}
};

四、力扣392–判断子序列

代码随想录题目链接:代码随想录

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

这个题用动态规划多少有点牛刀杀鸡的感觉,其实双指针就足够了,慢指针遍历s,快指针遍历t,检查慢指针能不能到头即可

动态规划的做法需要定义二维的dp数组

dp[i][j]代表s[i-1]和t[j-1]的相同子序列长度,最后比一下是不是和s长度一样就知道了

递推公式和上面的题一样,如果s[i-1]=t[j-1],那么dp[i][j] = dp[i-1][j-1]+1,一样说明子序列多一位

不相等的话,双指针的思路是需要t往后一位,s指针不变,再搜索,这样会导致dp[i][j] = dp[i][j-1]

递推公式也明确了,就可以写了

代码如下:

class Solution {
public:bool isSubsequence(string s, string t) {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 dp[i][j] = dp[i][j-1];}return (dp[s.size()][t.size()] == s.size());}
};

双指针法做就是:

class Solution {
public:bool isSubsequence(string s, string t) {int slow = 0;int fast = 0;while(fast < t.size()){if(s[slow] == t[fast]){slow ++; fast++;}else fast++;}return slow == s.size();}
};

干干净净

相关文章:

代码随想录打卡第四十四天

代码随想录–动态规划部分 day 44 动态规划第11天 文章目录 代码随想录--动态规划部分一、力扣1143--最长公共子序列二、力扣1035--不相交的线三、力扣53--最大子数组和四、力扣392--判断子序列 一、力扣1143–最长公共子序列 代码随想录题目链接&#xff1a;代码随想录 给定…...

【JAVA】枚举类的使用:通过枚举类名称得到对应值进行输出

枚举类其实就是一个特殊的class。 /*** ClassName: CardType* Description:数字卡类型对应的文字卡类型*/ public enum CardType {NORMAL_CARD("金普卡"),BUSINESS_CARD("商务卡"),PRIVATE_CARD("黑金无限卡");private String cardName;CardTyp…...

20240731软考架构------软考6-10答案解析

每日打卡题6-10答案 6、【2012年真题】 难度&#xff1a;一般 若系统中的某子模块需要为其他模块提供访问不同数据库系统的功能&#xff0c;这些数据库系统提供的访问接口有一定的差异&#xff0c;但访问过程却都是相同的&#xff0c;例如&#xff0c;先连接数据库&#xff0c…...

学习记录——day25 多线程编程 临界资源 临界区 竞态 线程的同步互斥机制(用于解决竟态)

目录 ​编辑 一、多进程与多线程对比 二、 临界资源 临界区 竞态 例1&#xff1a;临界资源 实现 输入输出 例2&#xff1a;对临界资源 进行 减减 例子3&#xff1a;临界资源抢占使用 三、线程的同步互斥机制&#xff08;用于解决竟态&#xff09; 3.1基本概念 3.2线…...

[RK3566]linux下使用upgrade_tool报错

linux下使用upgrade_tool报错Creating Comm Object failed! Rockusb>uf /home/zhuhongxi/RK3566_AOSP_SDK/rockdev/Image-rk3566_tspi/update.img Loading firmware... Support Type:RK3568 FW Ver:b.0.00 FW Time:2024-08-03 12:00:09 Loader ver:1.01 Loader Time:…...

系统架构师(每日一练13)

每日一练 答案与解析 1.应用系统构建中可以采用多种不同的技术&#xff0c;()可以将软件某种形式的描述转换为更高级的抽象表现形式&#xff0c;而利用这些获取的信息&#xff0c;()能够对现有系统进行修改或重构&#xff0c;从而产生系统的一个新版本。答案与解析 问题1 A.逆…...

Error: No module factory available for dependency type: CssDependency

本篇主要用来记录VUE打包的问题点&#xff0c;今天使用npm run build:prod 打包VUE出现如下问题&#xff1a; Error: No module factory available for dependency type: CssDependency 因为测试和预发布都挺正常的&#xff0c;正式环境竟然出问题&#xff0c;废话不多说&…...

【langchain学习】使用Langchain生成多视角查询

使用Langchain生成多视角查询 导入所需库&#xff1a; from langchain.prompts import ChatPromptTemplate from langchain_core.output_parsers import StrOutputParser from langchain_core.runnables import RunnablePassthrough from config import llm设置提示模板&#x…...

ASPCMS 漏洞详细教程

一.后台修改配置文件拿shell 登录后台 如下操作 保存并抓包 将slideTextStatus的值修改为1%25><%25Eval(Request(chr(65)))25><%25 放包&#xff08;连接密码是a&#xff09; 然后用工具连接 成功连接...

二维码生成原理及解码原理

☝☝☝二维码配图 二维码 二维码&#xff08;Quick Response Code&#xff0c;简称QR码&#xff09;是一种广泛使用的二维条形码技术&#xff0c;由日本公司Denso Wave在1994年开发。二维码能有效地存储和传递信息&#xff0c;广泛应用于商品追溯、支付、广告等多个领域。二维…...

云计算实训20——mysql数据库安装及应用(增、删、改、查)

一、mysql安装基本步骤 1.下载安装包 wget https://downloads.mysql.com/archives/get/p/23/file/mysql-8.0.33-1.el7.x86_64.rpm-bundle.tar 2.解压 tar -xf mysql-8.0.33-1.el7.x86_64.rpm-bundle.tar 3.卸载mariadb yum -y remove mariadb 查看解压后的包 [rootmysq…...

24年电赛——自动行驶小车(H题)基于 CCS Theia -陀螺仪 JY60 代码移植到 MSPM0G3507(附代码)

前言 只要搞懂 M0 的代码结构和 CCS 的图形化配置方法&#xff0c;代码移植就会变的很简单。因为本次电赛的需要&#xff0c;正好陀螺仪部分代码的移植是我完成的。&#xff08;末尾附全部代码&#xff09; 一、JY60 陀螺仪 JY60特点 1.模块集成高精度的陀螺仪、加速度计&…...

数组的增删查查改

1、增 1.Cpp #include <iostream> using namespace std; #include "add.h"int main() {//初始化数组int arr[5];//前四个元素为1&#xff0c;2&#xff0c;3&#xff0c;4for (int i 0; i < 4; i){arr[i] i1;}//数组第5个赋值为100arr[4] 100;for (int…...

设计模式——动态代理

设计模式——动态代理 动态代理的基本概念动态代理的实现步骤总结 在Java中&#xff0c;动态代理是一种强大的机制&#xff0c;它允许在运行时创建一个代理对象&#xff0c;这个代理对象可以代表另一个实际对象&#xff0c;它允许你在不直接操作原始对象的情况下&#xff0c;通…...

vue(element-ui组件) 的this.$notify的具体使用

getNotify() {this.noClose();let message "";message this.itemData.map((ele) > {const text "任务" ele.title "新增" ele.num "条言论";return this.$createElement("el-tooltip",{props: {content: text,pla…...

c++ - 模拟实现set、map

文章目录 前言一、set模拟实现二、map模拟实现 前言 在C标准库中&#xff0c;std::set 和 std::map都是非常常用的容器&#xff0c;它们提供了基于键值对的存储和快速查找能力。然而&#xff0c;关于它们的底层实现&#xff0c;C标准并没有强制规定具体的数据结构&#xff0c;只…...

计算机网络-PIM协议基础概念

一、PIM基础概念 组播网络回顾&#xff1a; 组播网络从网络结构上大体可以分为三个部分&#xff1a; 源端网络&#xff1a;将组播源产生的组播数据发送至组播网络。 组播转发网络&#xff1a;形成无环的组播转发路径&#xff0c;该转发路径也被称为组播分发树&#xff08;Multi…...

优化PyCharm:让IDE响应速度飞起来

优化PyCharm&#xff1a;让IDE响应速度飞起来 PyCharm&#xff0c;作为一款功能强大的集成开发环境&#xff08;IDE&#xff09;&#xff0c;在提供丰富功能的同时&#xff0c;有时也会出现响应慢的问题。这不仅影响开发效率&#xff0c;还可能打击开发者的积极性。本文将详细…...

对象转化为String,String转化为对象

title: 对象转化为string&#xff0c;string转化为对象 date: 2024-08-02 11:50:40 tags: javascript const obj { uname:haha, age:18,gender:女} //将对象转换成string JSON.stringify(obj) //取成一个对象&#xff0c;将字符串传化为对象 JSON.parse(obj)常用领域在localst…...

SolverLearner:提升大模型在高度归纳推理的复杂任务性能,使其能够在较少的人为干预下自主学习和适应

SolverLearner&#xff1a;提升大模型在高度归纳推理的复杂任务性能&#xff0c;使其能够在较少的人为干预下自主学习和适应 提出背景归纳推理&#xff08;Inductive Reasoning&#xff09;演绎推理&#xff08;Deductive Reasoning&#xff09;反事实推理&#xff08;Counterf…...

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

实战三:开发网页端界面完成黑白视频转为彩色视频

​一、需求描述 设计一个简单的视频上色应用&#xff0c;用户可以通过网页界面上传黑白视频&#xff0c;系统会自动将其转换为彩色视频。整个过程对用户来说非常简单直观&#xff0c;不需要了解技术细节。 效果图 ​二、实现思路 总体思路&#xff1a; 用户通过Gradio界面上…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

起重机起升机构的安全装置有哪些?

起重机起升机构的安全装置是保障吊装作业安全的关键部件&#xff0c;主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理&#xff1a; 一、超载保护装置&#xff08;核心安全装置&#xff09; 1. 起重量限制器 功能&#xff1a;实时监测起升载荷&a…...

stm32进入Infinite_Loop原因(因为有系统中断函数未自定义实现)

这是系统中断服务程序的默认处理汇编函数&#xff0c;如果我们没有定义实现某个中断函数&#xff0c;那么当stm32产生了该中断时&#xff0c;就会默认跑这里来了&#xff0c;所以我们打开了什么中断&#xff0c;一定要记得实现对应的系统中断函数&#xff0c;否则会进来一直循环…...