Day46 300最长递增子序列 674最长连续递增子序列 718最长重复子数组 1143最长公共子序列

300 最长递增子序列

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

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

本题利用两个循环,外层循环 i 和内层循环 j,dp【j】表示 i 之内最长递增子序列长度,如果nums【i】> nums【j】, 那么就让dp【i】等于前面的最长长度加上1:

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        int result = 0;
        for (int i = 1; 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 最长连续递增子序列

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

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

 本题要求连续,所以只需要和前一个数值比就可以:

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

 718. 最长重复子数组

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

本题dp数组的定义是以i-1和j-1为结尾的两个数组的最大重复长度,选择减一就是为了初始化边界条件时不用做特殊处理,直接全部初始化为0即可

根据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;

根据递推公式可以看出,遍历i 和 j 要从1开始!

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;
                }
                if (dp[i][j] > result) result = dp[i][j];
            }
        }
        return result;
    }
};

1143 最长公共子序列

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

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

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

若这两个字符串没有公共子序列,则返回 0。

本体与上一题不同的一点就是不要求连续,同时不需要result,因为长度是不断累加的,后面的序列一定包含了前面的序列:

主要就是两大情况: text1[i - 1] 与 text2[j - 1]相同,text1[i - 1] 与 text2[j - 1]不相同

如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的。

