day55 最长递增子序列 最长连续递增子序列 最长重复子数组

题目1  300 最长递增子序列

题目链接 300 最长递增子序列

题意

找到整数数组nums的最长严格递增子序列的长度(子序列并不改变原始的顺序,但是可以删除元素)

动态规划

动规五部曲

1)dp数组及下标i的含义

dp[i] 表示以nums[i]为结尾的最长递增子序列的长度

2)dp数组初始化

根据定义 长度至少是1  dp[i] = 1

3)递推公式

j从0到i-1各个位置的最长升序子序列 + 1 的最大值 

要计算每个当前值dp[i]与现在遍历的nums[j]的长度的大小关系 每一个值都要进行比较

if(nums[i] > nums[j]) dp[i] = max(dp[j]+1,dp[i])

4)遍历顺序

根据递推公式 当前长度依赖于之前的结果  i从小到大遍历 j的遍历顺序无所谓,只要把i-1的范围内的值遍历完就ok

for(i=1;i<nums.size(); i++){

     for(j=0;j<i;j++){

      }

}

5)打印dp数组

代码

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //定义dp数组  初始化
        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[j] + 1, dp[i]);
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};
  • 时间复杂度: O(n^2)
  • 空间复杂度: O(n)

题目2   674 最长连续递增子序列

题目链接  674 最长连续递增序列

题意

找到未排序的整数数组的最长且连续递增的子序列的长度(不能删减元素了)

动态规划

动规五部曲

1)dp数组及下标i的含义

dp[i] 表示以nums[i]为结尾的最长连续递增子序列的长度

2)dp数组初始化

至少包含1个元素  dp[i] = 1

3)递推公式

只比较nums[i]与nums[i-1]即可,这样才可以保证是连续 

不用去比较nums[j]与nums[i] (j是在0到i之间遍历)

if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1

4)遍历顺序

根据递推公式 dp[i]依赖于dp[i-1]  从前往后推导

5)打印dp数组

代码

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        //定义dp数组 初始化
        vector<int> dp(nums.size(), 1);
        int result = 1;  //对于只有1个元素的数组
        for(int i = 1; i < nums.size(); i++){
            if(nums[i] > nums[i-1]) dp[i] = dp[i-1] + 1;
            result = max(result, dp[i]);
        }
        return result;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

题目3  718 最长重复子数组

题目链接  718 最长重复子数组

题意

返回两个整数数组nums1和nums2的公共的最长子数组的长度

动态规划

动规五部曲

1)dp数组及下标i的含义

想到使用二维dp数组可以记录两个字符串的所有比较情况

dp[i][j] 表示以nums1[i-1]结尾的数组和以nums2[j-1]结尾的数组的公共最长子数组的长度

2)dp数组初始化

根据递推公式 初始化第一行第一列

根据dp数组定义 dp[i][0] 与 dp[0][j] 没有意义

根据递推公式 是在上一个基础上加1 应该从0开始往上加 dp[i-1][0] = 0  dp[0][j-1] = 0  其他下标可初始为任意值

3)递推公式

根据dp数组的定义 dp[i][j]以nums1[i-1]结尾 nums2[j-1]结尾  所以比较nums1[i-1]与nums2[j-1]

if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1

4)遍历顺序

遍历2个数组的顺序谁先谁后均可 只要把两个数组遍历完即可

之所以有等号,根据dp数组的定义 dp[i][j]以nums1[i-1]结尾 nums2[j-1]结尾

等号代表 nums1[nums1.size()-1]   nums2[nums2.size()-1]

for(i=1;i<=nums1.size();i++){

   for(j=1;j<=nums2.size();j++){

   }

}

5)打印dp数组

代码

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        //定义dp数组  初始化dp数组
        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;
    }
};
  • 时间复杂度:O(n × m),n 为nums1长度,m为nums2长度
  • 空间复杂度:O(n × m)

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【现代C++】委托构造函数

