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

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

  • 300.最长递增子序列
    • 解法一:动态规划
  • 674. 最长连续递增序列
    • 解法一:动态规划
    • 解法二:双指针法
  • 718. 最长重复子数组
    • 解法一:动态规划
  • 总结


300.最长递增子序列

教程视频:https://www.bilibili.com/video/BV1ng411J7xP
在这里插入图片描述
在这里插入图片描述

解法一:动态规划

思路:
1、dp[i]含义:表示以nums[i]结尾的最长递增子序列的长度。
2、递推公式:dp[i]=Math.max(dp[j]+1,dp[i]);
3、dp数组初始化:全部初始化为1,dp[i]=1;
4、遍历顺序:外层 i 从前向后遍历,内层 j 正序倒序都可以。
5、打印验证。

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp, 1);
        int result = 1;//因为外层for不是从dp[0]开始遍历,考虑单个元素情况下输出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[j]+1,dp[i]);
                }
            }
            result=Math.max(result,dp[i]);
        }
        return result;
    }
}

674. 最长连续递增序列

教程视频:https://www.bilibili.com/video/BV1bD4y1778v
在这里插入图片描述

解法一:动态规划

思路:
1、dp[i]含义:表示以nums[i]结尾的最长连续递增子序列的长度。
2、递推公式:if(nums[i-1]<nums[i]) dp[i]=dp[i-1]+1;
3、dp数组初始化:全部初始化为1,dp[i]=1;
4、遍历顺序:外层 i 正序遍历,内层 无需遍历。
5、打印验证。

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

解法二:双指针法

class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if(nums.length==1)return 1;
        int maxLength=1;
        for(int left=0;left<nums.length;left++){
            int curLength=1;
            for(int right=left+1;right<nums.length;right++){
                if(nums[right-1]<nums[right]){
                    curLength++;
                }else{
                    break;
                }
            }
            maxLength=Math.max(maxLength,curLength);
        }
        return maxLength;
    }
}

718. 最长重复子数组

教程视频:https://www.bilibili.com/video/BV178411H7hV
在这里插入图片描述

解法一:动态规划

思路:
1、dp[i][j]含义:以下标 i - 1为 结尾的nums1,和以下标 j - 1 为结尾的nums2,最长重复子数组长度为dp[i][j]。 这里-1是为了简化初始化过程。
2、递推公式:两个数组指针始终对齐,需要同时-1if(nums2[j]==nums1[i]){ dp[i][j]=dp[i-1][j-1]+1; }
3、dp数组初始化:dp[0][j]和dp[i][0]无实际意义,为了保证递推有意义,全部初始化为0,dp[i][j]=0;
4、遍历顺序:外层 遍历nums1,内层遍历nums2。正序倒序无影响。
5、打印验证。

class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        int maxLength=0;
        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;
                }
                maxLength=Math.max(maxLength,dp[i][j]);
            }
        }
        return maxLength;
    }
}

//空间压缩
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[] dp = new int[nums2.length+1];
        int maxLength=0;
        for(int i=1;i<=nums1.length;i++){
            for(int j=nums2.length;j>=1;j--){
                if(nums1[i-1]==nums2[j-1]){
                    dp[j]=dp[j-1]+1;
                }else {
                    dp[j] = 0;//这里不能漏,否则上一阶段状态不能完全刷新
                }
                maxLength=Math.max(maxLength,dp[j]);
            }
        }
        return maxLength;
    }
}

总结

1、子数组相关题目要从尾部元素去定义dp数组;
2、两个不同序列比较时,递推公式需要考虑指针对齐的问题;
3、718. 最长重复子数组中dp[i][j]表示索引为i-1和j-1处的最长公共子序列,可以简化初始化状态。

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

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

相关文章

SQL案例-高校信息管理系统实现要求

SQL案例-高校信息管理系统实现要求 (1) 建表 stuInfo(学生信息表) 字段名称数据类型说明stuName字符学生姓名&#xff0c;该列必填&#xff0c;要考虑姓氏可能是两个字的&#xff0c;如欧阳俊雄stuNo字符学号&#xff0c;该列必填&#xff0c;学号不能重复&#xff0c;且必须…

