【LeetCode】最长公共子序列 | 718. Maximum Length of Repeated Subarray | 最短路径

标签: 动态规划  公共子序列

1. 最长公共子序列

1.1 介绍最长公共子序列的概念

最长公共子串(Longest Common Substring)最长公共子序列(Longest Common Subsequence)的区别: 子串要求在原字符串中是连续的,而子序列则只需保持相对顺序一致,并不要求连续

(1)例如X = {a, Q, 1, 1}; Y = {a, 1, 1, d, f}那么,{a, 1, 1}是X和Y的最长公共子序列,但不是它们的最长公共字串。

(2)S1 = ABCD,S2=AEBD,那么S1与S2的最长公共子序列是{ABD}。

1.2 最长公共子序列的解题思路

S1[0...m]表示:S1字符串下标从0到m的子串。

S2[0...n]表示:S2字符串下标从0到n的子串。

那么最长公共子序列的状态转移方程为:

LCS(m,n)表示:S1[0...m]和S2[0...n]的最长公共子序列的长度。

 

 1.3 具体例子理解最长公共子序列的解题思路

1.4 代码实现

(1)递归方法

class Solution:

    def tryLCS(self, s1, s2):

        if s1 == None or s2 == None:
            return None

        if len(s1) == 0 or len(s2) == 0:
            return 0

        # 求s1[0...m]和s2[0...n]的最长公共子序列的长度值
        def LCS(s1, s2, m, n):

            if m < 0 or n < 0:
                return 0

            if s1[m] == s2[n]:
                return 1 + LCS(s1, s2, m-1, n-1)
            else:
                 return max(LCS(s1, s2, m-1, n), LCS(s1, s2, m, n-1))

        return LCS(s1, s2, len(s1)-1, len(s2)-1)

solution = Solution()
# test 1
s1 = "ABCDGH"
s2 = "ABDHG"
print(solution.tryLCS(s1, s2))

(2)记忆化搜索算法

class Solution:

    def tryLCS(self, s1, s2):

        if s1 == None or s2 == None:
            return None

        if len(s1) == 0 or len(s2) == 0:
            return ""

        memo = [[-1 for _ in range(len(s2))] for _ in range(len(s1)) ]

        # 求s1[0...m]和s2[0...n]的最长公共子序列的长度值
        def LCS(s1, s2, m, n):

            if m < 0 or n < 0:
                return 0

            if memo[m][n] != -1:
                return memo[m][n]

            if s1[m] == s2[n]:
                res = 1 + LCS(s1, s2, m-1, n-1)
            else:
                res = max(LCS(s1, s2, m-1, n), LCS(s1, s2, m, n-1))

            memo[m][n] = res
            return res

        return LCS(s1, s2, len(s1)-1, len(s2)-1)

solution = Solution()
# test 1
# s1 = "ABCDGH"
# s2 = "ABDHG"
# print(solution.tryLCS(s1, s2))

# test 2
s1 = "AAACCGTGAGTTATTCGTTCTAGAA"
s2 = "CACCCCTAAGGTACCTTTGGTTC"
print(solution.tryLCS(s1, s2))

(3)动态规划方法 

class Solution:

    def LCS(self, s1, s2):

        m = len(s1)
        n = len(s2)

        # 对memo的第0行和第0列进行初始化
        memo = [[0 for _ in range(n)] for _ in range(m)]

        # 初始化第0列
        for i in range(n):
            if s1[0] == s2[i]:
                for k in range(i,n):
                    memo[0][k] = 1
                break

        # 初始化第0行
        for i in range(m):
            if s1[i] == s2[0]:
                for k in range(i,m):
                    memo[k][0] = 1
                break

        # 动态规划过程
        for i in range(1, m):
            for j in range(1, n):
                if s1[i] == s2[j]:
                    memo[i][j] = 1 + memo[i - 1][j - 1]
                else:
                    memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])

        return memo[m-1][n-1]


solution = Solution()
# test 1
s1 = "ABCDGH"
s2 = "ABDHG"
print(solution.LCS(s1, s2))

1.5 【718】 Maximum Length of Repeated Subarray

地址:https://leetcode.com/problems/maximum-length-of-repeated-subarray/

2. 最短路径与动态规划求解

3. 求动态规划的具体解

反向求解出s1与s2的最长公共子序列,而不是求最长公共子序列的长度。

例题:输出最长公共子序列。

class Solution:

    def LCS(self, s1, s2):

        m = len(s1)
        n = len(s2)

        # 对memo的第0行和第0列进行初始化
        memo = [[0 for _ in range(n)] for _ in range(m)]

        # 初始化第0列
        for i in range(n):
            if s1[0] == s2[i]:
                for k in range(i,n):
                    memo[0][k] = 1
                break

        # 初始化第0行
        for i in range(m):
            if s1[i] == s2[0]:
                for k in range(i,m):
                    memo[k][0] = 1
                break

        # 动态规划过程
        for i in range(1, m):
            for j in range(1, n):
                if s1[i] == s2[j]:
                    memo[i][j] = 1 + memo[i - 1][j - 1]
                else:
                    memo[i][j] = max(memo[i - 1][j], memo[i][j - 1])

        # return memo[m-1][n-1]

        # 通过memo反向求解s1和s2的最长公共子序列
        m = m - 1
        n = n - 1
        LCSstr = []
        while m >= 0 and n >=0:
            if s1[m] == s2[n]:
                LCSstr.append(s1[m])
                m = m - 1
                n = n - 1

            elif m == 0:
                n = n - 1
            elif n == 0:
                m = m - 1
            else:
                if memo[m - 1][n] > memo[m][n - 1]:
                    m = m -1
                else:
                    n = n - 1
        return LCSstr

solution = Solution()
# test 1
s1 = "ABCDGH"
s2 = "ABDHG"
print(solution.LCS(s1, s2))

练习题(未完成):

【LeetCode】300. Longest Increasing Subsequence

要求:打印出最长上升子序列。

【动态规划】0-1背包问题

要求:输出背包中放的具体有哪些物品。

版权声明:本文为program_developer原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/program_developer/article/details/89360165

智能推荐

用栈判断一个字符串是否平衡

注: (1)本文定义:左符号:‘(’、‘[’、‘{’…… 右符号:‘)’、‘]’、‘}’……. (2)所谓的字符串的符号平衡,是指字符串中的左符号与右符号对应且相等,如字符串中的如‘(&r...

JAVA环境变量配置

位置 计算机->属性->高级系统设置->环境变量 方式一 用户变量新建path 系统变量新建classpath 方式二 系统变量 新建JAVA_HOME,值为JDK路径 编辑path,前加 方式三 用户变量新建JAVA_HOME 此路径含lib、bin、jre等文件夹。后运行tomcat,eclipse等需此变量,故最好设。 用户变量编辑Path,前加 系统可在任何路径识别jav...

常用的伪类选择器

CSS选择器众多 CSS选择器及权重计算 最常用的莫过于类选择器,其它的相对用的就不会那么多了,当然属性选择器和为类选择器用的也会比较多,这里我们就常用的伪类选择器来讲一讲。 什么是伪类选择器? CSS伪类是用来添加一些选择器的特殊效果。 常用的为类选择器 状态伪类 我们中最常见的为类选择器就是a标签(链接)上的为类选择器。 当我们使用它们的时候,需要遵循一定的顺序问题,否则将可能出现bug 注意...

ButterKnife的使用介绍及原理探究(六)

前面分析了ButterKnife的源码,了解其实现原理,那么就将原理运用于实践吧。 github地址:       点击打开链接 一、自定义注解 这里为了便于理解,只提供BindView注解。 二、添加注解处理器 添加ViewInjectProcessor注解处理器,看代码, 这里分别实现了init、getSupportedAnnotationTypes、g...

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。考试复习题库1|要求:只能使用单字符比较操作。

1.写一个程序,提示输入两个字符串,然后进行比较,输出较小的字符串。 要求只能使用单字符比较操作。 参考代码: 实验结果截图:...

猜你喜欢

小demo:slideDown()实现二级菜单栏下拉效果

效果如下,鼠标经过显示隐藏的二级菜单栏 但是这样的时候会存在一个问题,就是鼠标快速不停移入移出会导致二级菜单栏闪屏现象,一般需要使用stop()来清除事件  ...

基于docker环境的mysql主从复制

1、安装docker 可以参考之前的博客,之前写过了~ 2、拉取mysql镜像 3、创建mysql01和mysql02实例 主: 从: 4、进入容器修改配置 1)修改主数据库配置 进入主数据库容器 切换到 etc/mysql/目录下 查看可以看到my.cnf文件,使用vim编辑器打开,但是需要提前安装 安装vim命令: 安装成功后,修改my.cnf文件 新增配置后的my.cnf: binlog 日...

机器学习算法之决策树

原文:http://www.jianshu.com/p/6eecdeee5012 决策树是一种简单高效并且具有强解释性的模型,广泛应用于数据分析领域。其本质是一颗由多个判断节点组成的树,如: 决策树 在使用模型进行预测时,根据输入参数依次在各个判断节点进行判断游走,最后到叶子节点即为预测结果。 如何构造决策树 决策树算法的核心是通过对数据的学习,选定判断节点,构造一颗合适的决策树。 假设我们从用户...

Netty实现一个简单的RPC框架

微服务 微服务通讯 API构建需要考虑的因素 通讯协议 文本协议或者二进制协议 支持的调用方式:单向、双向、Streaming API定义与声明 API容错、可伸缩性 RPC框架 REST http://www.ics.uci.edu/~fielding/pubs/dissertation/rest_arch_style.htm REST即Representational State Transf...

04-键值对操作(pair RDD)

前言 键值对(pair RDD)是Spark的一部分,与普通RDD具有相同的特性,却又拥有不同于普通RDD的一些特性和操作。 简单来pair RDD就是以key-value形式的RDD。 1 创建pair RDD 根据文本内容,以第一个单词作为键为例: map()函数需要设置key-value参数,如该例中:key=x.split(" ")[0], value=x。 2 pai...