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

[Swift]LeetCode718.最长重复子数组|MaximumLengthofRepeatedSubarray

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

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

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

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

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

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1]. 

Note:

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

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释: 
长度最长的公共子数组是 [3, 2, 1]。

说明:

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

308ms

 1 class Solution {
 2     func findLength(_ A: [Int], _ B: [Int]) -> Int {
 3         var ret = 0
 4         let lenA = A.count, lenB = B.count
 5         for k in 1..<(lenA + lenB) {
 6             var i = max(0, lenA - k)
 7             var j = max(0, k - lenA)
 8             var len = 0
 9             while i < lenA && j < lenB {
10                 len = (A[i] == B[j]) ? (len + 1) : 0
11                 ret = max(ret, len)
12                 i += 1
13                 j += 1
14             }
15         }
16         return ret
17     }
18 }

1304ms

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

Runtime: 2028 ms
Memory Usage: 25.4 MB
 1 class Solution {
 2     func findLength(_ A: [Int], _ B: [Int]) -> Int {
 3         var res:Int = 0
 4         var dp:[[Int]] = [[Int]](repeating:[Int](repeating:0,count:B.count + 1),count:A.count + 1)
 5         for i in 1..<dp.count
 6         {
 7             for j in 1..<dp[i].count
 8             {
 9                 dp[i][j] = (A[i - 1] == B[j - 1]) ? dp[i - 1][j - 1] + 1 : 0
10                 res = max(res, dp[i][j])
11             }
12         }
13         return res
14     }
15 }

 

 


鲜花

握手

雷人

路过

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

请发表评论

全部评论

专题导读
上一篇:
[Swift]LeetCode295.数据流的中位数|FindMedianfromDataStream发布时间:2022-07-13
下一篇:
[Swift]LeetCode916.单词子集|WordSubsets发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

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

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

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