【leetcode】1035. Uncrossed Lines
2024-09-24 04:38:40
题目如下:
We write the integers of
A
andB
(in the order they are given) on two separate horizontal lines.Now, we may draw connecting lines: a straight line connecting two numbers
A[i]
andB[j]
such that:
A[i] == B[j]
;- The line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting lines cannot intersect even at the endpoints: each number can only belong to one connecting line.
Return the maximum number of connecting lines we can draw in this way.
Example 1:
Input: A = [1,4,2], B = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from A[1]=4 to B[2]=4 will intersect the line from A[2]=2 to B[1]=2.Example 2:
Input: A = [2,5,1,2,5], B = [10,5,2,1,5,2]
Output: 3Example 3:
Input: A = [1,3,7,1,7,5], B = [1,9,2,5,1]
Output: 2Note:
1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000
解题思路:本题可以采用动态规划的方法。记dp[i][j]为A[i]与B[j]连线后可以组成的最多连线的数量,当然这里A[i]与B[j]连线是虚拟的连线,因此存在A[i] != B[j]的情况。首先来看A[i] == B[j],这说明A[i]与B[i]可以连线,显然有dp[i][j] = dp[i-1][j-1]+1;如果是A[i] != B[j],那么分为三种情况dp[i][j] = max(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]),这是因为A[i]不与B[j]连线,但是A[i]可能可以与B[j]之前所有点的连线,同理B[j]也是一样的。
代码如下:
class Solution(object):
def maxUncrossedLines(self, A, B):
"""
:type A: List[int]
:type B: List[int]
:rtype: int
"""
dp = []
for i in range(len(A)):
dp.append([0] * len(B)) for i in range(len(A)):
for j in range(len(B)):
if A[i] == B[j]:
dp[i][j] = max(dp[i][j],1)
if i - 1 >= 0 and j - 1 >= 0 :
dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1) else:
if i - 1 >= 0 and j - 1 >= 0:
dp[i][j] = max(dp[i][j],dp[i-1][j-1])
if j - 1 >= 0:
dp[i][j] = max(dp[i][j],dp[i][j-1])
if i - 1 >= 0:
dp[i][j] = max(dp[i][j],dp[i-1][j])
return dp[-1][-1]
最新文章
- 【Java EE 学习 24 上】【注解详解】
- javascript:history.go()和History.back()的区别(转载)
- Java程序员的日常 —— Java类加载中的顺序
- DOJO 八 event dojo/on
- 如何杀掉当前正在执行的hadoop任务
- Debian apt-get 无法补全
- PrintDocument组件打印
- canvas图形编辑器
- 视音频编解码学习工程:JPEG分析器
- 关于我的博客(About My Blogs)
- Java基础学习-类型转换之隐式转换
- Centos yum 修改为阿里源以及常用的命令
- 【16】有关python面向对象编程
- underscore函数存在两种用法
- solr 5.3.1安装配置
- Linux 加阿里yum源
- ADOX
- centos7 安装zookeeper 集群
- python 内置函数eval()、exec()、compile()
- L153
热门文章
- The Linux usage model for device tree data
- 图论&;线性基(?)(8.12)
- Openstack_通用模块_Oslo_vmware 创建/删除 vCenter 虚拟机
- 阶段1 语言基础+高级_1-3-Java语言高级_06-File类与IO流_06 Properties集合_1_使用Properties集合存储数据,遍历取出集合中的数据
- Week 7 - 714. Best Time to Buy and Sell Stock with Transaction Fee &; 718. Maximum Length of Repeated Subarray
- request.getParameter() 和request.getAttribute()
- POI读取指定Excel中行与列的数据
- django在线教育网站开发---需求分析
- layui中获取全部提交的数据
- Java基础/利用fastjson反序列化json为对象和对象数组