当前位置: 首页 > 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…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

在建筑行业&#xff0c;项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升&#xff0c;传统的管理模式已经难以满足现代工程的需求。过去&#xff0c;许多企业依赖手工记录、口头沟通和分散的信息管理&#xff0c;导致效率低下、成本失控、风险频发。例如&#…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

MVC 数据库

MVC 数据库 引言 在软件开发领域,Model-View-Controller(MVC)是一种流行的软件架构模式,它将应用程序分为三个核心组件:模型(Model)、视图(View)和控制器(Controller)。这种模式有助于提高代码的可维护性和可扩展性。本文将深入探讨MVC架构与数据库之间的关系,以…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

spring:实例工厂方法获取bean

spring处理使用静态工厂方法获取bean实例&#xff0c;也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下&#xff1a; 定义实例工厂类&#xff08;Java代码&#xff09;&#xff0c;定义实例工厂&#xff08;xml&#xff09;&#xff0c;定义调用实例工厂&#xff…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

DBAPI如何优雅的获取单条数据

API如何优雅的获取单条数据 案例一 对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; select id, name, age from user where id #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; {&qu…...