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

代码随想录算法训练营第五十二天|300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

第九章 动态规划part13

300. 最长递增子序列

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

没有想出来,思维定式在状态定义。本题重点是递推公式:

dp[i]:前i天包含第i天的最长递增子序列的长度

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

674. 最长连续递增序列

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 rl < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

 思路与上一题类似

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

718. 最长重复子数组

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 

dp[i][j]:截止nums1前i个,nums2 前j个存在的最长重复子数组的长度。

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

相关文章:

代码随想录算法训练营第五十二天|300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

第九章 动态规划part13 300. 最长递增子序列 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列&#xff0c;删除&#xff08;或不删除&#xff09;数组中的元素而不改变其余元素的顺序。例如&#xff0c;[3,6,2,7] 是数…...

使用 Hugging Face Transformer 微调 BERT

微调 BERT有助于将其语言理解能力扩展到更新的文本领域。BERT 的与众不同之处在于它能够掌握句子的上下文关系,理解每个单词相对于其邻居的含义。我们将使用 Hugging Face Transformers 训练 BERT,还将教 BERT 分析 Arxiv 的摘要并将其分类为 11 个类别之一。 为什么微调 BER…...

Vue原型对象

原型对象 prototype 称为&#xff1a;显示的原型属性&#xff0c;用法&#xff1a;函数.prototype&#xff0c;例如&#xff1a;Vue.prototype __proto__称为&#xff1a;隐式的原型属性&#xff0c;用户&#xff1a;实例.proto&#xff0c;例如&#xff1a;vm.proto 不管如何 …...

向量数据库的分类概况

保存和检索矢量数据的五种方法&#xff1a; 像 Pinecone 这样的纯矢量数据库 全文搜索数据库&#xff0c;例如 ElasticSearch 矢量库&#xff0c;如 Faiss、Annoy 和 Hnswlib 支持矢量的NoSQL 数据库&#xff0c;例如 MongoDB、Cosmos DB 和 Cassandra 支持矢量的SQL 数据库&am…...

工业镜头的类别

工业镜头的类别 按照等效焦距分为&#xff1a; 广角镜头 中焦距镜头 长焦距镜头 广角镜头 等效焦距小于标准镜头&#xff08;等效焦距为50mm&#xff09;的镜头。特点是最小工作距离短&#xff0c;景深大&#xff0c;视角大。常常表现为桶形畸变。 中焦距镜头 焦距介于广角镜…...

实验11 SQL互联网业务查询-2

这就是SQL题带给我的自信&#x1f615; 可能发题解到博客上&#xff0c;主要是写完一遍实在不想看第二遍&#xff0c;太长了&#xff0c;优化都不想优化&#xff0c;看着头疼。 技术栈 – WhiteNights Site 一 USE mydata; #请在此处添加实现代码 ########## Begin #######…...

C++知识点梳理:C++ templates

c模板包括&#xff1a;类模板、类&#xff08;非模板类和模板类&#xff09;方法模板、函数模板、别名模板、变量模板。 类模板模板参数列表说明&#xff1a; 1&#xff09;类定义 仅模板参数列表声明&#xff0c;template<>行。 类名后无需参数说明<>。 2&#xf…...

uniapp form表单提交事件手动调用

背景&#xff1a; UI把提交的按钮弄成了图片&#xff0c;之前的button不能用了。 <button form-type"submit">搜索</button> 实现&#xff1a; html&#xff1a; 通过 this.$refs.fd 获取到form的vue对象。手动调用里面的_onSubmit()方法。 methods:…...

Accelerate 0.24.0文档 三:超大模型推理(内存估算、Sharded checkpoints、bitsandbytes量化、分布式推理)

文章目录 一、内存估算1.1 Gradio Demos1.2 The Command 二、使用Accelerate加载超大模型2.1 模型加载的常规流程2.2 加载空模型2.3 分片检查点&#xff08;Sharded checkpoints&#xff09;2.4 示例&#xff1a;使用Accelerate推理GPT2-1.5B2.5 device_map 三、bitsandbytes量…...

HackTheBox-Starting Point--Tier 2---Markup

文章目录 一 Markup测试过程1.1 打点1.2 权限获取1.3 权限升级 二 题目 一 Markup测试过程 1.1 打点 1.端口扫描 nmap -A -Pn -sC 10.129.95.1922.访问web网站&#xff0c;登录口爆破发现存在弱口令admin&#xff1a;password 3.抓包&#xff0c;发现请求体是XML格式 4.尝试使…...

