1035.不相交的线

题目描述

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

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

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

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

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

示例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

解题思路

绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，只要 nums1[i] == nums2[j]，且直线不能相交

直线不能相交，这就是说明在nums1中 找到一个与nums2相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，链接相同数字的直线就不会相交。

其实也就是说nums1和nums2的最长公共子序列是[1,4]，长度为2

求解过程与【算法|动态规划】Leetcode 1143.最长公共子序列同

代码实现

• 核心模式

class Solution{
public:
    int maxUncrossedLines(const vector<int>& nums1, const vector<int>& nums2){
        // initialize the DP array
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));

        // traversal
        for (int i = 1; i <= nums1.size(); i++){
            for (int j = 1; j <= nums2.size(); j++){
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        return dp[nums1.size()][nums2.size()];
    }
};

• ACM模式
"dynamicPro.h"

#include <iostream>
#include "dynamicPro.h"

class Solution{
public:
    int maxUncrossedLines(const vector<int>& nums1, const vector<int>& nums2){
        // initialize the DP array
        vector<vector<int>> dp(nums1.size() + 1, vector<int>(nums2.size() + 1, 0));

        // traversal
        for (int i = 1; i <= nums1.size(); i++){
            for (int j = 1; j <= nums2.size(); j++){
                if (nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }

        print2DVector(dp);

        return dp[nums1.size()][nums2.size()];
    }
};

int main(){
    vector<int> case11 = {1, 4, 2};
    vector<int> case12 = {1, 2, 4};
    vector<int> case21 = {2, 5, 1, 2, 5};
    vector<int> case22 = {10, 5, 2, 1, 5, 2};
    vector<int> case31 = {1, 3, 7, 1, 7, 5};
    vector<int> case32 = {1, 9, 2, 5, 1};

    Solution solution;
    cout << "Result1's DP array = " << solution.maxUncrossedLines(case11, case12) << endl;
    cout << "Result2's DP array = " << solution.maxUncrossedLines(case21, case22) << endl;
    cout << "Result3's DP array = " << solution.maxUncrossedLines(case31, case32) << endl;
    
    return 0;
}

• 输出

Result1's DP array = [[0, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 2], [0, 1, 2, 2]]
2
Result2's DP array = [[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1], [0, 0, 1, 1, 1, 2, 2], [0, 0, 1, 1, 2, 2, 2], [0, 0, 1, 2, 2, 2, 3], [0, 0, 1, 2, 2, 3, 3]]  
3
Result3's DP array = [[0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 1], [0, 1, 1, 1, 1, 2], [0, 1, 1, 1, 1, 2], [0, 1, 1, 1, 2, 2]]
2