乐趣区

你的衣服我扒了-最长公共子序列

之前出了一篇穿上衣服我就不认识你了?来聊聊最长上升子序列,收到了大家的一致好评。今天给大家带来的依然是换皮题 – 最长公共子序列系列。

最长公共子序列是一个很经典的算法题。有的会直接让你求最长上升子序列,有的则会换个说法,但最终考察的还是最长公共子序列。那么问题来了,它穿上衣服你还看得出来是么?

如果你完全看不出来了,说明抽象思维还不到火候。经常看我的题解的同学应该会知道,我经常强调 抽象思维。没有抽象思维,所有的题目对你来说都是新题。你无法将之前做题的经验迁移到这道题,那你做的题意义何在?

虽然抽象思维很难练成,但是幸好算法套路是有限的,经常考察的题型更是有限的。从这些入手,或许可以让你轻松一些。本文就从一个经典到不行的题型《最长公共子序列》,来帮你进一步理解 抽象思维

注意。本文是帮助你识别套路,从横向上理清解题的思维框架,并没有采用最优解,所有的题目给的解法可能不是最优的,但是都可以通过所有的测试用例。如果你想看最优解,可以直接去讨论区看。或者期待我的 深入剖析系列

718. 最长重复子数组

题目地址

https://leetcode-cn.com/probl…

题目描述

给两个整数数组  A  和  B,返回两个数组中公共的、长度最长的子数组的长度。示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。说明:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

前置知识

  • 哈希表
  • 数组
  • 二分查找
  • 动态规划

思路

这就是最经典的最长公共子序列问题。一般这种求解 两个数组或者字符串求最大或者最小 的题目都可以考虑动态规划,并且通常都定义 dpi 为 以 A[i], B[j] 结尾的 xxx。这道题就是:以 A[i], B[j] 结尾的两个数组中公共的、长度最长的子数组的长度

关于状态转移方程的选择可以参考:穿上衣服我就不认识你了?来聊聊最长上升子序列

算法很简单:

  • 双层循环找出所有的 i, j 组合,时间复杂度 $O(m * n)$,其中 m 和 n 分别为 A 和 B 的 长度。

    • 如果 A[i] == B[j],dpi = dpi – 1 + 1
    • 否则,dpi = 0
  • 循环过程记录最大值即可。

记住这个状态转移方程,后面我们还会频繁用到。

关键点解析

  • dp 建模套路

代码

代码支持:Python

Python Code:

class Solution:
    def findLength(self, A, B):
        m, n = len(A), len(B)
        ans = 0
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    ans = max(ans, dp[i][j])
        return ans

复杂度分析

  • 时间复杂度:$O(m * n)$,其中 m 和 n 分别为 A 和 B 的 长度。
  • 空间复杂度:$O(m * n)$,其中 m 和 n 分别为 A 和 B 的 长度。

二分查找也是可以的,不过并不容易想到,大家可以试试。

1143. 最长公共子序列

题目地址

https://leetcode-cn.com/probl…

题目描述

给定两个字符串  text1 和  text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的   子序列   是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,”ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例 1:

输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace”,它的长度为 3。
示例 2:

输入:text1 = “abc”, text2 = “abc”
输出:3
解释:最长公共子序列是 “abc”,它的长度为 3。
示例 3:

输入:text1 = “abc”, text2 = “def”
输出:0
解释:两个字符串没有公共子序列,返回 0。

提示:

1 <= text1.length <= 1000
1 <= text2.length <= 1000
输入的字符串只含有小写英文字符。

前置知识

  • 数组
  • 动态规划

思路

和上面的题目类似,只不过数组变成了字符串(这个无所谓),子数组(连续)变成了子序列(非连续)。

算法只需要一点小的微调:如果 A[i] != B[j],那么 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

关键点解析

  • dp 建模套路

代码

你看代码多像

代码支持:Python

Python Code:

class Solution:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        m, n = len(A), len(B)
        ans = 0
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return ans

复杂度分析

  • 时间复杂度:$O(m * n)$,其中 m 和 n 分别为 A 和 B 的 长度。
  • 空间复杂度:$O(m * n)$,其中 m 和 n 分别为 A 和 B 的 长度。

1035. 不相交的线

题目地址

https://leetcode-cn.com/probl…

题目描述

我们在两条独立的水平线上按给定的顺序写下  A  和  B  中的整数。

现在,我们可以绘制一些连接两个数字  A[i]  和  B[j]  的直线,只要  A[i] == B[j],且我们绘制的直线不与任何其他连线(非水平线)相交。

以这种方法绘制线条,并返回我们可以绘制的最大连线数。

示例 1:

输入:A = [1,4,2], B = [1,2,4]
输出:2
解释:
我们可以画出两条不交叉的线,如上图所示。
我们无法画出第三条不相交的直线,因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。
示例 2:

输入:A = [2,5,1,2,5], B = [10,5,2,1,5,2]
输出:3
示例 3:

输入:A = [1,3,7,1,7,5], B = [1,9,2,5,1]
输出:2

提示:

1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000

前置知识

  • 数组
  • 动态规划

思路

从图中可以看出,如果想要不相交,则必然相对位置要一致,换句话说就是:公共子序列。因此和上面的 1143. 最长公共子序列 一样,属于换皮题,代码也是一模一样。

关键点解析

  • dp 建模套路

代码

你看代码多像

代码支持:Python

Python Code:

class Solution:
    def longestCommonSubsequence(self, A: str, B: str) -> int:
        m, n = len(A), len(B)
        ans = 0
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    ans = max(ans, dp[i][j])
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return ans

复杂度分析

  • 时间复杂度:$O(m * n)$,其中 m 和 n 分别为 A 和 B 的 长度。
  • 空间复杂度:$O(m * n)$,其中 m 和 n 分别为 A 和 B 的 长度。

总结

第一道是“子串”题型,第二和第三则是“子序列”。不管是“子串”还是“子序列”,状态定义都是一样的,不同的只是一点小细节。

只有熟练掌握基础的数据结构与算法,才能对复杂问题迎刃有余。 基础算法,把它彻底搞懂,再去面对出题人的各种换皮就不怕了。相反,如果你不去思考题目背后的逻辑,就会刷地很痛苦。题目稍微一变化你就不会了,这也是为什么很多人说 刷了很多题,但是碰到新的题目还是不会做 的原因之一。关注公众号力扣加加,努力用清晰直白的语言还原解题思路,并且有大量图解,手把手教你识别套路,高效刷题。

更多题解可以访问我的 LeetCode 题解仓库:https://github.com/azl3979858…。目前已经 30K star 啦。

退出移动版