即:dp[i][j] = max(dp[i - 1][j], 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 = 1; i <= text1.size(); i++) {
            for (int j = 1; j <= text2.size(); j++) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

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

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

相关文章

Kafka 入门笔记

课程地址 概述 定义 Kafka 是一个分布式的基于发布/订阅模式的消息队列&#xff08;MQ&#xff09; 发布/订阅&#xff1a;消息的发布者不会将消息直接发送给特定的订阅者&#xff0c;而是将发布的消息分为不同的类别&#xff0c;订阅者只接受感兴趣的消息 消息队列 消息队…

【北邮鲁鹏老师计算机视觉课程笔记】04 fitting 拟合

【北邮鲁鹏老师计算机视觉课程笔记】04 fitting 拟合 1 拟合的任务 如何从边缘找出真正的线&#xff1f; 存在问题 ①噪声 ②外点、离群点 ③缺失数据 2 最小二乘 存在的问题 3 全最小二乘 度量的是点到直线的距离而不是点在y方向到直线的距离 提示&#xff1a;点到直线的…

【北邮鲁鹏老师计算机视觉课程笔记】05 Hough 霍夫变换

【北邮鲁鹏老师计算机视觉课程笔记】05 Hough 霍夫变换 1 投票策略 考虑到外点率太高 ①让直线上的每一点投票 ②希望噪声点不要给具体的任何模型投票&#xff0c;即噪声点不会有一致性的答案 ③即使被遮挡了&#xff0c;也能把直线找出来 参数空间离散化 直线相当于就是m,b两…

vue核心技术(二)

◆ 指令补充 指令修饰符 通过 "." 指明一些指令 后缀&#xff0c;不同 后缀 封装了不同的处理操作 → 简化代码 v-bind 对于样式控制的增强 为了方便开发者进行样式控制&#xff0c; Vue 扩展了 v-bind 的语法&#xff0c;可以针对 class 类名 和 style 行内样式…

网络安全检查表

《网络攻击检查表》 1.应用安全漏洞 2.弱口令&#xff0c;默认口令 3.服务器互联网暴露 4.操作系统&#xff0c;中间件安全漏洞 5.研发服务器&#xff0c;邮件服务器等安全检查

PySpark(四)PySpark SQL、Catalyst优化器、Spark SQL的执行流程、Spark新特性

目录 PySpark SQL 基础 SparkSession对象 DataFrame入门 DataFrame构建 DataFrame代码风格 DSL SQL SparkSQL Shuffle 分区数目 DataFrame数据写出 Spark UDF Catalyst优化器 Spark SQL的执行流程 Spark新特性 自适应查询(SparkSQL) 动态合并 动态调整Join策略 …

Android---Jetpack Compose学习003

Compose 状态。本文将探索如何在使用 Jetpack Compose 时使用和考虑状态&#xff0c;为此&#xff0c;我们需要构建一个 TODO 应用&#xff0c;我们将构建一个有状态界面&#xff0c;其中会显示可修改的互动式 TODO 列表。 状态的定义。在科学技术中&#xff0c;指物质系统所处…

【XR806开发板试用】轻松连上华为云实现物联网

本文为极术社区XR806试用活动文章。 一.开始 偶然的机会在网上看到了鸿蒙开发板的试用,作为一个"老鸿蒙"岂能放弃这个机会,报名之后不出意料地得到了使用名额,在此感谢极术社区. 收到开发板之后其实还有点失望了,就那么一个小小的核心板,其他啥也没有,连一根数据线…

图灵日记--MapSet字符串常量池反射枚举Lambda表达式泛型

目录 搜索树概念实现性能分析和 java 类集的关系 搜索概念及场景模型 Map的使用Map常用方法 Set的说明常见方法说明 哈希表冲突-避免-负载因子调节冲突-解决-闭散列冲突-解决-开散列/哈希桶冲突严重时的解决办法 实现和 java 类集的关系 字符串常量池String对象创建intern方法 …

MongoDB 与 mongo-express docker 安装

MongoDB 和 mongo-express 与 MySQL 不同&#xff0c;MongoDB 为 NoSQL 数据库&#xff0c;MongoDB 中没有 table &#xff0c;schema 概念&#xff0c;取而代之的 collection&#xff0c;其中 collection 存储的为 BSON 格式&#xff0c;是一种类似于 JSON 的用于存储 k-v 键…

每日五道java面试题之java基础篇(五)

第一题. final、finally、finalize 的区别&#xff1f; final ⽤于修饰变量、⽅法和类&#xff1a;final 修饰的类不可被继承&#xff1b;修饰的⽅法不可被重写&#xff1b;修饰的变量不可变。finally 作为异常处理的⼀部分&#xff0c;它只能在 try/catch 语句中&#xff0c;…

PyTorch深度学习实战(26)——多对象实例分割

PyTorch深度学习实战&#xff08;26&#xff09;——多对象实例分割 0. 前言1. 获取并准备数据2. 使用 Detectron2 训练实例分割模型3. 对新图像进行推断小结系列链接 0. 前言 我们已经学习了多种图像分割算法&#xff0c;在本节中&#xff0c;我们将学习如何使用 Detectron2 …

Netty Review - NioEventLoopGroup源码解析

文章目录 概述类继承关系源码分析小结 概述 EventLoopGroup bossGroup new NioEventLoopGroup(1); EventLoopGroup workerGroup new NioEventLoopGroup();这段代码是在使用Netty框架时常见的用法&#xff0c;用于创建两个不同的EventLoopGroup实例&#xff0c;一个用于处理连…

【计算几何】确定两条连续线段向左转还是向右转

确定两条连续线段向左转还是向右转 目录 一、说明二、算法2.1 两点的叉积2.2 两个段的叉积 三、旋转方向判别3.1 左转3.2 右转3.3 共线判别 一、说明 如果是作图&#xff0c;或者是判别小车轨迹。为了直观地了解&#xff0c;从当前点到下一个点过程中&#xff0c;什么是左转、…

树莓派4B(Raspberry Pi 4B)使用docker搭建阿里巴巴sentinel服务

树莓派4B&#xff08;Raspberry Pi 4B&#xff09;使用docker搭建阿里巴巴sentinel服务 由于国内访问不了docker hub&#xff0c;而国内镜像仓库又没有适配树莓派ARM架构的sentinel镜像&#xff0c;所以我们只能退而求其次——自己动手构建镜像。本文基于Ubuntu&#xff0c;Jav…

springboot169基于vue的工厂车间管理系统的设计

基于VUE的工厂车间管理系统设计与实现 摘 要 社会发展日新月异&#xff0c;用计算机应用实现数据管理功能已经算是很完善的了&#xff0c;但是随着移动互联网的到来&#xff0c;处理信息不再受制于地理位置的限制&#xff0c;处理信息及时高效&#xff0c;备受人们的喜爱。本…

书生谱语-大语言模型测试demo

课程内容简介 1.作业 demo1 demo2 demo3 demo4

Makefile编译原理 make 中的路径搜索_1

一.make中的路径搜索 问题&#xff1a;在实际的工程项目中&#xff0c;所有的源文件和头文件都放在同一个文件夹中吗&#xff1f; 实验1 &#xff1a; VPATH 引子 mhrubuntu:~/work/makefile1/17$ ll total 28 drwxrwxr-x 4 mhr mhr 4096 Apr 22 00:46 ./ drwxrwxr-x 7 mhr m…

《UE5_C++多人TPS完整教程》学习笔记10 ——《P11 设置加入游戏会话(Setup for Joining Sessions)》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P11 设置加入游戏会话&#xff08;Setup for Joining Sessions&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&…

Python远程控制工具的使用

本节我们对所编写的远程控制工具的功能进行测试。首先开启主控端程序&#xff0c; 如下所示&#xff1a; 接下来打开被控端程序。当被控端打开时&#xff0c;主控端会收到被控端的连接请 求。 开启被控端程序&#xff1a; 主控端接收到连接请求并显示被控端主机的信息&#xff…