• 力扣: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
  • 相关阅读:
    jemter使用和优化
    封装, 继承, 多态详解
    医院信息化的三种演进建设模式
    ros建图过程中给上位机发布地图信息
    ARM的七种工作模式
    【Linux】文件系统
    Linux入门与进阶(二)
    基于 Apache Hudi 和DBT 构建开放的Lakehouse
    ppt复现CVPR顶会流程图
    Electron实战之进程间通信
  • 原文地址:https://blog.csdn.net/qq_56762247/article/details/126316552