算法|1.二分及其扩展

算法|1.二分及其扩展 1、有序数组中找到num 题意&#xff1a;给定有序数组&#xff0c;在有序数组中找到指定数字&#xff0c;找到返回true&#xff0c;找不到返回false. 解题思路&#xff1a; 数组有序查找指定元素使用二分法L指针初始值设为0&#xff0c;R指针初始值设为…

IOC初始化 IOC启动阶段 (Spring容器的启动流程)

[toc](IOC初始化 IOC启动阶段 (Spring容器的启动流程)) IOC初始化 IOC启动阶段 (Spring容器的启动流程) Resource定位过程&#xff1a;这个过程是指定位BeanDefinition的资源&#xff0c;也就是配置文件&#xff08;如xml&#xff09;的位置&#xff0c;并将其封装成Resource对…

拥抱新时代的Java

原文链接 拥抱新时代的Java Java作为面向对象编程的王牌语言&#xff0c;曾经风靡一时&#xff0c;在Web领域是绝对的老大。随着时间的推移&#xff0c;一些新的编程范式不断的涌现&#xff0c;如函数式编程&#xff0c;响应式编程&#xff0c;以及对函数的全力支持&#xff0…

node.js+vue房屋租赁管理系统z0g8w

本系统主要包括以下功能模块&#xff1a;租户、出租人、房源信息、预约看房、合同信息等模块。 其中设计的主要功能如下&#xff1a; &#xff08;1&#xff09;用户的注册和登录本系统&#xff0c;登录到系统的首页。 &#xff08;2&#xff09;用户可以发布自己的房源信息…

强化学习:值迭代和策略迭代

值迭代 通过上一章的学习&#xff0c;我们知道了贝尔曼最优方程的求解实际上分两部分&#xff0c;一是给定一个初始值 v k v_k vk​ 找到最优策略 π k 1 π_{k1} πk1​ &#xff0c;二是更新 v k 1 v_{k1} vk1​   下面&#xff0c;我们将详细剖析这个算法&#xff0…

RabbitMQ

处理问题 服务异步调用 两个服务调用时&#xff0c;我们可以通过传统的HTTP方式&#xff0c;让服务A直接去调用服务B的接口&#xff0c;但是这种方式是同步的方式&#xff0c;虽然可以采用SpringBoot提供的Async注解实现异步调用&#xff0c;但是这种方式无法确保请求一定回访…

从Redisson的RedissonSemaphore引发的信号量实际含义的思考

Semaphore到底该如何使用 事情的起因是最近在看redisson的源码&#xff0c;刚好看到了RedissonSemaphore的acquire/release实现。 public RFuture<Void> releaseAsync(int permits) {if (permits < 0) {throw new IllegalArgumentException("Permits amount ca…

ThingsBoard教程(五十):规则节点解析 创建关系节点Create Relation Node,删除关系节点 Delete Relation Node

创建关系节点 Create Relation Node Since TB Version 2.2.1 根据类型和方向,从所选实体创建到消息发起方的关系。 以下消息发起方类型被允许:资产、设备、实体视图、客户、租、仪表板。 通过元数据键模式查找目标实体,然后在源实体和目标实体之间创建关系。 如果选择的…

ASP.NET Core 使用Filter和Redis实现接口防重

背景 日常开发中&#xff0c;经常需要对一些响应不是很快的关键业务接口增加防重功能&#xff0c;即短时间内收到的多个相同的请求&#xff0c;只处理一个&#xff0c;其余不处理&#xff0c;避免产生脏数据。 这和幂等性&#xff08;idempotency&#xff09;稍微有点区别&am…

每日一练 | 网络工程师软考真题 Day12

