• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1035.不相交的线|UncrossedLines

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

We write the integers of A and B (in the order they are given) on two separate horizontal lines.

Now, we may draw a straight line connecting two numbers A[i] and B[j] as long as A[i] == B[j], and the line we draw does not intersect any other connecting (non-horizontal) line.

Return the maximum number of connecting lines we can draw in this way.

Example 1:

Input: A = [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 = [10,5,2,1,5,2]
Output: 3

Example 3:

Input: A = [1,9,2,5,1]
Output: 2

Note:

  1. 1 <= A.length <= 500
  2. 1 <= B.length <= 500
  3. 1 <= A[i], B[i] <= 2000 

 我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在,我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线,只要 A[i] == B[j],且我们绘制的直线不与任何其他连线(非水平线)相交。 

以这种方法绘制线条,并返回我们可以绘制的最大连线数。

示例 1:

输入:A = [1,4,2], B = [1,2,4]
输出:2
解释:
我们可以画出两条不交叉的线,如上图所示。
我们无法画出第三条不相交的直线,因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。

示例 2:

输入:A = [2,5,1,2,5], B = [10,5,2,1,5,2]
输出:3 

示例 3:

输入:A = [1,3,7,1,7,5], B = [1,9,2,5,1]
输出:2

提示: 

  1. 1 <= A.length <= 500
  2. 1 <= B.length <= 500
  3. 1 <= A[i], B[i] <= 2000

76ms
 1 class Solution {
 2     func maxUncrossedLines(_ A: [Int], _ B: [Int]) -> Int {
 3         var dp = Array(repeating: Array(repeating: 0, count: B.count), count: A.count)        
 4         var res = 0        
 5         for row in 0 ..< A.count {
 6             for col in 0 ..< B.count {
 7                 dp[row][col] = max(col > 0 ? dp[row][col - 1] : 0, row > 0 ? dp[row - 1][col] : 0)
 8                 if A[row] == B[col] {
 9                     dp[row][col] = max(dp[row][col], col > 0 && row > 0 ? dp[row - 1][col - 1] + 1 : 1)
10                     
11                     res = max(res, dp[row][col])
12                 }    
13             }
14         }
15         return res
16         
17     }
18 }

Runtime: 84 ms

Memory Usage: 18.7 MB 
 1 class Solution {
 2     func maxUncrossedLines(_ A: [Int], _ B: [Int]) -> Int {
 3         let n:Int = A.count
 4         let m:Int = B.count
 5         var dp:[[Int]] = [[Int]](repeating:[Int](repeating: 0, count:m + 1),count:n + 1)
 6         dp[0][0] = 0
 7         for i in 1...n
 8         {
 9             for j in 1...m
10             {
11                 if A[i - 1] == B[j - 1]
12                 {
13                     dp[i][j] = dp[i - 1][j - 1] + 1
14                 }
15                 else
16                 {
17                      dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
18                 }
19             }
20         }
21         return dp[n][m]
22     }
23 }

92ms

 1 class Solution {
 2     func maxUncrossedLines(_ A: [Int], _ B: [Int]) -> Int {                
 3         var dp = [[Int]](repeating: [Int](repeating: 0, count: B.count+1), count: A.count+1)
 4         for i in 1...A.count {
 5             for j in 1...B.count {
 6                 if A[i - 1] == B[j - 1] {
 7                     dp[i][j] = 1 + dp[i - 1][j - 1]
 8                 } else {
 9                     dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])
10                 }
11             }
12         }
13         return dp[A.count][B.count]
14     }
15 }

196ms

 1 class Solution {
 2     var dp = [[Int?]]()
 3     var arrA = [Int]()
 4     var arrB = [Int]()
 5     func maxUncrossedLines(_ A: [Int], _ B: [Int]) -> Int {
 6         arrA = A
 7         arrB = B
 8         dp = Array(repeating: Array(repeating: nil, count: B.count), count: A.count)
 9         
10         return helper(startA: 0, startB: 0)
11     }
12     
13     private func helper(startA: Int, startB: Int) -> Int {
14         if let result = dp[startA][startB] {
15             return result
16         }
17         
18         if startA == arrA.count - 1 && startB == arrB.count - 1 {
19             let result = arrA[startA] == arrB[startB] ? 1 : 0
20             dp[startA][startB] = result
21             return result
22         }
23         
24         if startA == arrA.count - 1 || startB == arrB.count - 1{
25             let a = arrA[startA]
26             let b = arrB[startB]
27             let result: Int
28             if a == b {
29                 result = 1
30             } else if startA == arrA.count - 1 {
31                 result = helper(startA: startA, startB: startB + 1)
32             } else {
33                 result = helper(startA: startA + 1, startB: startB)
34             }
35             
36             dp[startA][startB] = result
37             return result
38         }
39         
40         let a = arrA[startA]
41         let b = arrB[startB]
42         let result: Int
43         if a == b {
44             result = helper(startA: startA + 1, startB: startB + 1) + 1
45         } else {
46             result = max(
47                 helper(startA: startA + 1, startB: startB),
48                 helper(startA: startA, startB: startB + 1)
49             )
50         }
51         
52         dp[startA][startB] = result
53         return result
54     }
55 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap