1号店网站网页特效,深圳公司排名榜,怎么开平台,兰州app制作在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在#xff0c;可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线#xff0c;这些直线需要同时满足满足#xff1a;
nums1[i] nums2[j] 且绘制的直线不与任何其他连线#xff08;非水平线#x…在两条独立的水平线上按给定的顺序写下 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
解题思路
这题本质上就匹配最长公共子序列只不过是把字母换成了数字但是方法上是一样的
代码
class Solution {public int maxUncrossedLines(int[] nums1, int[] nums2) {int nnums1.length,mnums2.length;int[][] dp new int[n1][m1];for (int i1;in;i)for (int j 1; j m; j)dp[i][j]nums1[i-1]nums2[j-1]?dp[i-1][j-1]1:Math.max(dp[i-1][j],dp[i][j-1]);return dp[n][m];}}结果
