码农知识堂 - 1000bd
  •   Python
  •   PHP
  •   JS/TS
  •   JAVA
  •   C/C++
  •   C#
  •   GO
  •   Kotlin
  •   Swift
  • 力扣:718. 最长重复子数组


    力扣:718. 最长重复子数组

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

    dp数组含义:
    dp[i][j] :以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。 (特别注意: “以下标i - 1为结尾的A” 标明一定是 以A[i-1]为结尾的字符串 )

    解决初始化nums【-1】【-1】的问题:
    模拟遍历:
    i的范围是0~nums1.size()
    j的范围是0~nums2.size()
    依次选定i,然后依次选定j,然后算出dp【i】【j】,if(nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1]+1;即dp【i】【j】通过dp【i-1】dp【j-1】得到。
    此时想象遍历过程。当 i 为0,j 依次为0~nums2.size()。dp【0】【0】决定了dp【0】【后面的值】,dp【0】【0】怎么初始化呢?很明显看nums1【0】与nums2【0】是否相等,这个就是递归公式。相等则nums【-1】【-1】+1。只需要将nums【-1】【-1】初始化为0即可。那么我们可以将数组扩大一个元素,所有元素都向后移动一个单位,此时dp【0】【0】设为0,然后就可以从第0个元素开始遍历了。此时dp数组下标为1的元素代表的是nums1,nums2小标为0的元素。即dp【i】【j】代表的是以nums1下标 i-1结尾,以nums2下标 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(result < dp[i][j]) result = dp[i][j];
                }
            }
            return result;
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
  • 相关阅读:
    【深入解析spring cloud gateway】05 gateway请求转发实验
    设计模式(1) - UML类图
    day-64 代码随想录算法训练营(19)图论 part 03
    【在线聊天】原来微信小程序也能回复Facebook主页消息!
    Go语言使用AES加密解密
    微服务技术栈简单介绍,Eureka和Ribbon的引入和使用
    计算机毕业设计SSM电力公司员工安全培训系统【附源码数据库】
    手把手教你完成(Java)师生信息管理系统
    Springboot整合dubbo&zookeeper为注册中心
    Shopee印尼站停止销售跨境商品:电商新规是否将改变印尼电商格局?
  • 原文地址:https://blog.csdn.net/qq_56762247/article/details/126316552
  • 最新文章
  • 攻防演习之三天拿下官网站群
    数据安全治理学习——前期安全规划和安全管理体系建设
    企业安全 | 企业内一次钓鱼演练准备过程
    内网渗透测试 | Kerberos协议及其部分攻击手法
    0day的产生 | 不懂代码的"代码审计"
    安装scrcpy-client模块av模块异常,环境问题解决方案
    leetcode hot100【LeetCode 279. 完全平方数】java实现
    OpenWrt下安装Mosquitto
    AnatoMask论文汇总
    【AI日记】24.11.01 LangChain、openai api和github copilot
  • 热门文章
  • 十款代码表白小特效 一个比一个浪漫 赶紧收藏起来吧!!!
    奉劝各位学弟学妹们,该打造你的技术影响力了!
    五年了,我在 CSDN 的两个一百万。
    Java俄罗斯方块,老程序员花了一个周末,连接中学年代!
    面试官都震惊,你这网络基础可以啊!
    你真的会用百度吗?我不信 — 那些不为人知的搜索引擎语法
    心情不好的时候,用 Python 画棵樱花树送给自己吧
    通宵一晚做出来的一款类似CS的第一人称射击游戏Demo!原来做游戏也不是很难,连憨憨学妹都学会了!
    13 万字 C 语言从入门到精通保姆级教程2021 年版
    10行代码集2000张美女图,Python爬虫120例,再上征途
Copyright © 2022 侵权请联系2656653265@qq.com    京ICP备2022015340号-1
正则表达式工具 cron表达式工具 密码生成工具

京公网安备 11010502049817号