dangdangA

導(dǎo)航

公告

python活力練習(xí)Day28

題目描述：最長(zhǎng)重復(fù)子數(shù)組

給兩個(gè)整數(shù)數(shù)組 A 和 B ，返回兩個(gè)數(shù)組中公共的、長(zhǎng)度最長(zhǎng)的子數(shù)組的長(zhǎng)度。

示例 1:

輸入:
A: [1,0,0,1,1]
B: [1,0,0,0,1]
輸出: 3
解釋: 
長(zhǎng)度最長(zhǎng)的公共子數(shù)組是 [1,0,0] or [0,0,1]。

說(shuō)明:

1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100

引申概念：

最長(zhǎng)公共子序列：

最長(zhǎng)公共子串：

python代碼：

最長(zhǎng)公共子串：

 1 def findLength( A, B):
 2     n = len(A)
 3     m = len(B)
 4     dis = [[0 for i in range(n + 1)] for j in range(m + 1)]
 5     for i in range(m):
 6         for j in range(n):
 7             if A[i] == B[j]:
 8                 dis[i + 1][j + 1] = dis[i][j] + 1
 9     max = 0
10     for i in range(n+1):
11         for j in range(n+1):
12             if dis[i][j] > max:
13                 max = dis[i][j]
14 
15     return max
16 
17 if __name__ == "__main__":
18 
19     A = [1, 0, 0, 1, 1]
20     B = [1, 0, 0, 0, 1]
21     print(findLength(A,B))

輸出結(jié)果：3 此時(shí)最長(zhǎng)公共子串為[1,0,0] 或者【0,0,1】

		1	0	0	0	1
	0	0	0	0	0	0
1	0	1	0	0	0	1
0	0	0	2	1	1	0
0	0	0	1	3	2	0
1	0	1	0	0	0	3
1	0	1	0	0	0	1

最長(zhǎng)公共子序列：

 1 def findLength( A, B):
 2     n = len(A)
 3     m = len(B)
 4     dis = [[0 for i in range(n + 1)] for j in range(m + 1)]
 5     for i in range(m):
 6         for j in range(n):
 7             if A[i] == B[j]:
 8                 dis[i + 1][j + 1] = dis[i][j] + 1
 9             else:
10                 dis[i + 1][j + 1] = max(dis[i+1][j],dis[i][j+1])
11 
12     return dis[-1][-1]
13 
14 if __name__ == "__main__":
15 
16     A = [1, 0, 0, 1, 1]
17     B = [1, 0, 0, 0, 1]
18     print(findLength(A,B))

輸出結(jié)果：4 此時(shí)最長(zhǎng)公共子序列為[1,0,0,1]

		1	0	0	0	1
	0	0	0	0	0	0
1	0	1	1	1	1	1
0	0	1	2	2	2	2
0	0	1	2	3	3	3
1	0	1	2	3	3	4
1	0	1	2	3	3	4

定義來(lái)源：https://blog.csdn.net/ggdhs/article/details/90713154

題目來(lái)源：https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

posted on 2020-07-01 10:52 dangdangA 閱讀(147) 評(píng)論(0) 收藏舉報(bào)

刷新頁(yè)面返回頂部