首页 > 其他分享 >LeetCode 1035.不相交的线

LeetCode 1035.不相交的线

时间:2023-08-17 21:32:17浏览次数:48  
标签:直线 示例 int 相交 LeetCode nums1 nums2 1035

1.题目:

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

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

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

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

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

 

示例 1:

LeetCode 1035.不相交的线_连线

输入: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



2.代码:

跟最长公共子序列一样

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length+1][nums2.length+1];
        for(int i=1;i<=nums1.length;i++){
            for(int j=1;j<=nums2.length;j++){
                if(nums1[i-1]==nums2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
        return dp[nums1.length][nums2.length];
    }
}










标签:直线,示例,int,相交,LeetCode,nums1,nums2,1035
From: https://blog.51cto.com/u_15806469/7127596

相关文章

  • LeetCode 718.最长重复子数组
    1.题目:给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。 示例1:输入:nums1=[1,2,3,2,1],nums2=[3,2,1,4,7]输出:3解释:长度最长的公共子数组是[3,2,1]。示例2:输入:nums1=[0,0,0,0,0],nums2=[0,0,0,0,0]输出:52.代码:classSo......
  • LeetCode 1143.最长公共子序列
    1.题目:给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。例如,"......
  • Leetcode 19. 删除链表的倒数第N个结点(Remove nth node from end of list)
    题目链接给你一个链表,删除链表的倒数第n个结点,并且返回链表的头结点.示例1:输入:head=[1,2,3,4,5],n=2输出:[1,2,3,5]示例2:输入:head=[1],n=1输出:[]提示:链表中结点的数目为sz1<=sz<=300<=Node.val<=1001<=n<=sz思路暴力解法:可以先......
  • LeetCode 674.最长连续递增序列
    1.题目:给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。连续递增的子序列 可以由两个下标 l 和 r(l<r)确定,如果对于每个 l<=i<r,都有 nums[i]<nums[i+1] ,那么子序列 [nums[l],nums[l+1],...,nums[r-1],nums[r]] 就是连续递增......
  • LeetCode 300.最长递增子序列
    1.题目:给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。示例1:输入:nums=[10,9,2,5,3,7,101,18]输出:4解释:最长递增子序列是[2......
  • LeetCode 714.买卖股票的最佳时机含手续费
    1.题目:给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格;整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。注意:这里的一笔交易......
  • 第 358 场周赛 - 力扣(LeetCode)
    第358场周赛-力扣(LeetCode)2815.数组中的最大数对和-力扣(LeetCode)双for遍历即可classSolution{public:intmaxSum(vector<int>&nums){autore=[](intx){intma=0;while(x){if(x%10>ma)......
  • 【leetcode】404 左叶子之和
    https://leetcode.cn/problems/sum-of-left-leaves/description/【分析】该题要求左叶子之和。如果我们对当前节点进行叶子节点的判断,那么我们是不知道当前节点是左叶子还是右叶子的。所以我们应该在叶子结点的上层(父节点)进行判断。【代码】classSolution:defsumOfL......
  • LeetCode -- 19. 删除链表的倒数第 N 个结点
     一般的删除问题,可以直接删除(找符合条件的,找到了直接删掉),延迟删除(打标记,找完了再删除),栈,双指针 在链表中删除一个节点,要找到其前面一个节点cur,然后cur->next=cur->next->next即可 方法一:直接删除我们先算出链表长度len,要删除倒第n个节点就是删除第len-n......
  • LeetCode 121.买卖股票的最佳时机
    1.题目:给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获......