代码随想录第51天|● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

文章目录

  • ● 300.最长递增子序列
    • 思路
    • 代码:
  • ● 674. 最长连续递增序列
    • 思路:
    • 代码:
  • ● 718. 最长重复子数组
    • 思路:
    • 代码一:dp二维数组
    • 代码二:滚动数组

● 300.最长递增子序列

在这里插入图片描述

思路

dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码:

注意:需要判断[0]输出是1的情况。

class Solution {public int lengthOfLIS(int[] nums) {// if(nums.length==1)return 1;int[] dp = new int[nums.length];int res = 1;Arrays.fill(dp, 1);for(int i=1;i<nums.length;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=Math.max(dp[i],dp[j]+1);}}res = Math.max(res, dp[i]);}return res;}
}

● 674. 最长连续递增序列

在这里插入图片描述

思路:

在这里插入图片描述

代码:

class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp=new int[nums.length];Arrays.fill(dp,1);int res=1;for(int i=1;i<nums.length;i++){if(nums[i]>nums[i-1]){dp[i]=dp[i-1]+1;}res=Math.max(res,dp[i]);}return res;}
}

● 718. 最长重复子数组

在这里插入图片描述

思路:

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

代码一:dp二维数组

class Solution {public int findLength(int[] nums1, int[] nums2) {int res = 0;int[][] dp = new int[nums1.length + 1][nums2.length + 1];for(int i=1;i<=nums1.length;i++){//循环是为了匹配for(int j=1;j<=nums2.length;j++){if(nums1[i-1]==nums2[j-1]){dp[i][j]=dp[i-1][j-1]+1;}res = Math.max(res,dp[i][j]);}}return res;}
}

代码二:滚动数组

在这里插入图片描述
我们可以看出dp[i][j]都是由dp[i - 1][j - 1]推出。那么压缩为一维数组,也就是dp[j]都是由dp[j - 1]推出。

也就是相当于可以把上一层dp[i - 1][j]拷贝到下一层dp[i][j]来继续用。

此时遍历B数组的时候,就要从后向前遍历,这样避免重复覆盖。

// 版本二

class Solution {public int findLength(int[] nums1, int[] nums2) {int res = 0;int[]dp = new int[nums2.length + 1];for(int i=1;i<=nums1.length;i++){//循环是为了匹配for(int j=nums2.length;j>0;j--){if(nums1[i-1]==nums2[j-1]){dp[j]=dp[j-1]+1;}else{dp[j]=0;}res = Math.max(res,dp[j]);}}return res;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/270542.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

从 Language Model 到 Chat Application:对话接口的设计与实现

作者&#xff1a;网隐 RTP-LLM 是阿里巴巴大模型预测团队开发的大模型推理加速引擎&#xff0c;作为一个高性能的大模型推理解决方案&#xff0c;它已被广泛应用于阿里内部。本文从对话接口的设计出发&#xff0c;介绍了业界常见方案&#xff0c;并分享了 RTP-LLM 团队在此场景…

MySQL下实现纯SQL语句的递归查询

需求 有一个部门表&#xff0c;部门表中有一个字段用于定义它的父部门&#xff1b; 在实际业务中有一个『部门中心』的业务&#xff1b; 比如采购单&#xff0c;我们需要显示本部门及子部门的采购单显示出来。 结构 数据如下&#xff1a; 实现方式如下&#xff1a; WITH RECUR…

Vue点击切换组件颜色

例如我有一个这样的组件&#xff0c;我希望在点击组件之后由蓝色变成橙色 先把原来的代码附上(简化掉了叉号&#xff09;&#xff1a; <div v-for"(item, index) in words" :key"index" class"scrollbar-demo-item"><span>{{ item …

Unreal 5打开Windows虚拟键盘的权限问题

可以通过以下代码打开Windows虚拟键盘 void UMouseSimulatorBPLibrary::ShowVirtualKeyboard() {TCHAR* OskPath L"C:\\Program Files\\Common Files\\microsoft shared\\ink\\TabTip.exe";if (!FPaths::FileExists(OskPath)){OskPath L"C:\\windows\\system…

比较 2 名无人机驾驶员:借助分析飞得更高

近年来&#xff0c;越来越多的政府和执法机构使用无人机从空中鸟瞰。为了高效执行任务&#xff0c;无人机必须能够快速机动到预定目标。快速机动使它们能够在复杂的环境中航行&#xff0c;并高效地完成任务。成为认证的无人机驾驶员的要求因国家/地区而异&#xff0c;但都要求您…

数字人民币钱包(二)

文章目录 前言一 什么是数字人民币钱包&#xff1f;二 怎么开通数字人民币钱包&#xff1f;三 数字人民币钱包有哪些&#xff1f;四 数字人民币钱包升级 前言 上篇文章梳理了什么是数字人民币&#xff0c;及其特征和相关概念&#xff0c;这篇文章来整理下数字人民币钱包。数字人…

Redis线程模型解析

引言 Redis是一个高性能的键值对&#xff08;key-value&#xff09;内存数据库&#xff0c;以其卓越的读写速度和灵活的数据类型而广受欢迎。在Redis 6.0之前的版本中&#xff0c;它采用的是一种独特的单线程模型来处理客户端的请求。尽管单线程在概念上似乎限制了其扩展性和并…

【笔记】Android ServiceStateTracker 网络状态变化逻辑及SPN更新影响

业务简介 在网络状态变化的时候&#xff08;数据或WiFi&#xff09;&#xff0c;会更新SPN。 基于Android U的代码分析。 分类&#xff1a;SPN Data_Dic-的博客-CSDN博客 功能逻辑 状态说明 飞行模式下注册上WFC的话&#xff0c;注册状态MD上报 regState: NOT_REG_MT_NOT…

【注意】宽泛负载!

放大器输出摆幅会限制可测量的负载电流范围。例如&#xff0c;从 100mV 至 4.9V 的输出摆幅相当于频程约 15 倍的线性输出范围。那么如果要测量 30 倍频程的负载电流&#xff0c;应该怎么做&#xff1f;调节增益&#xff01; 在TIE2E 论坛上为客户提供支持时&#xff0c;我遇到…

CUDA学习笔记05:卷积(sobel)

参考资料 CUDA编程模型系列四(卷积 or sobel边缘检测)_哔哩哔哩_bilibili 强推 ! ! 代码片段 主函数: #include <stdio.h> #include <iostream> #include <math.h> #include <opencv2/opencv.hpp> #include <opencv2/core.hpp> #include &l…

Java设计模式:建造者模式之经典与流式的三种实现(四)

本文将深入探讨Java中建造者模式的两种实现方式&#xff1a;经典建造者与流式建造者。建造者模式是一种创建型设计模式&#xff0c;它允许你构建复杂对象的步骤分解&#xff0c;使得对象的创建过程更加清晰和灵活。我们将通过示例代码详细解释这两种实现方式&#xff0c;并分析…

十:套接字和标准I/O,以及分离I/O流

1 标准I/O函数的优点 C语言标准IO整理 1.1 标准I/O函数的两个优点 标准I/O函数具有良好的移植性。 标准I/O函数可以利用缓冲提高性能 从图中可以看出&#xff0c;使用标准I/O函数传输数据时&#xff0c;经过两个缓冲。例如&#xff0c;使用fputs函数传输字符串 “Hello” 时…

安卓游戏开发之图形渲染技术优劣分析

一、引言 随着移动设备的普及和性能的提升&#xff0c;安卓游戏开发已经成为一个热门领域。在安卓游戏开发中&#xff0c;图形渲染技术是关键的一环。本文将对安卓游戏开发中常用的图形渲染技术进行分析&#xff0c;比较它们的优劣&#xff0c;并探讨它们在不同应用场景下的适用…

关于 selinux 规则

1. 查看selinux状态 SELinux的状态&#xff1a; enforcing&#xff1a;强制&#xff0c;每个受限的进程都必然受限 permissive&#xff1a;允许&#xff0c;每个受限的进程违规操作不会被禁止&#xff0c;但会被记录于审计日志 disabled&#xff1a;禁用 相关命令&#xf…

manjaro 安装 wps 教程

内核: Linux 6.6.16.2 wps-office版本&#xff1a; 11.10.11719-1 本文仅作为参考使用, 如果以上版本差别较大不建议参考 安装wps主体 yay -S wps-office 安装wps字体 &#xff08;如果下载未成功看下面的方法&#xff09; yay -S ttf-waps-fonts 安装wps中文语言 yay …

upload-Labs靶场“11-15”关通关教程

君衍. 一、第十一关 %00截断GET上传1、源码分析2、%00截断GET上传 二、第十二关 %00截断POST上传1、源码分析2、%00截断POST上传 三、第十三关 文件头检测绕过1、源码分析2、文件头检测绕过 四、第十四关 图片检测绕过上传1、源码分析2、图片马绕过上传 五、第十五关 图片检测绕…

mysql学习笔记8——常用5个内置方法

1count 对查询内容进行计数&#xff0c;并返回结果 2as as可以将查询出来结果赋予新名字 3sum sum可以查询某字段特定条件下的和值 4concat concat可以将多列数据合并成一列&#xff0c;只要concat&#xff08;&#xff09;即可 5group_concat group_concat可以把多列…

Docker的镜像操作

目录 镜像的操作(**开头为常用请留意) 镜像查找 **拉取镜像 **推送镜像 **查看镜像 **修改镜像名称 **查看镜像的详细信息 ​编辑 删除镜像 查看所有镜像ID 删除全部镜像 **查看镜像的操作历史 镜像迁移 镜像打包 远程发送镜像(需要先打包) 本地镜像tar包恢复 镜像过…

【YOLO v5 v7 v8 v9小目标改进】辅助超推理SAHI:分而治之,解决高分辨率图像中小物体检测的问题

辅助超推理SAHI&#xff1a;分而治之&#xff0c;解决高分辨率图像中小物体检测的问题 设计思路结构小目标涨点YOLO v5 魔改YOLO v7 魔改YOLO v8 魔改YOLO v9 魔改 论文&#xff1a;https://arxiv.org/pdf/2202.06934.pdf 代码&#xff1a;https://github.com/obss/sahi 设计思…

文件MD5校验码的安全性及重要性

title: 文件MD5校验码的安全性及重要性 date: 2024/3/6 18:13:20 updated: 2024/3/6 18:13:20 tags: MD5原理文件校验下载验证数据库一致性安全性保障计算方法MD5安全防护 文件MD5&#xff08;Message Digest Algorithm 5&#xff09;是一种常用的哈希算法&#xff0c;用于验证…