LeetCode 题解工作台
不相交的线
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。 现在，可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，这些直线需要同时满足： nums1[i] == nums2[j] 且绘制的直线不与任何其他连线（非水平线）相交。 请注意，连线即使在端点也不能…
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
我们定义 表示 前 个数和 前 个数的最大连线数。初始时 $f[i][j] = 0$，答案即为 。 当 $\textit{nums1}[i-1] = \textit{nums2}[j-1]$ 时，我们可以在 的前 个数和 的前 个数的基础上增加一条连线，此时 $f[i][j] = f[i-1][j-1] + 1$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
在两条独立的水平线上按给定的顺序写下 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
提示：
1 <= nums1.length, nums2.length <= 5001 <= nums1[i], nums2[j] <= 2000
解题思路
方法一：动态规划
我们定义 表示 前 个数和 前 个数的最大连线数。初始时 ，答案即为 。
当 时，我们可以在 的前 个数和 的前 个数的基础上增加一条连线，此时 。
当 时，我们要么在 的前 个数和 的前 个数的基础上求解，要么在 的前 个数和 的前 个数的基础上求解，取两者的最大值，即 。
最后返回 即可。
时间复杂度 ，空间复杂度 。其中 和 分别是 和 的长度。
class Solution:
def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
m, n = len(nums1), len(nums2)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i, x in enumerate(nums1, 1):
for j, y in enumerate(nums2, 1):
if x == y:
f[i][j] = f[i - 1][j - 1] + 1
else:
f[i][j] = max(f[i - 1][j], f[i][j - 1])
return f[m][n]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n1 \cdot n2) |
| 空间 | O(n2) |
面试官常问的追问
外企场景- question_mark
The candidate demonstrates an understanding of dynamic programming and its application to problems with overlapping subproblems.
- question_mark
The candidate efficiently uses space optimization techniques for dynamic programming.
- question_mark
The candidate can identify the base cases and correctly initialize the dynamic programming table.
常见陷阱
外企场景- error
Forgetting to handle the base cases when either nums1 or nums2 is empty.
- error
Incorrectly filling the DP table, particularly when updating dp[i][j] based on conditions like nums1[i] == nums2[j].
- error
Using too much space for the DP table without considering the optimization to reduce space complexity.
进阶变体
外企场景- arrow_right_alt
Implementing a solution that handles multiple arrays rather than just two.
- arrow_right_alt
Extending the problem to consider more than one match between elements at the same index.
- arrow_right_alt
Considering the problem with additional constraints, like limiting the number of allowed lines.