算法学习——LeetCode力扣动态规划篇8(300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组、1143. 最长公共子序列)

算法学习——LeetCode力扣动态规划篇8

在这里插入图片描述

300. 最长递增子序列

300. 最长递增子序列 - 力扣(LeetCode)

描述

给你一个整数数组 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 <= nums.length <= 2500
-104 <= nums[i] <= 104

代码解析

动态规划
  • dp[i]的定义
    dp[i]表示i之前包括i的以nums[i]结尾最长上升子序列的长度

  • 状态转移方程
    位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
    所以:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
    注意这里不是要dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值。

  • dp[i]的初始化
    每一个i,对应的dp[i](即最长上升子序列)起始大小至少都是1.

  • 确定遍历顺序
    dp[i] 是有0到i-1各个位置的最长升序子序列 推导而来,那么遍历i一定是从前向后遍历。
    j其实就是0到i-1,遍历i的循环在外层,遍历j则在内层

class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(nums.size() ==1 ) return 1;vector<int> dp(nums.size() , 1);int result = 0;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) ;}if(dp[i] > result) result = dp[i];}return result;}
};

674. 最长连续递增序列

674. 最长连续递增序列 - 力扣(LeetCode)

描述

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

连续递增的子序列 可以由两个下标 l 和 r(l < 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。

提示

1 <= nums.length <= 104
-109 <= nums[i] <= 109

代码解析

动态规划
  • dp数组定义
    i点前连续递增序列的个数
  • dp的迭代
    if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;
    当i的值大于i-1,dp[i] = dp[i-1] + 1
  • dp初始化
    全都设置为1
    自己认为是一个元素的递增数组
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if(nums.size()==1) return 1;vector<int> dp(nums.size() ,1);int result = 0;for(int i=1 ; i<nums.size();i++){if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;if(dp[i]>result) result = dp[i];}return result;}
};

718. 最长重复子数组

718. 最长重复子数组 - 力扣(LeetCode)

描述

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例

示例 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

提示

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100

代码解析

动态规划
  • 确定dp数组含义
    dp[i][j] :以下标i - 1为结尾的A(A的第i个元素),和以下标j - 1为结尾的B(B的第j个元素),最长重复子数组长度为dp[i][j]。
  • 确定递推公式
    根据dp[i][j]的定义,dp[i][j]的状态只能由dp[i - 1][j - 1]推导出来。
    即当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
  • 初始化
    dp[0][0]、dp[i][0]、dp[0][j]都为0,因为下标为0意味着没有元素进行匹配,因此匹配的个数也是0。从dp[i][j]开始有意义,即nums1和nums2都拿出了一个元素
class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {//dp数组下标i和j意味着第几个元素,因此长度+1vector<vector<int>>  dp(nums1.size()+1 , vector<int>(nums2.size()+1,0));int result = 0 ;for(int i=0 ; i<nums1.size() ;i++){for(int j=0 ;j<nums2.size();j++){if(nums1[i] == nums2[j])dp[i+1][j+1] = dp[i][j]+1;if(dp[i+1][j+1] > result) result = dp[i+1][j+1];}}// for(int i=0 ; i<=nums1.size() ;i++)// {//     for(int j=0 ;j<=nums2.size();j++)//     {//         if(dp[i][j] > result) result = dp[i][j];//          cout<<dp[i][j]<<' ';//     }//      cout<<endl;// }return result;}
};

1143. 最长公共子序列

1143. 最长公共子序列 - 力扣(LeetCode)

描述

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。

例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例

示例 1:

输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace” ,它的长度为 3 。

示例 2:

输入:text1 = “abc”, text2 = “abc”
输出:3
解释:最长公共子序列是 “abc” ,它的长度为 3 。

示例 3:

输入:text1 = “abc”, text2 = “def”
输出:0
解释:两个字符串没有公共子序列,返回 0 。

提示

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

