LWC 56:718. Maximum Length of Repeated Subarray

LWC 56:718. Maximum Length of Repeated Subarray

传送门:718. Maximum Length of Repeated Subarray

Problem:

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1].

Note:

1 <= len(A), len(B) <= 1000

0 <= A[i], B[i] < 100

思路: 和上周一样,还是一道动态规划题,如果对动规不熟悉,可以采用递归+记忆化搜索,本题亦如此。首先判断末位两个元素是否相等,不相等把A的问题规模变成n-1,和B求出最长subarray长度,或者把B的问题规模变成m-1,和A求出最长subarray。

遇到相等该如何操作,自然在子问题n-1,和m-1基础上+1,(问题的定义如下:给定A和B的末区间i和j,返回A[0,…,i]和B[0,…,j]中以i和j结尾的最长subArray长度),

所以有如下递归式:

f(A, B, i, j) = 1 + f(A, B, i - 1, j - 1); if (A[i] == B[j])

or:
f(A, B, i, j) = 0;

此时就可以用数组dp记录每个状态的最长subArray长度,并在过程中不断更新max。

代码如下:

   public int findLength(int[] A, int[] B) {
        max = 0;
        int n = A.length;
        int m = B.length;
        dp = new int[n + 1][m + 1];
        for (int i = 0; i < n + 1; ++i) {
            for (int j = 0; j < m + 1; ++j) {
                dp[i][j] = -1;
            }
        }
        dfs(A, B, n - 1, m - 1);
        return max;
    }


    int[][] dp;
    int max = 0;
    int dfs(int[] A, int[] B, int n, int m) {
        if (n == -1 || m == -1) return 0;
        if (dp[n][m] >= 0) return dp[n][m];

        dfs(A, B, n - 1, m);
        dfs(A, B, n, m - 1);

        if (A[n] == B[m]) {
            int ans = 1;
            int sub = dfs(A, B, n - 1, m - 1);

            max = Math.max(max, ans + sub);
            dp[n][m] = ans + sub;
            return ans + sub;
        }
        else {
            dp[n][m] = 0;
            return 0;
        }
    }

注意此处,0也是可能的一种答案,所以DP初始化为-1,否则超时。

递推版本(动态规划):

        public int findLength(int[] A, int[] B) {
            int n = A.length;
            int m = B.length;
            int max = 0;
            int[][] dp = new int[n + 1][m + 1];

            for (int i = 1; i <= n; ++i) {
                for (int j = 1; j <= m; ++j) {
                    if (A[i - 1] == B[j - 1]) {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    else {
                        dp[i][j] = 0;
                    }

                    max = Math.max(dp[i][j], max);
                }
            }

            return max;
        }   

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

linux系统编程之文件与I/O(三):目录的操作

一、目录的访问 功能说明:打开一个目录 原型:DIR*  opendir(char *pathname); 返回值: 打开成功,返回一个目录指针 打开...

1585
来自专栏崔庆才的专栏

Bash 脚本 set 命令教程

1375
来自专栏机器学习从入门到成神

Vue2.0中v-for迭代语法变化(key、index)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

401
来自专栏流柯技术学院

jmeter正则表达式提取器提取特定字符串后的全部内容

jmeter进行JDBC请求时,请求后的响应结果在传递给下一个请求使用时,需要用到关联,也在jmeter中,关联通过正则表达式提取器实现。

782
来自专栏IT可乐

Linux系列教程(二十二)——Linux的bash变量

  上篇博客我们介绍了bash的一些基本功能,这是我们平时操作最频繁的。本篇博客我们介绍bash的变量,为后面编写shell脚本做铺垫。 1、什么是变量   变...

18410
来自专栏Laoqi's Linux运维专列

shell 1>&2 2>&1 &>filename重定向的含义和区别

1145
来自专栏Python私房菜

60行Python代码,实现多线程PDF转Word

工作中经常会遇到需要提取PDF文件中文字的情况,一个PDF还好,复制粘贴一下也花不了太多时间,如果需要把大量PDF转为Word,怎么办呢?

633
来自专栏一个会写诗的程序员的博客

java代码执行过程简介

代码即数据,数据即代码,而我们的数据是保存在文件上的,所以我们说文件就是数据,一切代码都是文件。

813
来自专栏大闲人柴毛毛

Linux管道命令

1 什么是管道命令? 管道命令能够将一个命令的执行结果经过筛选,只保留我们需要的信息。 如,/etc目录下会有大量的文件,如果使用ls很难找到需要的文件,...

3476
来自专栏Java 源码分析

Linux小记

正文 定义别名: alias vi='vim' 查看别名: alias 让某个用户永久生效 vim ~/.bashrc 删除别名 ualias vi 快捷键: ...

2965

扫码关注云+社区