0%

1035.不相交的线(Medium)

LeetCodee每日一题(2021.05.21)之不相交的线
难度:中等

0.0.1. 题目

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

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

nums1[i] == nums2[j]
且绘制的直线不与任何其他连线(非水平线)相交。
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。

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

示例1
img1

1
2
3
4
输入:nums1 = [1,4,2], nums2 = [1,2,4]
输出:2
解释:可以画出两条不交叉的线,如上图所示。
但无法画出第三条不相交的直线,因为从 nums1[1]=4 到 nums2[2]=4 的直线将与从 nums1[2]=2 到 nums2[1]=2 的直线相交。

示例2

1
2
输入:nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2]
输出:3

示例3

1
2
输入:nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1]
输出:2

提示:

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

0.0.2. 暂时错误的思路

一开始看到这道题,我想到的是数学中如何验证平面上两条线段是否相交,也就是讲问题转化成了:给定两个线段的坐标(也就是四个点的直角坐标系坐标),判断这两个线段是否相交。

假定输入p1,p2,q1,q2四个点的坐标,p1p2为一条线段,q1q2为另外一条线段。

两条线段相交只有两种情况:

  1. 其中一条线段的某一端点在另一条线段上
  2. 两条线段成X型

详细的解题过程见:参考

实际上没有用上的代码部分:

1
2
3
4
5
def judge(a,b,c,d):
if min(a[0],b[0])<=max(c[0],d[0]) and min(c[1],d[1])<=max(a[1],b[1]) and min(c[0],d[0])<=max(a[0],b[0]) and min(a[1],b[1])<=max(c[1],d[1]):
print("True")
else:
print("False")

0.0.3. 解题思路

这道题LC解题思路里给出的基本为动态规划的解法,也是我算法里最差的一部分。

定义

  • dp[i][j]表示数组nums1的前i个数字和数组nums2的前j个数字能形成的不相交的线的最大数。(大问题化小问题)
  • 其中m为nums1长度,n为nums2长度

重点:状态转移方程

  • 对于任意 0 < j < m, 0 < j < n, 当nums1[i]和nums2[j]`数字相同的时候:
    • 当前最大连线数又可以增加一条,用dp[i-1][j-1]+1表示
  • 如果数字不相同,可以从nums1或nums2去掉一个数字进行比较
    • 比如比较 dp[i-1][j]dp[i−1][j] 和 dp[i][j-1]dp[i][j−1], 取两者中的较大值来更新 dp[i][j]dp[i][j] 即可.
    • dp[i-1][j]dp[i−1][j] 代表不考虑 nums[i]nums[i] 字符, nums[j]nums[j] 是考虑的, 但不是必须包含. dp[i][j-1]dp[i][j−1] 同理
  • 最后,遍历完成后,结果在dp[m][n]上

实现代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
def maxUncrossedLines(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: int
"""

m, n = len(nums1),len(nums2)

dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
dp[i][j] = max(dp[i-1][j],dp[i][j-1])
if nums1[i-1] == nums2[j-1]:
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1)

return dp[m][n]

赤小豆

-------------本文结束感谢您的阅读-------------