leetcode刷题笔记-1035.不相交的线

题目

在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。

现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足：

1
2
nums1[i] == nums2[j]
且绘制的直线不与任何其他连线（非水平线）相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

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

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
示例 1：
输入：nums1 = [1,4,2], nums2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。 
但无法画出第三条不相交的直线，因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例 2：
输入：nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出：3

示例 3：
输入：nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出：2

image.png

提示

1
2
1 <= nums1.length, nums2.length <= 500
1 <= nums1[i], nums2[j] <= 2000

思路

这道题乍一看好像没有什么好的办法，但是多举几个例子，就能发现它本质上问的是这两个数组的最长公共子序列。因为只要我们不修改画线的元素在原始数组中的相对位置，那么画出来的线就不会出现交叉，最长公共子序列就符合这个特性，这也是这道题真正询问的点！

来复盘一下最长公共子序列的思路吧，最长公共子序列这个题目非常重要，会被其他很多相似的题目引用。最好是能理解并记忆下来。

首先是dp数组的含义，我们定义了二维dp数组，含义是a[i]和b[j]这两个元素（包括他们自己）之前的最长公共子序列的长度。

递推的情况则是a[i]和b[j]相等的时候，dp[i][j] = dp[i-1][j-1] + 1；其他情况代表最长公共子序列没有被扩张，则需要采用“前一位”的最大值，分别是i-1（j不变）和j-1（i不变）的两种情况。

代码

完整代码如下，另外的办法可以参考最长公共子序列的题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        int result = 0;
        vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size(), 0));
        // 初始化，第一行和第一列
        for (int i = 0; i < nums1.size(); i++) {
            if (nums1[i] == nums2[0]) {
                dp[i][0] = 1;
                result = 1;
            } else if (i > 0) {
                dp[i][0] = dp[i - 1][0];
            }
        }
        for (int j = 0; j < nums2.size(); j++) {
            if (nums2[j] == nums1[0]) {
                dp[0][j] = 1;
                result = 1;
            } else if (j > 0) {
                dp[0][j] = dp[0][j - 1];
            }
        }
        // 开始遍历
        for (int i = 1; i < nums1.size(); i++) {
            for (int j = 1; j < nums2.size(); j++) {
                if (nums1[i] == nums2[j]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                if (dp[i][j] > result) {
                    result = dp[i][j];
                }
            }
        }

        return result;
    }
};

image.png