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

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

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

300.最长递增子序列

题目介绍

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]
输出:4
解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

输入:nums = [0,1,0,3,2,3]
输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]
输出:1

思路解析

本题的一个难点在于子序列可以不连续,那么我们如何能够确定这个子序列呢?

动规五部曲

  1. 确定dp数组及其下标含义

    dp[i]:表示以第i个元素为结尾的严格递增子序列(必须包括第i个)

  2. 递推公式

    for (int j = 0; j < i; j++) { //[0,j]+i部分的区域j、i必取if (nums[i] > nums[j])dp[i] = Integer.max(dp[i], dp[j] + 1);
    }
    

    这里的关键之处,要遍历以下标j为结尾的前区间,如此循环遍历,最终即可得到以下标i结尾的最长严格子序列。

    结果不是最后一位dp数值,所以我们需要记录过程中的最大值

  3. 初始化dp数组

    Arrays.fill(dp,1);
    

    每个位置保底为1,对应它本身

  4. 确定遍历顺序

    正序遍历即可

  5. 打印dp数组检验

本题关键要确定dp数组及其下标含义,还要想到循环遍历得到结果,复杂度O(n2)O(n^2)O(n2)

class Solution {int result = 1;public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];//以第i个元素为结尾的最长严格递增子序列Arrays.fill(dp,1);for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) { //[0,j]+i部分的区域j、i必取if (nums[i] > nums[j])dp[i] = Integer.max(dp[i], dp[j] + 1);}result = Integer.max(dp[i], result);}return result;}
}

674. 最长连续递增序列

题目介绍

给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。

连续递增的子序列 可以由两个下标 lrl < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1:

输入:nums = [1,3,5,4,7]
输出:3
解释:最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。 

示例 2:

输入:nums = [2,2,2,2,2]
输出:1
解释:最长连续递增序列是 [2], 长度为1。

个人思路

本题相比于上一题简单不少,因为它有个连续的限制,我们不需要再遍历就可以直接确定dp数组的每个元素

直接上代码了

class Solution {public int findLengthOfLCIS(int[] nums) {int result = 1;int[] dp = new int[nums.length];dp[0] = 1;for (int i = 1; i < nums.length; i++) {dp[i] = nums[i] > nums[i - 1] ? dp[i - 1] + 1 : 1;result = Integer.max(result, dp[i]);}return result;}
}

718. 最长重复子数组

题目介绍

给两个整数数组 nums1nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度

示例 1:

输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3,2,1] 。

示例 2:

输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出:5

个人思路

本题相较于前两题难点在于,这里给了两个数组,所以我们考虑使用二维dp数组来记录一些中间状态。注意到本题要求,连续子序列,所以这道题其实就是上一题的二维升级版

不难得出递推公式:dp[i][j] = nums1[i] == nums2[j] ? dp[i - 1][j - 1] + 1 : 0;

由此可以推出初始化操作,必须把0下标位置初始化好,避免越界问题

动规五部曲

  1. 确定dp数组及其下标含义

    int[][] dp = new int[nums1.length][nums2.length];
    

    dp[i][j]表示下标[i]、[j]位置为结尾的两子串符合条件的最大长度

  2. 递推公式的确定

    dp[i][j] = nums1[i] == nums2[j] ? dp[i - 1][j - 1] + 1 : 0;
    
  3. 初始化dp数组

    for (int i = 0; i < nums1.length; i++) {dp[i][0] = nums1[i] == nums2[0] ? 1 : 0;result = Integer.max(result, dp[i][0]);
    }
    for (int i = 0; i < nums2.length; i++) {dp[0][i] = nums1[0] == nums2[i] ? 1 : 0;result = Integer.max(result, dp[0][i]);
    }
    

    由递推公式推出

  4. 确定遍历顺序

    两层for循环,正序遍历即可

  5. 打印dp数组检验

