不相交的线
难度:
标签:
题目描述
在两条独立的水平线上按给定的顺序写下 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
代码结果
运行时间: 35 ms, 内存: 16.2 MB
解释
方法:
本题解的思路是将问题转化为寻找两个数组之间的最长递增子序列（Longest Increasing Subsequence, LIS）的问题。首先，为了方便处理，确保nums1是两个数组中较短的一个。然后，使用一个字典dic来存储nums1中每个数字的所有出现位置，并按照逆序存储，以便后续操作。接下来，遍历nums2数组，将nums2中的元素按照在nums1中出现的位置顺序记录到一个列表tmp中。这一步是为了找到所有在nums1和nums2中都出现的元素，并保留其在nums1中的位置。最后，通过计算tmp列表的最长递增子序列的长度来确定最大的不相交的线的数量，这是因为这些位置的递增序列对应于不相交的连接线。
时间复杂度:
O(m log m)
空间复杂度:
O(n + m)
代码细节讲解
🦆
为什么在解决问题时首先选择将nums1和nums2中较短的数组作为nums1？这种选择对算法的效率有何影响？
▷🦆
在构建字典dic时，为什么选择逆序存储nums1中元素的出现位置？这样做有什么特别的优势吗？
▷🦆
如何理解算法中对tmp列表使用二分查找来计算最长递增子序列（LIS）的过程？
▷🦆
给定的算法实现中，是否考虑了nums1或nums2为空的情况，如果没有，应该如何处理？
▷相关问题
编辑距离
给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符
示例 1：
输入：word1 = "horse", word2 = "ros" 输出：3 解释： horse -> rorse (将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e')
示例 2：
输入：word1 = "intention", word2 = "execution" 输出：5 解释： intention -> inention (删除 't') inention -> enention (将 'i' 替换为 'e') enention -> exention (将 'n' 替换为 'x') exention -> exection (将 'n' 替换为 'c') exection -> execution (插入 'u')
提示：
0 <= word1.length, word2.length <= 500word1和word2由小写英文字母组成