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

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

300.最长递增子序列

题目链接/文章讲解/视频讲解:代码随想录

1.代码展示

//300.最长递增子序列
int lengthOfLIS(vector<int>& nums) {if (nums.size() == 1) {return 1;}//step1 构建dp数组//dp[i]的含义是长度未nums数组中长度为i + 1的数组的最长子序列长度vector<int> dp(nums.size(), 1);//step2 状态转移方程//将第i + 1个数和前面的i个数一一对比,找到最大的dp[i]//if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);//step3 初始化//step4 开始遍历int nResult = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = max(dp[i], dp[j] + 1);}}nResult = max(nResult, dp[i]);}return nResult;
}

 2.本体小节

        思考:明确本题dp数组含义,dp[i]指的是到下标为i的数组中最长递增子序列个数;遍历nums数组,再对下标i前的所有数字进行遍历,通过比较nums[i]和nums[j]的大小,来更新最大dp[i],即dp[i] = max(dp[i], dp[j] + 1);i下次遍历之前,更新result即可,最终取出最大的dp[i]作为结果;注意初始化时每个元素都为1,因为元素本身递增子序列就为1。

        基本思路:如上,注意初始化和状态转移方程。

674. 最长连续递增序列

题目链接/文章讲解/视频讲解:代码随想录

1.代码展示

//674.连续最长递增子序列
int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 1) {return 1;}vector<int> dp(nums.size(), 1);int nResult = 0;for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) {dp[i] = dp[i - 1] + 1;}nResult = max(nResult, dp[i]);}return nResult;
}

 2.本题小节

        思考:本题和上一题最大的不同在于,遍历时,当前值只需要和前一个值进行比较即可,不需要对当前值之前的所有值进行遍历;因此dp[i]只与dp[i - 1]有关,如果nums[i] > nums[i - 1],那么dp[i] = dp[i - 1] + 1,并更新result,获得最大的dp[i];初始化时dp均为1。

       基本思路:如上,注意初始化和状态转移方程。

718. 最长重复子数组  

 题目链接/文章讲解/视频讲解:代码随想录

1.代码展示

//718.最长重复子数组
int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int nResult = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;nResult = max(nResult, dp[i][j]);}}}return nResult;
}

2.本题小节

        思考:本题和上面两题不同的是本题要比较的是两个数组的最长重复子数组。构建dp数组,dp[i][j]含义是以下标为 i - 1 和 j - 1 为结尾的数组A和B的最长重复子序列,初始化时数组全部初始化为0,这里dp[i][j]的含义就体现了出来,不需要对dp[0][j]和dp[i][0]一个一个初始化。首先对nums1开始遍历,再对nums2遍历,都从1开始,当nums1[i - 1] == nums2[j - 1]时,此时触发状态转移方程,dp[i][j]  = dp[i - 1][j - 1] + 1,并更新result。

        基本思路:注意本题使用的是二维数组,并把每种情况都列举了出来。

相关文章:

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

300.最长递增子序列 题目链接/文章讲解/视频讲解&#xff1a;代码随想录 1.代码展示 //300.最长递增子序列 int lengthOfLIS(vector<int>& nums) {if (nums.size() 1) {return 1;}//step1 构建dp数组//dp[i]的含义是长度未nums数组中长度为i 1的数组的最长子序列长…...

前端三大Css处理器之Less

Less是Css预处理器之一&#xff0c;分别有Sass、Less、Stylus这三个。 Lesshttps://lesscss.org/ Less是用JavaScript编写的&#xff0c;事实上&#xff0c;Less是一个JavaScript库&#xff0c;他通过混合、变量、嵌套和规则设置循环扩展了原生普通Css的功能。Less的少数…...

Win 教程 Win7实现隔空投送

一直觉得自己写的不是技术&#xff0c;而是情怀&#xff0c;一个个的教程是自己这一路走来的痕迹。靠专业技能的成功是最具可复制性的&#xff0c;希望我的这条路能让你们少走弯路&#xff0c;希望我能帮你们抹去知识的蒙尘&#xff0c;希望我能帮你们理清知识的脉络&#xff0…...