class Solution {public int findLength(int[] nums1, int[] nums2) {int result = 0;int[][] dp = new int[nums1.length][nums2.length];//以i.j为结尾的符合条件的子数组最长长度for (int i = 0; i < nums1.length; i++) {dp[i][0] = nums1[i] == nums2[0] ? 1 : 0;result = Integer.max(result, dp[i][0]);}for (int i = 0; i < nums2.length; i++) {dp[0][i] = nums1[0] == nums2[i] ? 1 : 0;result = Integer.max(result, dp[0][i]);}for (int i = 1; i < nums1.length; i++) {for (int j = 1; j < nums2.length; j++) {dp[i][j] = nums1[i] == nums2[j] ? dp[i - 1][j - 1] + 1 : 0;result = Integer.max(result, dp[i][j]);}}return result;}
}

相关文章:

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

代码随想录算法训练营第52天 || 300.最长递增子序列 || 674. 最长连续递增序列 || 718. 最长重复子数组 300.最长递增子序列 题目介绍 给你一个整数数组 nums &#xff0c;找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列&#xff0c;删除&#xff08;或…...

gitblit 安装使用

1 安装服务端 简而言之&#xff1a;需要安装 java&#xff0c;gitblit&#xff0c; git 三个软件 Windows 10环境使用Gitblit搭建局域网Git服务器 前言 安装Java并配置环境安装gitblit并配置启动gitblit为windows服务使用gitblit创建repository并管理用户 1.1 安装Java并配…...

使用 TensorFlow、Keras-OCR 和 OpenCV 从技术图纸中获取信息

简单介绍输入是技术绘图图像。对象检测模型获取图像后对其进行分类&#xff0c;找到边界框&#xff0c;分配维度&#xff0c;计算属性。示例图像&#xff08;输入&#xff09;分类后&#xff0c;找到“IPN”部分。之后&#xff0c;它计算属性&#xff0c;例如惯性矩。它适用于不…...

ESP32设备驱动-GUVA-S12SD紫外线检测传感器驱动

GUVA-S12SD紫外线检测传感器驱动 文章目录 GUVA-S12SD紫外线检测传感器驱动1、GUVA-S12SD介绍2、硬件准备3、软件准备4、驱动实现1、GUVA-S12SD介绍 GUVA-S12SD 紫外线传感器芯片适用于检测太阳光中的紫外线辐射。 它可用于任何需要监控紫外线量的应用,并且可以简单地连接到任…...

WIN7下 program file 权限不足?咋整?!!

在WIN7下对Program Files目录的权限问题 [问题点数&#xff1a;40分&#xff0c;结帖人mysunck] 大部分人说要使用manifest&#xff0c;但是其中一个人说&#xff1a; “安装程序要求管理员很正常&#xff0c;你的程序可以在programfiles,但用户数据不能放那里&#xff0c;因…...

119.(leaflet篇)文字碰撞

听老人家说:多看美女会长寿 地图之家总目录(订阅之前建议先查看该博客) 文章末尾处提供保证可运行完整代码包,运行如有问题,可“私信”博主。 效果如下所示: 下面献上完整代码,代码重要位置会做相应解释 <!DOCTYPE html> <html>...

cuda编程以及GPU基本知识

目录CPU与GPU的基本知识CPU特点GPU特点GPU vs. CPU什么样的问题适合GPU&#xff1f;GPU编程CUDA编程并行计算的整体流程CUDA编程术语&#xff1a;硬件CUDA编程术语&#xff1a;内存模型CUDA编程术语&#xff1a;软件线程块&#xff08;Thread Block&#xff09;网格&#xff08…...

Python 机器学习/深度学习/算法专栏 - 导读目录

目录 一.简介 二.机器学习 三.深度学习 四.数据结构与算法 五.日常工具 一.简介 Python 机器学习、深度学习、算法主要是博主从研究生到工作期间接触的一些机器学习、深度学习以及一些算法的实现的记录&#xff0c;从早期的 LR、SVM 到后期的 Deep&#xff0c;从学习到工…...

Springboot怎么实现restfult风格Api接口

前言在最近的一次技术评审会议上&#xff0c;听到有同事发言说&#xff1a;“我们的项目采用restful风格的接口设计&#xff0c;开发效率更高&#xff0c;接口扩展性更好...”&#xff0c;当我听到开头第一句&#xff0c;我脑子里就开始冒问号&#xff1a;项目里的接口用到的是…...

Jetpack Compose 深入探索系列六:Compose runtime 高级用例

Compose runtime vs Compose UI 在深入讨论之前&#xff0c;非常重要的一点是要区分 Compose UI 和 Compose runtime。Compose UI 是 Android 的新 UI 工具包&#xff0c;具有 LayoutNodes 的树形结构&#xff0c;它们稍后在画布上绘制其内容。Compose runtime 提供底层机制和…...

23.3.2 Codeforces Round #834 (Div. 3) A~E

FG明天补 A-Yes-Yes? 题面翻译 给定 ttt 个字符串&#xff0c;请判定这些字符串是否分别是 YesYesYesYes…\texttt{YesYesYesYes\dots}YesYesYesYes… 的子串。是则输出 YES&#xff0c;否则输出 NO&#xff08;YES 和 NO 大小写不定&#xff09;。 Translated by JYqwq …...

一次失败的面试经历:我只想找个工作,你却用面试题羞辱我!

金三银四近在咫尺&#xff0c;即将又是一波求职月&#xff0c;面对跳槽的高峰期&#xff0c;很多软件测试人员都希望能拿一个满意的高薪offer&#xff0c;但是随着招聘职位的不断增多&#xff0c;面试的难度也随之加大&#xff0c;而面试官更是会择优录取小王最近为面试已经焦头…...

java版工程管理系统 Spring Cloud+Spring Boot+Mybatis实现工程管理系统源码

java版工程管理系统Spring CloudSpring BootMybatis实现工程管理系统 工程项目各模块及其功能点清单 一、系统管理 1、数据字典&#xff1a;实现对数据字典标签的增删改查操作 2、编码管理&#xff1a;实现对系统编码的增删改查操作 3、用户管理&#xff1a;管理和…...

附录3-大事件项目后端-项目准备工作,config.js,一些库的简易用法,main.js

目录 1 一些注意 2 创建数据库 3 项目结构 4 配置文件 config.js 5 参数规则包 hapi/joi与escook/express-joi 5.1 安装 5.2 文档中的demo 5.2.1 定义规则 5.2.2 使用规则 5.3 项目中的使用 5.3.1 定义信息规则 5.3.2 使用规则 6 密码加密包 bcrypt.…...

并发编程-线程

并发编程-线程 一个进程是操作系统中运行的一个任务&#xff0c;进程独立拥有CPU、内存等资源一个线程是一个进程中运行的一个任务&#xff0c;线程之间共享CPU、内存等资源&#xff0c;进程里的每一个任务都是线程。 线程创建 创建线程&#xff1a;使用threading模块中的Th…...

图解LeetCode——剑指 Offer 34. 二叉树中和为某一值的路径

一、题目 给你二叉树的根节点 root 和一个整数目标和 targetSum &#xff0c;找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。 二、示例 2.1> 示例 1&#xff1a; 【输入】root [5,4,8,11,null,13,4,7,2,null,null,5,1], t…...

使用Python免费试用最新Openai API

一、背景介绍 3月2日凌晨&#xff0c;OpenAI放出了真正的ChatGPT API&#xff0c;不是背后的GPT-3.5大模型&#xff0c;是ChatGPT的本体模型&#xff01;ChatGPT API价格为1k tokens/$0.002&#xff0c;等于每输出100万个单词&#xff0c;价格才2.7美金&#xff08;约18元人民…...

04、启动 SVN 服务器端程序

启动 SVN 服务器端程序1 概述2 用命令行单项目启动2.1 采用 svnserve 命令2.2 验证服务是否启动2.3 命令行方式的缺陷3 注册Windows服务3.1 注册服务的命令3.2 命令说明3.3 启动服务1 概述 SVN 服务器和 Tomcat 服务器&#xff0c;Nexus 服务器一样, 必须处于运行状态才能响应…...

jsp船舶引航计费网站Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 JSP船舶引航计费网站是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql5.0&…...

Allegro如何画半圆形的线操作指导

Allegro如何画半圆形的线操作指导 在用Allegro设计PCB的时候,在某些应用场合会需要画半圆形,如下图 如何画半圆形,具体操作如下 点击Add点击Arc w/Radius...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

工业安全零事故的智能守护者:一体化AI智能安防平台

前言&#xff1a; 通过AI视觉技术&#xff0c;为船厂提供全面的安全监控解决方案&#xff0c;涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面&#xff0c;能够实现对应负责人反馈机制&#xff0c;并最终实现数据的统计报表。提升船厂…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

鸿蒙(HarmonyOS5)实现跳一跳小游戏

下面我将介绍如何使用鸿蒙的ArkUI框架&#xff0c;实现一个简单的跳一跳小游戏。 1. 项目结构 src/main/ets/ ├── MainAbility │ ├── pages │ │ ├── Index.ets // 主页面 │ │ └── GamePage.ets // 游戏页面 │ └── model │ …...

C++11 constexpr和字面类型:从入门到精通

文章目录 引言一、constexpr的基本概念与使用1.1 constexpr的定义与作用1.2 constexpr变量1.3 constexpr函数1.4 constexpr在类构造函数中的应用1.5 constexpr的优势 二、字面类型的基本概念与使用2.1 字面类型的定义与作用2.2 字面类型的应用场景2.2.1 常量定义2.2.2 模板参数…...

C# WPF 左右布局实现学习笔记(1)

开发流程视频&#xff1a; https://www.youtube.com/watch?vCkHyDYeImjY&ab_channelC%23DesignPro Git源码&#xff1a; GitHub - CSharpDesignPro/Page-Navigation-using-MVVM: WPF - Page Navigation using MVVM 1. 新建工程 新建WPF应用&#xff08;.NET Framework) 2.…...