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

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

300.最长递增子序列

        这道题还挺简单的,咱们设置dp[i]表示到第i个数字时的递增子序列的最长的值,那么dp[i]就要遍历从0到i-1的数,也就是看看当前这个数字是否比前面的数字大,如果大的话就看看现在的子序列长度是否会长于前面那个数字代表的子序列长度+1(1是表示加上当前这个数字),如果不会的话就更新最长值。

https://leetcode.cn/problems/longest-increasing-subsequence/submissions/510789123/

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

674.最长连续递增序列

        动规题写多了题感也就来了,这道题求最长连续递增序列,dp[i]表示到第i个数字的最长递增子序列是多少,如果nums[i]>nums[i-1],自然说明i可以加入到前面那个序列里面,所以dp[i]+=dp[i-1],如果nums[i]<=nums[i-1],则说明i不可以加入,所以dp[i]还是维持1(注意:这里就涉及初始化的问题,因为根据dp[i]的解释,可以知道初始化时最长递增子序列也就是这个数字本身)。

https://leetcode.cn/problems/longest-continuous-increasing-subsequence/description/

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];}}int result=0;for(int i=0;i<nums.size();i++){result=max(result,dp[i]);}return result;}
};

718.最长重复子数组

        这道题我听完讲解的一半就去做,但是过不了,仔细一看,我的判断条件写成dp[i]==dp[j],这就要回到这道题的原始了,dp[i][j]表示到第一个数组的第i个,第二个数组的第j个时候的最长重复子数组,这里我们把dp[i][j]初始化的数组增加了最上面【0】下标的一行最左边【0】下标的一列,这样我们可以按照直观的表示,第i个就是从nums1数第i个,而不是从0下标开始,就方便我们计算了,但是需要注意的就是判断条件要是dp[i-1]==dp[j-1]因为虽然数是那样从1开始数,但是我们遍历nums1和nums2还是得从下标0的时候开始遍历。

https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>>dp(nums1.size()+1,vector<int>(nums2.size()+1,0));int result=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;result=max(result,dp[i][j]);}}}return result;}
};

相关文章:

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

300.最长递增子序列 这道题还挺简单的&#xff0c;咱们设置dp[i]表示到第i个数字时的递增子序列的最长的值&#xff0c;那么dp[i]就要遍历从0到i-1的数&#xff0c;也就是看看当前这个数字是否比前面的数字大&#xff0c;如果大的话就看看现在的子序列长度是否会长于前面那个数…...

分享一些开源的游戏仓库

1.CnC_Remastered_Collection 红色警戒95版本 https://github.com/electronicarts/CnC_Remastered_Collection gitee仓库分流&#xff1a;https://gitee.com/loswdarmy/CnC_Remastered_Collection 2.Far-Cry-1-Source-Full 孤岛惊魂1 https://github.com/StrongPC123/Far-Cry-…...

Java详解:单列 | 双列集合 | Collections类

○ 前言&#xff1a; 在开发实践中&#xff0c;我们需要一些能够动态增长长度的容器来保存我们的数据&#xff0c;java中为了解决数据存储单一的情况&#xff0c;java中就提供了不同结构的集合类&#xff0c;可以让我们根据不同的场景进行数据存储的选择&#xff0c;如Java中提…...

Centos7 使用docker来部署mondb

参考官方手册&#xff1a; https://www.mongodb.com/docs/manual/tutorial/install-mongodb-community-with-docker/#std-label-docker-mongodb-community-install 使用脚本快速安装docker curl -fsSL https://get.docker.com -o get-docker.sh | bash get-docker.sh使用 Doc…...

Java SE入门及基础(35)

接口 1. 概念 在软件工程中&#xff0c;软件与软件的交互很重要&#xff0c;这就需要一个约定。每个程序员都应该能够编写实现这样的约定。接口就是对约定的描述。 In the Java programming language, an interface is a reference type, similar to a class, that can con…...

基于YOLOv8/YOLOv7/YOLOv6/YOLOv5的常见车型识别系统(Python+PySide6界面+训练代码)

摘要&#xff1a;本文深入探讨了如何应用深度学习技术开发一个先进的常见车型识别系统。该系统核心采用最新的YOLOv8算法&#xff0c;并与早期的YOLOv7、YOLOv6、YOLOv5等版本进行性能比较&#xff0c;主要评估指标包括mAP和F1 Score等。详细解析了YOLOv8的工作机制&#xff0c…...

Sqoop 学习

参考视频 大数据Sqoop教程丨从零开始讲解大数据业务及数据采集和迁移需求_哔哩哔哩_bilibili 介绍 Sqoop是Hadoop生态体系和RDBMS&#xff08;关系型数据库&#xff09;体系之间传送数据的一种工具 Hadop生态系统&#xff1a;HDFS&#xff0c;Hbase&#xff0c;Hive等 RDBMS包…...

Ollama 只安装 Ollama,本地快速部署谷歌开源大模型Gemma(基于Ollama)

参考&#xff1a;本地快速部署谷歌开源大模型Gemma(基于Ollama) - 知乎 确保系统更新: Bash sudo apt update && sudo apt upgrade 需要先下载Ollama&#xff0c;版本要求0.1.26及以上 运行curl -fsSL https://ollama.com/install.sh | sh 监听 Ollama API 接…...

一条 sql 语句可能导致的表锁和行锁以及死锁检测

锁 MDL 当对一个表做增删改查操作的时候&#xff0c;加 MDL 读锁&#xff1b;当要对表做结构变更操作的时候&#xff0c;加 MDL 写锁 ALTER TABLE tbl_name NOWAIT add column ... ALTER TABLE tbl_name WAIT N add column ... …...

prometheus 原理(架构,promql表达式,描点原理)

大家好&#xff0c;我是蓝胖子&#xff0c;提到监控指标&#xff0c;不得不说prometheus&#xff0c;今天这篇文章我会对prometheus 的架构设计&#xff0c;promql表达式原理和监控图表的绘图原理进行详细的解释。来让大家对prometheus的理解更加深刻。 架构设计 先来看看&am…...

Linux的目录结构(介绍主要的)

/&#xff1a;根目录&#xff0c;文件系统的起点&#xff0c;包含了所有目录和文件 /bin&#xff1a;存放基本的可执行命令&#xff0c;如ls&#xff0c;cp&#xff0c;rm /lib&#xff1a;主要存放动态链接库 /opt&#xff1a;供第三方软件安装的目录&#xff0c;通常将软件…...

推房子游戏c++

这段代码是一个推箱子游戏的实现。游戏中有一个地图&#xff0c;地图上有墙壁、人、箱子和目标位置。玩家通过键盘输入WASD或方向键来控制人物的移动&#xff0c;目标是将所有的箱子推到相应的目标位置上。 代码中的dt数组表示地图&#xff0c;每个位置上的字符表示对应的元素…...

docker学习入门篇

1、docker简介 docker官网&#xff1a; www.docker.com dockerhub官网&#xff1a; hub.docker.com docker文档官网&#xff1a;docs.docker.com Docker是基于Go语言实现的云开源项目。 Docker的主要目标是&#xff1a;Build, Ship and Run Any App, Anywhere(构建&…...

【Spring Boot 3】动态注入和移除Bean

【Spring Boot 3】动态注入和移除Bean 背景介绍开发环境开发步骤及源码工程目录结构总结动态注入Bean的方法动态移除Bean的方法注意事项背景 软件开发是一门实践性科学,对大多数人来说,学习一种新技术不是一开始就去深究其原理,而是先从做出一个可工作的DEMO入手。但在我个…...

555经典电路

1、555介绍&#xff1a; 555 定时器是一种模拟和数字功能相结合的中规模集成器件。一般用双极性工艺制作的称为 555&#xff0c;用 CMOS 工艺制作的称为 7555&#xff0c;除单定时器外&#xff0c;还有对应的双定时器 556/7556。555 定时器的电源电压范围宽&#xff0c;可在 4…...

vue 下载的插件从哪里上传?npm发布插件详细记录

文章参考&#xff1a; 参考文章一&#xff1a; 封装vue插件并发布到npm详细步骤_vue-cli 封装插件-CSDN博客 参考文章二&#xff1a; npm发布vue插件步骤、组件、package、adduser、publish、getElementsByClassName、important、export、default、target、dest_export default…...

吴恩达机器学习笔记 十七 通过偏差与方差诊断性能 正则化 偏差 方差

高偏差&#xff08;欠拟合&#xff09;&#xff1a;在训练集上表现得也不好 高方差&#xff08;过拟合&#xff09;&#xff1a;J_cv要远大于J_train 刚刚好&#xff1a;J_cv和J_train都小 J_cv和J_train与拟合多项式阶数的关系 从一阶到四阶&#xff0c;训练集的误差越来越小…...

Java高频面试之SSM篇

有需要互关的小伙伴,关注一下,有关必回关,争取今年认证早日拿到博客专家 Java高频面试之总纲篇 Java高频面试之集合篇 Java高频面试之异常篇 Java高频面试之并发篇 Java高频面试之SSM篇 Java高频面试之Mysql篇 Java高频面试之Redis篇 Java高频面试之消息队列与分布式篇…...

【软件工程】介绍

软件工程 软件工程是一门应用计算机科学、数学和工程原则来设计、开发、维护和测试软件的学科。软件工程着重于创建质量高效、可靠、可使用、可维护和快速开发的系统。这个领域从20世纪60年代初开始蓬勃发展&#xff0c;主要是为了解决软件危机&#xff0c;即随着计算机和软件…...

考研复习C语言初阶(4)+标记和BFS展开的扫雷游戏

目录 1. 一维数组的创建和初始化。 1.1 数组的创建 1.2 数组的初始化 1.3 一维数组的使用 1.4 一维数组在内存中的存储 2. 二维数组的创建和初始化 2.1 二维数组的创建 2.2 二维数组的初始化 2.3 二维数组的使用 2.4 二维数组在内存中的存储 3. 数组越界 4. 冒泡…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

基于Uniapp开发HarmonyOS 5.0旅游应用技术实践

一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架&#xff0c;支持"一次开发&#xff0c;多端部署"&#xff0c;可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务&#xff0c;为旅游应用带来&#xf…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

Xen Server服务器释放磁盘空间

disk.sh #!/bin/bashcd /run/sr-mount/e54f0646-ae11-0457-b64f-eba4673b824c # 全部虚拟机物理磁盘文件存储 a$(ls -l | awk {print $NF} | cut -d. -f1) # 使用中的虚拟机物理磁盘文件 b$(xe vm-disk-list --multiple | grep uuid | awk {print $NF})printf "%s\n"…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...