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

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

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

srs linux

下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935&#xff0c;SRS管理页面端口是8080&#xff0c;可…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

代理篇12|深入理解 Vite中的Proxy接口代理配置

在前端开发中,常常会遇到 跨域请求接口 的情况。为了解决这个问题,Vite 和 Webpack 都提供了 proxy 代理功能,用于将本地开发请求转发到后端服务器。 什么是代理(proxy)? 代理是在开发过程中,前端项目通过开发服务器,将指定的请求“转发”到真实的后端服务器,从而绕…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Spring是如何解决Bean的循环依赖:三级缓存机制

1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间‌互相持有对方引用‌,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...