代码随想录算法训练营Day45 | 70. 爬楼梯 (进阶) | 322. 零钱兑换 | 279. 完全平方数

文章目录 70. 爬楼梯 (进阶)322. 零钱兑换二维数组滚动数组 279. 完全平方数 70. 爬楼梯 (进阶) 题目链接 | 理论基础 以完全背包的思路来解题&#xff0c;正如组合总和 Ⅳ 中提到的一样。在本题中&#xff0c;先背包后物品的思路就显得非常合理明显了。 本题中的物品就是可…...

算法训练营第四十一天(9.2)| 动态规划Part11:最长公共子序列

Leecode 1143.最长公共子序列 题目地址&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 题目类型&#xff1a;最长子序列 class Solution { public:int longestCommonSubsequence(string text1, string text2) {int m text1.size(), n t…...

k8s基于rbac权限管理serviceAccount授权管理

测试通过http访问apiServer curl没有证书不能通过https来访问apiServer需要使用kubectl代理 #使用kubectl代理 kubectl proxy --port8111& #curl访问 api/v1 是资源所属群组/版本 即创建资源时定义的apiVersion #后边跟的是要访问的资源 #查看所有命名空间 #查看核心资源用…...

linux URL访问工具

URL访问工具 有时候想在命令行下通过http访问接口/网页&#xff0c;可以使用curl来进行操作 发起请求 curl www.baidu.com 会返回网页内容 参数选项 -i参数 使用-i参数&#xff0c;会返回响应header curl -i www.baidu.com -I参数 使用-I参数&#xff0c;只会返回响应header cu…...

CCF-CSP 29次 第五题【202303-5 施肥】

计算机软件能力认证考试系统 题解&#xff08;35分&#xff09;&#xff1a; 枚举每个区间&#xff0c;再枚举每个施肥车&#xff0c;看所有的施肥车能不能把这个区间填满 #include<bits/stdc.h> using namespace std; const int N410; int n,m; typedef pair<int,…...

前端基础4——jQuery

文章目录 一、基本了解1.1 导入jQuery库1.2 基本语法1.3 选择器 二、操作HTML2.1 隐藏和显示元素2.2 获取与设置内容2.3 获取、设置和删除属性2.4 添加元素2.5 删除元素2.6 设置CSS样式 三、jQuery Ajax3.1 基本语法3.2 回调函数3.3 常用HTTP方法3.4 案例一3.4.1 准备工作3.4.2…...

测试人:“躺平?不可能的“, 盘点测试人在职场的优势

之前有这么一个段子&#xff1a;有人喜欢创造世界&#xff0c;他们做了程序员&#xff1b;有人喜欢拯救世界&#xff0c;他们做了测试员&#xff01;近几年&#xff0c;测试工程师在企业究竟是怎么样的发展&#xff1f;随着企业对于用户体验的满意度越来越重视&#xff0c;更加…...

C++:初识类与this指针

文章目录 前言一、类类的定义和实例化类的访问限定符类的作用域计算类的大小 二、类的成员函数的this指针总结 个人主页 &#xff1a; 个人主页 个人专栏 &#xff1a; 《数据结构》 《C语言》《C》 前言 一、类 类的定义和实例化 注意类定义结束时后面分号( ; )不能省略。 类…...

2023应届生java面试紧张失误之一:CAS口误说成开心锁-笑坏面试官

源于&#xff1a;XX网&#xff0c;如果冒犯&#xff0c;表示歉意 面试官&#xff1a;什么是CAS 我&#xff1a;这个简单&#xff0c;开心锁 面试官&#xff1a;WTF&#xff1f; 我&#xff1a;一脸自信&#xff0c;对&#xff0c;就是这个 面试官&#xff1a;哈哈大笑&#xff…...

Excel_VBA程序文件的加密及解密说明

VBA应用技巧及疑难解答 Excel_VBA程序文件的加密及解密 在您看到这个文档的时候&#xff0c;请和我一起念&#xff1a;“唵嘛呢叭咪吽”“唵嘛呢叭咪吽”“唵嘛呢叭咪吽”&#xff0c;为自己所得而感恩&#xff0c;为付出者赞叹功德。 本不想分享之一技术&#xff0c;但众多学…...

