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

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

【7色560页】职场可视化逻辑图高级数据分析PPT模版

7种色调职场工作汇报PPT&#xff0c;橙蓝、黑红、红蓝、蓝橙灰、浅蓝、浅绿、深蓝七种色调模版 【7色560页】职场可视化逻辑图高级数据分析PPT模版&#xff1a;职场可视化逻辑图分析PPT模版https://pan.quark.cn/s/78aeabbd92d1...

[拓扑优化] 1.概述

常见的拓扑优化方法有&#xff1a;均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有&#xff1a;有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...

如何通过git命令查看项目连接的仓库地址?

要通过 Git 命令查看项目连接的仓库地址&#xff0c;您可以使用以下几种方法&#xff1a; 1. 查看所有远程仓库地址 使用 git remote -v 命令&#xff0c;它会显示项目中配置的所有远程仓库及其对应的 URL&#xff1a; git remote -v输出示例&#xff1a; origin https://…...