欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

2020-07-01-每日一题

程序员文章站 2022-11-30 13:34:25
更多python分类刷题题解代码:请参考github,博客, 知乎718. 最长重复子数组(medium)https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/# 动态规划# dp[i][j]表示以i为结束元素的A和以j为结束的B,的最长的公共子数组的长度# 状态转移方程# if A[i] == B[j] 则, dp[i][j] = dp[i-1][j-1] + 1# else: dp[i][j] =...

更多python分类刷题题解代码:请参考github,博客, 知乎

718. 最长重复子数组(medium)

https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/

# 动态规划
# dp[i][j]表示以i为结束元素的A和以j为结束的B,的最长的公共子数组的长度
# 状态转移方程
#   if A[i] == B[j] 则, dp[i][j] = dp[i-1][j-1] + 1
#   else: dp[i][j] = 0
# 边界条件:
#     dp[0][i] = 1 if A[0] == B[i]
#     dp[i][0] = 1 if A[i] == B[0]

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        if not A: return 0
        l = len(A)
        dp = [[0]*l for _ in range(l)]
        res = 0
        for i in range(l):
            if A[0] == B[i]:
                dp[0][i] = 1
                res = max(dp[0][i], res)
            if A[i] == B[0]:
                dp[i][0] = 1
                res = max(dp[i][0], res)
        
        for i in range(1, l):
            for j in range(1, l):
                if A[i] == B[j]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    res = max(dp[i][j], res)
                else:
                    dp[i][j] = 0
        # print(dp)
        return res

更多python分类刷题题解代码:请参考github,博客, 知乎

更多技术文章请点击查看

本文地址:https://blog.csdn.net/lxztju/article/details/107134813