android studio导入eclipse项目

网上下载一个老工程&#xff0c;.project文件里有eclipse。 android studio导入eclipse项目 eclipse项目结构 Android studio文件结构 下面是导入步骤&#xff1a; 第一步&#xff0c;打开一个项目。 选择File->New->Import Project 第二步&#xff0c;选择Eclipse项目根…...

如何利用AI实现银行存量客户的营销?

近年来&#xff0c;大数据、人工智能等热门关键字多次被写入中央文件与国务院政府工作报告&#xff0c;目前已上升为国家战略&#xff0c;并将深刻地改变现有行业的游戏规则。 金融行业是当今大数据、人工智能应用最广、最深的领域之一。随着数据仓库和数据科学的发展&#xff…...

springboot327基于Java的医院急诊系统

交流学习&#xff1a; 更多项目&#xff1a; 全网最全的Java成品项目列表 https://docs.qq.com/doc/DUXdsVlhIdVlsemdX 演示 项目功能演示&#xff1a; ————————————————...

Unity3d 导入中文字体转TMPtext asset

外部字体放入unity仓库以后呢&#xff0c;需要把这个字体转成用立体的字体文件才可以被使用&#xff01; 要想转换的话呢先放入仓库对字体点右键上面有一个Create创建里面有一个TEXT Asset&#xff0c;创建好就可以使用了...

云积万相,焕发电商店铺新活力

数字化时代&#xff0c;电商店铺的运营和营销策略越来越受到重视。如何让店铺在众多的竞争中脱颖而出&#xff0c;吸引更多的顾客&#xff0c;提高销售额&#xff0c;是每个电商品牌都需要思考的问题。云积天赫最近推出的云积万相为电商店铺带来全新的活力和更多的可能性。   …...

字典管理怎么使用,vue3项目使用若依的的字典管理模块

若依框架数据字典的使用_若依数据字典_哈哈水水水水的博客-CSDN博客 【精选】关于数据字典的理解与设计_数据字典怎么设计-CSDN博客 若依的字典值如何使用&#xff08;超详细图文教程&#xff09;_若依字典管理_丿BAIKAL巛的博客-CSDN博客 Vue3组合式API&#xff1a;getCurr…...

【汇编】内存中字的存储、用DS和[address]实现字的传送、DS与数据段

文章目录 前言一、内存中字的存储1.1 8086cpu字的概念1.2 16位的字存储在一个16位的寄存器中&#xff0c;如何存储&#xff1f;1.3 字单元 二、用DS和[address]实现字的传送2.1 字的传送是什么意思&#xff1f;2.2 要求原理解决方案&#xff1a;DS和[address]配合8086传送16字节…...

数据分析 - 分散性与变异的量度

全距 - 极差 处理变异性 方差度量 数值与均值的距离&#xff0c;也就是数据的差异性 标准差描述&#xff1a;典型值 和 均值的距离的方法&#xff0c;数据与均值的分散情况...

Neo4j数据库介绍及简单使用

图数据库介绍 图数据库是一种专门设计用于存储和管理图形数据的数据库类型。在图数据库中&#xff0c;数据以图的形式表示&#xff0c;其中节点表示实体&#xff0c;边表示实体之间的关系。这种表示方式非常适合处理具有复杂关系的数据&#xff0c;如社交网络、推荐系统、网络…...

ubuntu 20.04安装 Anaconda教程

在安装Anaconda之前需要先安装ros(防止跟conda冲突&#xff0c;先装ros)。提前安装好cuda 和cudnn。 本博客参考&#xff1a;ubuntu20.04配置ros noetic和cuda&#xff0c;cudnn&#xff0c;anaconda&#xff0c;pytorch深度学习的环境 安装完conda后&#xff0c;输入: pyth…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

Axios请求超时重发机制

Axios 超时重新请求实现方案 在 Axios 中实现超时重新请求可以通过以下几种方式&#xff1a; 1. 使用拦截器实现自动重试 import axios from axios;// 创建axios实例 const instance axios.create();// 设置超时时间 instance.defaults.timeout 5000;// 最大重试次数 cons…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

uniapp手机号一键登录保姆级教程(包含前端和后端)

目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号&#xff08;第三种&#xff09;后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

Vite中定义@软链接

在webpack中可以直接通过符号表示src路径&#xff0c;但是vite中默认不可以。 如何实现&#xff1a; vite中提供了resolve.alias&#xff1a;通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...