[LeetCode] 1035. Uncrossed Lines

[grandyang]

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 同步地址:

#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 题目讲解汇总(持续更新中...)