现代C中的委托构造函数&#xff08;Delegating Constructors&#xff09;是C11引入的特性&#xff0c;它允许一个构造函数调用同一个类中的另一个构造函数&#xff0c;以避免代码重复。这种特性在初始化对象时提高了代码的复用性和清晰性。 1. 基本用法 在同一个类中&#xf…

Harmony鸿蒙南向驱动开发-MMC

MMC&#xff08;MultiMedia Card&#xff09;即多媒体卡&#xff0c;是一种用于固态非易失性存储的小体积大容量的快闪存储卡。 MMC后续泛指一个接口协定&#xff08;一种卡式&#xff09;&#xff0c;能符合这种接口的内存器都可称作MMC储存体。主要包括几个部分&#xff1a;…

似曾相识:面向重复类型故障的可操作故障定位

导读 搜索引擎、在线视频和电子银行等在线服务系统在人们的日常生活中有着越来越重要的作用。但是&#xff0c;由于在线服务系统包含众多有着复杂依赖关系的组件&#xff08;例如服务器、容器和微服务等等&#xff09;&#xff0c;在线服务系统中的故障难以避免&#xff0c;并…

49 样式迁移【李沐动手学深度学习v2课程笔记】

1. 样式迁移&#xff08;Style Transfer) 计算机视觉的应用之一&#xff0c;将样式图片中的样式&#xff08;比如油画风格等&#xff09;迁移到内容图片&#xff08;比如实拍的图片&#xff09;上&#xff0c;得到合成图片 可以理解成为一个滤镜&#xff0c;但相对于滤镜来讲…

leetcode 常考题-动态规划算法-单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。 注意&#xff1a;不要求字典中出现的单词全部都使用&#xff0c;并且字典中的单词可以重复使用。 示例 1&#xff1a; 输入: s "leetcode"…

七分钟,拿下口头offer

shigen坚持更新文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 个人IP&#xff1a;shigen &#x1f9d1;‍&#x1f4bb;&#x1f9d1;‍&#x1f4bb;面2&#xff1a;行了…

每日一题 — 最大连续 1 的个数III

解法一&#xff1a;暴力枚举 先定义left和right双指针&#xff0c;left先固定在起始位置&#xff0c;遍历right当值等于1的时候&#xff0c;直接跳过&#xff0c;等于0的时候&#xff0c;zero计数器加一当zero等于k的时候&#xff0c;就开始记录此时最大长度是多少然后left加一…

做抖店要用到的东西:什么是精选联盟?开通到使用一篇详解!

哈喽~我是电商月月 做抖音小店的新手朋友在翻阅资料时一定接触过精选联盟这个东西 但它到底是干嘛的&#xff1f;如何开通。又是如何使用&#xff01;还没入手的朋友是不知道的 所以&#xff0c;今天我就给大家讲解一下精选联盟的入驻方法&#xff0c;以及在运营时要怎么正确…

蓝桥杯第十届c++大学B组详解

目录 1.组队 2.年号字符 3.数列求值 4.数的分解 5.迷宫 6.特别数的和 7.完全二叉树的权值 8.等差数列 9.后缀表达式 10.灵能传输 1.组队 题目解析&#xff1a;就是在个篮球人中选择这个最大的成绩&#xff0c;每个人只能选择一次不能重复选择。选满5人之后的成绩是最…

企业如何部署有效的防泄密软件策略?

在企业信息化飞速发展的今天&#xff0c;数据泄露的后果可能是灾难性的&#xff0c;不仅会导致经济损失&#xff0c;还可能损害公司的声誉。因此&#xff0c;制定和部署一个全面而有效的防泄密软件策略对于防范这种风险至关重要。策略的目标不仅是阻止外部攻击&#xff0c;更要…

《C++程序设计》阅读笔记【7-堆和拷贝构造函数】

&#x1f308;个人主页&#xff1a;godspeed_lucip &#x1f525; 系列专栏&#xff1a;《C程序设计》阅读笔记 本文对应的PDF源文件请关注微信公众号程序员刘同学&#xff0c;回复C程序设计获取下载链接。 1 堆与拷贝构造函数1.1 概述1.2 分配堆对象1.3 拷贝构造函数1.3.1 默…

多线程(进阶篇小白易懂版)

文章目录 多线程为什么要有多线程多线程案例线程通讯分传主线程通讯主传分关闭线程线程锁 多线程 概念&#xff1a;多线程就是多个线程同时工作的过程&#xff0c;我们可以将线程看作是程序的执行路径&#xff0c;每个线程都定义了一个独特的控制流&#xff0c;用来完成特定的…

DataX 数据库同步部分源码解析

在工作中遇到异构数据库同步的问题,从Oracle数据库同步数据到Postgres&#xff0c;其中的很多数据库表超过百万&#xff0c;并且包含空间字段。经过筛选&#xff0c;选择了开源的DataXDataX Web作为基础框架。DataX 是阿里云的开源产品&#xff0c;大厂的产品值得信赖&#xff…

【JavaWeb】Day39.MySQL概述——数据库设计-DQL(二)

数据库设计-DQL 聚合函数 聚合函数查询就是纵向查询&#xff0c;它是对一列的值进行计算&#xff0c;然后返回一个结果值。&#xff08;将一列数据作为一个整体&#xff0c;进行纵向计算&#xff09; 语法&#xff1a; select 聚合函数(字段列表) from 表名 ; 注意 : 聚合…

LeetCode 热题 100 | 多维动态规划(二)

目录 1 5. 最长回文子串 2 1143. 最长公共子序列 菜鸟做题&#xff0c;语言是 C 1 5. 最长回文子串 核心思想&#xff1a;把总问题拆解为若干子问题。 总问题&#xff1a;从第 i 个字母到第 j 个字母是回文串子问题&#xff1a;从第 i 1 个字母到第 j - 1 个字母是回文…

Obsidian的初步了解、安装及使用

一、为什么是Obsidian&#xff1f; 笔记软件我用的还是比较多了&#xff0c;一开始用有道云笔记&#xff0c;其实我个人觉得有道云笔记还是做的不错的&#xff0c;除了广告多点、功能弱一点、更新慢一点、偶尔收藏会有问题以外还是不错的&#xff0c;免费软件里性价比算是还可…

前端开发中地图定位与距离计算的应用实践

前端开发中地图定位与距离计算的应用实践 在前端开发中&#xff0c;地图功能的应用日益广泛&#xff0c;无论是用户位置的定位、目标距离的计算&#xff0c;还是地址的解析与展示&#xff0c;地图都发挥着不可替代的作用。本文将重点介绍前端开发中实现地图定位、距离计算以及…

windows 系统下全新下载安装 mysql8.0 数据库(详细)

windows 系统下全新下载安装 mysql8.0 数据库&#xff08;详细&#xff09; 段子手168 1、登录官方网站下载&#xff1a; https://dev.mysql.com/downloads/windows/installer/ 2、下载最新版本&#xff0c;一般可能需要注册登录&#xff0c;下载其他历史版本&#xff0c;请…

【LAMMPS学习】八、基础知识(1.3)从一个输入脚本运行多个模拟

8. 基础知识 此部分描述了如何使用 LAMMPS 为用户和开发人员执行各种任务。术语表页面还列出了 MD 术语&#xff0c;以及相应 LAMMPS 手册页的链接。 LAMMPS 源代码分发的 examples 目录中包含的示例输入脚本以及示例脚本页面上突出显示的示例输入脚本还展示了如何设置和运行各…

【智能算法】省时方便,智能算法统计指标——一键运行~

目录 1.常用统计指标2.参数统计检验3.结果展示4.自定义修改测试框架 1.常用统计指标 测试智能算法性能时&#xff0c;常常会用到以下5种常用指标&#xff0c;简单不赘述&#xff1a; 最优值、最差值、均值、中位数、标准差 2.参数统计检验 单纯依靠常用统计指标说服力不足&…