1035. Uncrossed Lines

We write the integers of A and B (in the order they are given) on two separate horizontal lines.

Now, we may draw  connecting lines : a straight line connecting two numbers A[i] and B[j] such that:

  • A[i] == B[j];
  • The line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.

Return the maximum number of connecting lines we can draw in this way.

Example 1:

Input: A = [1,4,2], B = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.

Example 2:

Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3

Example 3:

Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2

Note:

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

这道题给了A和B两个数字数组,并且上下并列排放,说是可以用线来连接相同的数字,问最多能连多少根线而且不会发生重叠。题目中的例子1还配了图帮助我们理解,自己可以画一画其他的例子,题意倒不难理解。难就难在如何在判断连线是否相交,当然不能利用几何学中的两条直线相交的知识,说实话这道题的迷惑性很强,很不容易想到正确的解题思路。首先来想一下,什么情况下两条连线会相交,可以观察下例子1给的图,发现若把4和2分别连上会交叉,这是因为在A数组中是 4,2,而且在B数组中是 2,4,顺序不一样。再来看例子2,分别连 5,1,2 或者 2,1,2,或者 5,2,5 都是可以的,仔细观察,可以发现这些其实就是最长公共子序列 Longest Common Subsequence,只有看到这一步,才算火眼金睛看得透问题的本质。所以这道题就是要求 LCS,跟后来的那道 Longest Common Subsequence 完全没有区别,代码拿来直接可以用,但这道题加了个背景,感觉难度直接提升了一个档次。这里是用动态规划 Dynamic Programing 来做,使用一个二维数组 dp,其中 dp[i][j] 表示数组A的前i个数字和数组B的前j个数字的最长相同的子序列的数字个数,这里大小初始化为 (m+1)x(n+1),这里的m和n分别是数组A和数组B的长度。接下来就要找状态转移方程了,如何来更新 dp[i][j],若二者对应位置的字符相同,表示当前的 LCS 又增加了一位,所以可以用 dp[i-1][j-1] + 1 来更新 dp[i][j]。否则若对应位置的字符不相同,由于是子序列,还可以错位比较,可以分别从数组A或者数组B去掉一个当前数字,那么其 dp 值就是 dp[i-1][j] 和 dp[i][j-1],取二者中的较大值来更新 dp[i][j] 即可,最终的结果保存在了 dp[m][n] 中,参见代码如下:

class Solution {
public:
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        int m = A.size(), n = B.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (A[i - 1] == B[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1035

类似题目:

Longest Palindromic Subsequence

Delete Operation for Two Strings

Longest Common Subsequence

参考资料:

https://leetcode.com/problems/uncrossed-lines/

https://leetcode.com/problems/uncrossed-lines/discuss/310367/Java-DP-Explained

https://leetcode.com/problems/uncrossed-lines/discuss/282842/JavaC%2B%2BPython-DP-The-Longest-Common-Subsequence

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation