北京地铁建设的网站,如何让百度不收录网站,建站模板工程造价,ssh架构jsp网站开发★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★➤微信公众号#xff1a;山青咏芝#xff08;shanqingyongzhi#xff09;➤博客园地址#xff1a;山青咏芝#xff08;https://www.cnblogs.com/strengthen/#xff09;➤GitHub地址山青咏芝shanqingyongzhi➤博客园地址山青咏芝https://www.cnblogs.com/strengthen/➤GitHub地址https://github.com/strengthen/LeetCode➤原文地址https://www.cnblogs.com/strengthen/p/10783476.html ➤如果链接不是山青咏芝的博客园地址则可能是爬取作者的文章。➤原文已修改更新强烈建议点击原文地址阅读支持作者支持原创★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ 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,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: 2 Note: 1 A.length 5001 B.length 5001 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 A.length 5001 B.length 5001 A[i], B[i] 200076ms 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.count4 let m:Int B.count5 var dp:[[Int]] [[Int]](repeating:[Int](repeating: 0, count:m 1),count:n 1)6 dp[0][0] 07 for i in 1...n8 {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.count1), count: A.count1)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 A7 arrB B8 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 } 转载于:https://www.cnblogs.com/strengthen/p/10783476.html