代码解析

  • dp数组含义
    dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j](即前i个字符和前j个字符匹配)
  • 递推公式
    • 当text1[i] == text2[j]
      当前匹配的i和j是相同的字符,dp[i+1][j+1] = dp[i][j] + 1;
      dp应该是不包括第i+1 和第j+1字符之前匹配成功个数+1
      要把i+1和j+1让出来。
    • 当text1[i] != text2[j]
      当前匹配的i和j是不同的字符,dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);
      dp为包括i+1字符或者包括j+1字符的最大值
    • 当匹配成功时
      为什么不是 dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1])+1;
      因为会造成一个字母匹配多次
      例如 text1中有一个b,text2中有两个b
      在i+1为text1的b,j+1为text2中第二个b时:
      max(dp[i+1][j],dp[i][j+1])包含和text2中第一个b匹配,+1是和第二个b匹配。
      则造成了text1中字母b与text2中两个b分别匹配。
      因此应该是dp[i+1][j+1] = dp[i][j] + 1,这样让开要匹配的字符
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()+1 , vector<int>(text2.size()+1 ,0) );for(int i=0 ;i<text1.size();i++){for(int j=0; j<text2.size();j++){if(text1[i] == text2[j])dp[i+1][j+1] = dp[i][j] + 1; elsedp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);}}//  for(int i=0 ;i<=text1.size();i++)// {//     for(int j=0; j<=text2.size();j++)//     {//         cout<<dp[i][j]<<' ';//     }//     cout<<endl;// }return dp[text1.size()][text2.size()];}
};

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

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

相关文章

Flutter开发之图片选择器

使用FLutter开发了一个图片选择的组件&#xff0c;功能如下&#xff1a; 1、支持设置最大可选图片的个数&#xff1b; 2、根据选择的图片个数自适应容器组件的高度&#xff1b; 3、可设置容器的最大高度&#xff1b; 4、支持点击放大和删除功能&#xff1b; 具体效果如下 …

Java多线程实战-从零手搓一个简易线程池(三)线程工厂,核心线程与非核心线程逻辑实现

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java全栈-专栏 &#x1f3f7;️本系列源码仓库&#xff1a;多线程并发编程学习的多个代码片段(github) &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正…

漂亮哇塞的可视化大屏页面该如何设计?

要提升可视化界面的设计美观度&#xff0c;可以从以下几个方面入手&#xff1a; 使用高质量的图片和素材&#xff1a;使用高质量的图片和素材可以让界面更加美观。可以选择高清晰度的图片和素材&#xff0c;使得整个界面的质感更加高端。突出重点&#xff1a;在界面设计中&…

《QT实用小工具·八》数据库通用翻页类

1、概述 源码放在文章末尾 该项目实现数据库通用翻页类&#xff0c;主要包含如下功能&#xff1a; 1:自动按照设定的每页多少行数据分页 2:只需要传入表名/字段集合/每页行数/翻页指示按钮/文字指示标签 3:提供公共静态方法绑定字段数据到下拉框 4:建议条件字段用数字类型的主…

debian的使用笔记

1. XP风格任务栏 安装 debian-live-12.5.0-amd64-xfce.iso 后&#xff0c;把下面的任务栏删除&#xff0c;把上面的任务栏移到下面&#xff0c;然后设置如下选项 2. 命令自动补全 sudo apt install bash-completion 3. 找不到命令 sudo apt install command-not-found sudo…

RISC-V GNU Toolchain 工具链安装问题解决(含 stdio.h 问题解决)

我的安装过程主要参照 riscv-collab/riscv-gnu-toolchain 的官方 Readme 和这位佬的博客&#xff1a;RSIC-V工具链介绍及其安装教程 - 风正豪 &#xff08;大佬的博客写的非常详细&#xff0c;唯一不足就是 sudo make linux -jxx 是全部小写。&#xff09; 工具链前前后后我装了…

论文阅读RangeDet: In Defense of Range View for LiDAR-based 3D Object Detection

文章目录 RangeDet: In Defense of Range View for LiDAR-based 3D Object Detection问题笛卡尔坐标结构图Meta-Kernel Convolution RangeDet: In Defense of Range View for LiDAR-based 3D Object Detection 论文&#xff1a;https://arxiv.org/pdf/2103.10039.pdf 代码&…

栈溢出攻击的软硬件缓解技术

为了防范栈溢出攻击&#xff0c;现代处理器架构&#xff08;如Arm架构&#xff09;具有执行权限。在Armv8-A中&#xff0c;主要的控制是在MMU地址转换表&#xff08;translation tables&#xff09;中的执行权限位。 UXN User (EL0) Execute-never …

SpringBoot+thymeleaf完成视频记忆播放功能

一、背景 1)客户要做一个视频播放功能,要求是系统能够记录观看人员在看视频时能够记录看到了哪个位置,在下次观看视频的时候能够从该位置进行播放。 2)同时,也要能够记录是谁看了视频,看了百分之多少。 说明:由于时间关系和篇幅原因,我们这里只先讨论第一个要求,第…