阅读以下说明&#xff0c;答复以下【问题1】至【问题3】 【说明】 某单位有1个总部和6个分部&#xff0c;各个部门都有自己的局域网。该单位申请了6个C类IP地址202.115.10.0/24~202.115.15.0/24&#xff0c;其中总部与分部4共用一个C类地址。现方案将这些部门用路由器互联&…

Mit6.006-problemSet03

3-1 哈希练习&#xff08;Hash Practice&#xff09; (a) 按顺序插入整数keys A[47, 61, 36, 52, 56, 33, 92]到尺寸为7的哈希表中&#xff0c;使用哈希函数 h ( k ) ( 10 k 4 ) m o d 7 h(k)(10k4)mod7 h(k)(10k4)mod7。哈希表的每个插槽&#xff0c;存储一个key&#xff…

字节真的是宇宙尽头吗?

身边在字节的朋友很多人抱怨很卷&#xff0c;但卷到何种程度?很多人没有直观感受。某乎上一个问题(在字节跳动工作是怎样的?)点赞排名第一的回答生动的解释了字节的卷。 租房的舍友在字节工作。 舍友主卧&#xff0c;我次卧。 合租两个月了&#xff0c;我没见过舍友长什么样。…

日语文法PPT截图31-45

31 形式名词 とき ところ 作为形式名词的话&#xff0c;一般是要写假名不写汉字的 相对时态 如果是一般时/将来时とき&#xff0c;就是先做后面的动作&#xff0c;在做前面的动作。 出教室的时候&#xff0c;关灯。 如果是过去时とき那么&#xff0c;是先做前面的动作&#…

【dfn序+DP】树

把一棵树转化成一个序列有三种方法&#xff1a; dfs序 dfn序&#xff08;时间戳&#xff09; 欧拉序 关于这三者的区别&#xff0c;参考这篇博客&#xff0c;讲的超级好&#xff01; 重谈DFS序、时间戳和欧拉序 - Seaway-Fu - 博客园 (cnblogs.com) 题意&#xff1a; 思路…

SVN 导出改动差异文件

文章目录 SVN 导出改动差异文件应用场景/背景介绍具体操作方法 SVN 导出改动差异文件 应用场景/背景介绍 当然下面的两个场景介绍可能用分支管理都会有不错的效果&#xff0c;或者更优&#xff0c;只是记录一下思路&#xff0c;用什么还是看大家个人爱好啦 在开发过程中偶尔会…

1. Ansible介绍,什么是Ansible?Ansible能用来做什么?

什么是Ansible&#xff1f;Ansible能用来做什么&#xff1f; 如果您是系统工程师或IT管理员,或者只是在IT部门工作的任何人,您可能会在环境中执行大量重复性任务, 无论是每天调整大小和创建新主机或虚拟机&#xff64; 在其上应用配置&#xff64; 修补数百台服务器&#xff6…

不用再找了,你要的国内好用的ChatGPT网站都在这里

&#x1f4a1; 大家好&#xff0c;我是可夫小子&#xff0c;关注AIGC、读书和自媒体。解锁更多ChatGPT、AI绘画玩法。加&#xff1a;keeepdance&#xff0c;备注&#xff1a;chatgpt&#xff0c;拉你进群。 目录 ChatGPT是什么 OpenAI与ChatGPT的发展历程 AI对话聊天 AI文档…

jdk13至15——文本块特性

文本块在jdk13中第一次预览&#xff0c;jdk14第二次预览&#xff0c;jdk15正式版&#xff1b; 终于不用在多行字符串中加一堆\n和一堆\"和一堆了&#xff1b; 之前需要这么麻烦&#xff1a; Testvoid test() {String s "testabcd\n" "aaa\n" "…

AI:Vue2和Vue3的对比

1. 什么是Vue.js以及Vue.js在前端开发中的重要性。 Vue.js是一个遵循MVVM&#xff08;Model-View-ViewModel&#xff09;模式的前端JavaScript框架&#xff0c;它采用了双向数据绑定和组件化的思想&#xff0c;使得前端开发变得更加简洁、高效、可维护。Vue.js由中国工程师尤雨…