Flutter关于StatefulWidget中State刷新时机的一点实用理解

刚入门flutter开发&#xff0c;使用StatefulWidget踩了很多坑&#xff0c;就我遇到典型问题谈谈见解。 1.initState方法只会在控件初始化的时候执行一遍。 2.控件内部执行setState方法&#xff0c;则会每次执行build方法。 3.控件销毁会执行dispose方法&#xff0c;所以一些…...

CS420 课程笔记 P2 - 内存编辑和基础的 GameHacking 尝试

文章目录 IntroductionOperating SystemToolsMemory ScanningMemory ScanExamples!Conclusion Introduction 本节将介绍操作系统的基础知识和内存扫描&#xff0c;这可以说是 game hacking 中最重要的技能&#xff0c;我们不会深入讨论操作系统&#xff0c;因为这本身就是一门…...

【sql】MongoDB 查询 高级用法

【sql】MongoDB 查询 高级用法 一、基本查询指定字段 db.getCollection(students).find({}, {name: 1, score: 1}) 二、指定字段别名 db.getCollection(students).find({}, {"name":1, "score":1, "grade":"$grade.grade"}) 这里将…...

监督学习的介绍

一、定义 监督学习是利用一组已知类别的样本调整分类器的参数&#xff0c;使其达到所要求性能的过程&#xff0c;也称为监督训练或有教师学习。它是一种机器学习的方法&#xff0c;目的是让模型能够从已知的输入和输出之间的关系中学习&#xff0c;并且能够对新的输入做出正确…...

【DRONECAN】(三)WSL2 及 ubuntu20.04 CAN 驱动安装

【DRONECAN】&#xff08;三&#xff09;WSL2 及 ubuntu20.04 CAN 驱动安装 前言 这一篇文章主要介绍一下 WSL2 及 ubuntu20.04 CAN 驱动的安装&#xff0c;首先说一下介绍本文的目的。 大家肯定都接触过 ubuntu 系统&#xff0c;但是我们常用的操作系统都是 Windows&#x…...

Databricks 入门之sql(二)常用函数

1.类型转换函数 使用CAST函数转换数据类型&#xff08;可以起别名&#xff09; SELECTrating,CAST(timeRecorded as timestamp) FROMmovieRatings; 支持的数据类型有&#xff1a; BIGINT、BINARY、BOOLEAN、DATE 、DECIMAL(p,s)、 DOUBLE、 FLOAT、 INT、 INTERVAL interva…...

Simulink建模与仿真(3)-Simulink 简介

分享一个系列&#xff0c;关于Simulink建模与仿真&#xff0c;尽量整理成体系 1、Simulink特点 Simulink是一个用来对动态系统进行建模、仿真和分析的软件包。使用Simulink来建模、分析和仿真各种动态系统(包括连续系统、离散系统和混合系统)&#xff0c;将是一件非常轻松的事…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

作为测试我们应该关注redis哪些方面

1、功能测试 数据结构操作&#xff1a;验证字符串、列表、哈希、集合和有序的基本操作是否正确 持久化&#xff1a;测试aof和aof持久化机制&#xff0c;确保数据在开启后正确恢复。 事务&#xff1a;检查事务的原子性和回滚机制。 发布订阅&#xff1a;确保消息正确传递。 2、性…...

掌握 HTTP 请求:理解 cURL GET 语法

cURL 是一个强大的命令行工具&#xff0c;用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中&#xff0c;cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

【SpringBoot自动化部署】

SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一&#xff0c;能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时&#xff0c;需要添加Git仓库地址和凭证&#xff0c;设置构建触发器&#xff08;如GitHub…...

JS红宝书笔记 - 3.3 变量

要定义变量&#xff0c;可以使用var操作符&#xff0c;后跟变量名 ES实现变量初始化&#xff0c;因此可以同时定义变量并设置它的值 使用var操作符定义的变量会成为包含它的函数的局部变量。 在函数内定义变量时省略var操作符&#xff0c;可以创建一个全局变量 如果需要定义…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...