【leetcode】1035. 不相交的线
距离上次更新本文已经过去了 249 天,文章部分内容可能已经过时,请注意甄别
leetcode 刷题笔记 - 1035. 不相交的线
题目
在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。
现在,可以绘制一些连接两个数字 nums1[i]
和 nums2[j]
的直线,这些直线需要同时满足:
plaintext
1 | nums1[i] == nums2[j] |
请注意,连线即使在端点也不能相交:每个数字只能属于一条连线。
以这种方法绘制线条,并返回可以绘制的最大连线数。
示例
plaintext
1 | 示例 1: |
提示
plaintext
1 | 1 <= nums1.length, nums2.length <= 500 |
思路
这道题乍一看好像没有什么好的办法,但是多举几个例子,就能发现它本质上问的是这两个数组的最长公共子序列。因为只要我们不修改画线的元素在原始数组中的相对位置,那么画出来的线就不会出现交叉,最长公共子序列就符合这个特性,这也是这道题真正询问的点!
来复盘一下最长公共子序列的思路吧,最长公共子序列这个题目非常重要,会被其他很多相似的题目引用。最好是能理解并记忆下来。
首先是 dp 数组的含义,我们定义了二维 dp 数组,含义是 a[i]
和 b[j]
这两个元素(包括他们自己)之前的最长公共子序列的长度。
递推的情况则是 a[i]
和 b[j]
相等的时候,dp[i][j] = dp[i-1][j-1] + 1
;其他情况代表最长公共子序列没有被扩张,则需要采用 “前一位” 的最大值,分别是 i-1(j 不变)和 j-1(i 不变)的两种情况。
代码
完整代码如下,另外的办法可以参考最长公共子序列的题解。
cpp
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 慕雪的寒舍!
评论
表情图片预览
0 条评论
- 最新
- 最热
- 最早
- 作者
关闭评论
通知中心
「此时无声胜有声」
Artalk ErrorTypeError: Failed to fetch,无法获取评论列表数据
点击重新获取 | 打开控制台
点击重新获取 | 打开控制台