leetcode-1035:不相交的线

简介: leetcode-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

解题

方法一:动态规划

参考链接

此题和leetcode-1143:最长公共子序列是一样的。

本题说是求绘制的最大连线数,其实就是求两个字符串的最长公共子序列的长度

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1));
        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]=max(dp[i][j-1],dp[i-1][j]);
                }
            }
        }
        return dp[nums1.size()][nums2.size()];
    }
};
相关文章
|
6月前
|
索引
【力扣刷题】两数求和、移动零、相交链表、反转链表
【力扣刷题】两数求和、移动零、相交链表、反转链表
46 2
【力扣刷题】两数求和、移动零、相交链表、反转链表
|
6月前
|
Go
golang力扣leetcode 160.相交链表
golang力扣leetcode 160.相交链表
48 0
|
6月前
|
C++ Python
leetcode-160:相交链表
leetcode-160:相交链表
47 0
LeetCode | 160. 相交链表
LeetCode | 160. 相交链表
|
3月前
|
存储 Python
【Leetcode刷题Python】1496.判断路径是否相交
Leetcode第1496题"判断路径是否相交"的Python代码实现,通过使用字典存储方向和集合记录访问过的坐标点来检测路径是否与自身相交。
42 2
|
3月前
|
算法 Python
【Leetcode刷题Python】106.相交链表
采用双指针法来找出两个链表的相交起始节点,并详细解释了算法的时间和空间复杂度。
24 1
|
5月前
|
存储 算法 数据可视化
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
深入解析力扣160题:相交链表的解决方法(哈希表法与双指针法详细图解)
|
6月前
|
C++
[leetcode 链表] 反转链表 vs 链表相交
[leetcode 链表] 反转链表 vs 链表相交
|
6月前
|
C语言 C++ 索引
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
【力扣】141. 环形链表、160. 相交链表、206.反转链表、234. 回文链表
|
6月前
|
算法
LeetCode刷题---160. 相交链表(双指针-对撞指针)
LeetCode刷题---160. 相交链表(双指针-对撞指针)