华为 OD 训练营 · 题解精讲
LC1035. 不相交的线
LC1035. 不相交的线
题目描述
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足： nums1[i] == nums2[j] 且绘制的直线不与任何其他连线（非水平线）相交。 请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。 以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1： Eq3ibwJk1o1B1gxgBk1cfbE6nzg.png
输入：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
提示： 1 <= nums1.length, nums2.length <= 500 1 <= nums1[i], nums2[j] <= 2000
题目解析
解题思路
本题要求绘制最多的不相交连线，每个数字只能使用一次，且连线不能交叉。这个约束实际上等价于求两个数组的最长公共子序列（LCS）长度：因为如果我们在两个数组中各选一个匹配位置，连线不能交叉意味着匹配的索引必须同时递增，这正是 LCS 的定义。
因此，本题直接转化为经典的 LCS 动态规划问题，使用二维 DP 求解。
关键步骤
1. 定义状态：dp[i][j] 表示 nums1[0..i-1] 和 nums2[0..j-1] 的最长公共子序列长度（即最大不相交连线数）。 2. 状态转移：
- 若
nums1[i-1] == nums2[j-1]，则当前字符可以匹配，dp[i][j] = dp[i-1][j-1] + 1 - 否则，取
dp[i-1][j]和dp[i][j-1]中的较大值
3. 初始化：dp[0][*] = dp[*][0] = 0，表示空序列的 LCS 长度为 0。 4. 最终答案：dp[n1][n2]
转移过程示意（以示例1 nums1=[1,4,2], nums2=[1,2,4] 为例，仅显示部分）：
dp 表（i行对应nums1，j列对应nums2）：
j=0 1 2 3
i=0 0 0 0 0
i=1 0 1 1 1 (nums1[0]=1 匹配 nums2[0]=1)
i=2 0 1 1 2 (nums1[1]=4 匹配 nums2[2]=4)
i=3 0 1 2 2 (nums1[2]=2 匹配 nums2[1]=2)复杂度分析
- 时间复杂度：O(n1 × n2)，两层循环遍历所有 i、j 组合。
- 空间复杂度：O(n1 × n2)，使用二维 DP 数组。可优化为 O(min(n1, n2)) 的一维滚动数组，但参考代码未做此优化。
参考代码
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
# 本质上就是1143题，求最长公共子序列
n1, n2 = len(nums1), len(nums2)
dp = [[0] * (n2+1) for _ in range(n1+1)]
for i in range(1, n1+1):
for j in range(1, n2+1):
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[n1][n2]