题解 | #最长公共子数组#

最长公共子数组

http://www.nowcoder.com/practice/6032826d387c4a10ad3690cce5fdb015

最长公共子数组

题意

给定两个子数组,求最长公共子数组的长度

方法

循环对比(TLE)

分析

公共子数组的性质是连续的一段

换句话说,从A的某个位置i开始,从B的某个位置j开始,长度为len的一段相等

那么问题可以变为,先分别选取起始位置,再进行比较,并记录最大的相等长度

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param B int整型vector 
     * @return int整型
     */
    int longestCommonSubarry(vector<int>& A, vector<int>& B) {
        int ans = 0;
        for(int i = 0;i<A.size();i++){ // 枚举A中开始的位置
            for(int j = 0;j<B.size();j++){ //  枚举B开始的位置
                for(int l = 0;i+l<A.size() && j+l < B.size();l++){ // 按位对比
                    if(A[i+l] == B[j+l]) ans = max(ans,l+1);
                    else break;
                }
            }
        }
        return ans;
    }
};

复杂度分析

空间复杂度: 使用了常数个额外变量,空间复杂度为O(1)O(1)

时间复杂度: 对于最里层的比较最坏情况是完全遍历,所以总时间复杂度为O(n3)O(n^3)

优化枚举过程

分析

上面的搜索过程中,是每次选择两个字符串比较的起始位置进行比较的, 例如A+i开始 和B+j开始

然而在后面的比较过程中,又会选取以A+i+1开始和B+j+1开始作为起始位置进行比较

这两次不同起始位置选取,都会将A[i+k]B[j+k]比较,也就是有不少的位置发生重复比较了

考虑通过一个办法减少这个重复的比较

注意到分别选取字符串起始位置后,BA对应比较的位置下标差为定值j-i

而 (A+i开始 和B+j开始) 与 (A+i+1开始和B+j+1开始)这两个比较方案中,这个定值相等,都是j-i

设偏移量offset=offset = B起始位置 - A起始位置

所以把循环枚举头部,改为循环枚举偏移量offsetoffset

样例

以样例数据

[1,2],[1,2]

为例

alt

代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param A int整型vector 
     * @param B int整型vector 
     * @return int整型
     */
    int longestCommonSubarry(vector<int>& A, vector<int>& B) {
        int ans = 0;
        for(int offset = 1-(int)A.size();offset < (int)B.size();offset++){ // 偏移量 注意size是无符号的需要转换
            int cur = 0; // 当前相等的长度
            for(int i = 0;i < A.size();i++){ // A的位置
                int j = i + offset; // B的位置
                if(j < 0)continue;
                if(j >= B.size())break;
                cur = A[i] == B[j] ? cur + 1 : 0; // 相等则长度+1,不等则长度为0
                ans = max(ans, cur); // 最大值
            }
        }
        return ans;
    }
};

复杂度分析

空间复杂度: 使用了常数个额外变量,空间复杂度为O(1)O(1)

时间复杂度: 通过先枚举偏移量优化了重复比较,相当于两个字符串字符两两比较,所以总时间复杂度为O(n2)O(n^2)

全部评论

相关推荐

10-09 00:50
已编辑
长江大学 算法工程师
不期而遇的夏天:1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
头像
11-09 17:30
门头沟学院 Java
TYUT太摆金星:我也是,好几个华为的社招找我了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务