基于WEB的花卉养殖知识平台的设计与实现|SSM+ Mysql+Java(可运行源码+数据库+LW)植物绿植种植,留言管理,知识科普,新闻数据

本项目包含可运行源码数据库LW&#xff0c;文末可获取本项目的所有资料。 推荐阅读300套最新项目持续更新中..... 最新ssmjava项目文档视频演示可运行源码分享 最新jspjava项目文档视频演示可运行源码分享 最新Spring Boot项目文档视频演示可运行源码分享 2024年56套包含ja…

Android Studio学习5——布局layout与视图view

wrap_content&#xff0c;内容有多大&#xff0c;就有多宽&#xff08;包裹&#xff09; 布局 padding 边框与它自身的内容 margin 控件与控件之间

docker容器环境安装记录(MAC M1)(完善中)

0、背景 在MAC M1中搭建商城项目环境时&#xff0c;采用docker统一管理开发工具&#xff0c;期间碰到了许多环境安装问题&#xff0c;做个总结。 1、安装redis 在宿主机新建redis.conf文件运行创建容器命令&#xff0c;进行容器创建、端口映射、文件挂载、以指定配置文件启动…

【Python面试题收录】Python的深浅拷贝

一、Python的深浅拷贝的区别 在Python中&#xff0c;深拷贝和浅拷贝是两种不同的对象复制机制&#xff0c;它们的主要区别在于如何处理对象内部所包含的可变或不可变类型的子对象。 浅拷贝 是指创建一个新的对象&#xff0c;但它只复制了原对象的第一层内容&#xff0c;也就是说…

Linux|centos7|postgresql数据库主从复制之异步还是同步的问题

前言&#xff1a; postgresql数据库是一个比较先进的中型关系型数据库&#xff0c;原本以为repmgr和基于repmgr的主从复制是挺简单的一个事情&#xff0c;但现实很快就给我教育了&#xff0c;原来postgresql和MySQL一样的&#xff0c;也是有异步或者同步的复制区别的 Postgre…

运放知识点总结

目录 一、运放基础知识 (operational amplifier) 1.由来 2.用途 3.符号 4.内部结构​编辑 5.虚短虚断 二、同相放大电路 &#xff08;Non-inverting Amplifier&#xff09; 三、反相放大电路 (Inverting Amplifier) 四、差分放大电路 (Difference Amplifier) 五、加法…

redis 数据库的安装及使用方法

目录 一 关系数据库与非关系型数据库 &#xff08;一&#xff09;关系型数据库 1&#xff0c;关系型数据库是什么 2&#xff0c;主流的关系型数据库有哪些 3&#xff0c;关系型数据库注意事项 &#xff08;二&#xff09;非关系型数据库 1&#xff0c;非关系型数据库是…

如果在 Ubuntu 系统中两个设备出现两个相同的端口号解决方案

问题描述&#xff1a; 自己的移动机器人在为激光雷达和IMU配置动态指定的端口时&#xff0c;发现激光雷达和深度相机配置的 idVendor 和 idProduct 相同&#xff0c;但是两个设备都具有不同的ttyUSB号&#xff0c;如下图所示 idVendor&#xff1a;代表着设备的生产商ID,由USB设…

EFK(elasticsearch+filebeat+kibana)日志分析平台搭建

本文是记录一下EFK日志平台的搭建过程 项目背景&#xff1a; 此次搭建的日志分析平台主要是采集服务器上的java服务的log日志(输出的日志已经是json格式)&#xff0c;这些日志都已经按照不同环境输出到/home/dev /home/test1 /home/test2 目录下了&#xff0c;按照不同的应…

Mybatis——一对一映射

一对一映射 预置条件 在某网络购物系统中&#xff0c;一个用户只能拥有一个购物车&#xff0c;用户与购物车的关系可以设计为一对一关系 数据库表结构&#xff08;唯一外键关联&#xff09; 创建两个实体类和映射接口 package org.example.demo;import lombok.Data;import …

在flutter中添加video_player【视频播放插件】

添加插件依赖 dependencies:video_player: ^2.8.3插件的用途 在Flutter框架中&#xff0c;video_player 插件是一个专门用于播放视频的插件。它允许开发者在Flutter应用中嵌入视频播放器&#xff0c;并提供了一系列功能来控制和定制视频播放体验。这个插件对于需要在应用中展…