LeetCode:718. 最长重复子数组 - Python

这篇具有很好参考价值的文章主要介绍了LeetCode:718. 最长重复子数组 - Python。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

718. 最长重复子数组

问题描述:

给两个整数数组 nums1nums2 ,返回 两个数组中 公共的长度最长子数组长度

示例 1:

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

示例 2:

输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出:5

提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 100

问题分析:

  • 动态规划老题目了,前面有 LeetCode:1143. 最长公共子序列 - Python , 求子序列的题目,这个是子数组,如果是字符串的话就求子串,大家注意子串子序列是有区别的哦。子序列 一般是指的是相对位置不变就是子序列子串严格连续的。
  • 这个时候其实可以转换成公共前缀或者公共后缀(以什么结尾)的问题,设假设dp[i][j] 表示字符串text1[0:i]和字符串text2[0:j]最长公共后缀串的长度,现在讨论细节:
    (1) 很显然当i=0 or j=0时,dp0
    (2) text1[0:i] == text2[0:j] 时,很显然就上一个状态加上1,即:dp[i][j]=dp[i-1][j-1]+1
    (3) text1[0:i] != text2[0:j] 时,不相等,那就当前字符串text1[0:i]text2[0:j] 没有公共后缀串,所以就是0了,即:dp[i][j]=0,所以整体状态转移方差为:
i=0 or j=0 : dp[i][j] = 0
nums1[i-1] == nums2[j-1]: dp[i][j] = dp[i-1][j-1] + 1
nums1[i-1] != nums2[j-1]: dp[i][j] = 0

Python3实现:

# @Time   :2023/09/02
# @Author :Liu
# 动态规划

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:

        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        ans, sub = 0, ''  # 最长公共子串长度,最长公共子串

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                # else:
                #     dp[i][j] = 0  # 这一步其实没必要,本身就为0

                if ans < dp[i][j]:  # 更新最长子串
                    ans = dp[i][j]
                    # sub = nums1[i-ans: i]  # 获取字符串

        return ans  # , sub


if __name__ == '__main__':
    solu = Solution()
    nums1, nums2 = [1, 2, 3, 2, 1], [3, 2, 1, 4, 7]
    print(solu.findLength(nums1, nums2))  # 3 [3, 2, 1]

相关参考:题目链接
声明: 总结学习,有问题或不当之处,可以批评指正哦,谢谢。文章来源地址https://www.toymoban.com/news/detail-693796.html

到了这里,关于LeetCode:718. 最长重复子数组 - Python的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode动态规划#14】子序列系列题(最长递增子序列、最长连续递增序列、最长重复子数组、最长公共子序列)

    力扣题目链接(opens new window) 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。 示例 1: 输入:nums = [10,9,2,5,3,7,101,18] 输出

    2024年02月01日
    浏览(56)
  • 算法刷题Day 52 最长递增子序列+最长连续递增子序列+最长重复子数组

    我自己想出来的方法,时间复杂度应该是 O(n2) 滑动窗口 连续的话,可以考虑用滑动窗口 动态规划 贪心算法

    2024年02月14日
    浏览(54)
  • 力扣(LeetCode)算法_C++——替换后的最长重复字符

    给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后,返回包含相同字母的最长子字符串的长度。 示例 1: 输入:s = “ABAB”, k = 2 输出:4 解释:用两个’A’替换为两个’B’

    2024年02月09日
    浏览(44)
  • 最长重复子数组,最大子序和,最长公共子序列

    欢迎批评指正!

    2024年04月13日
    浏览(62)
  • 算法leetcode|80. 删除有序数组中的重复项 II(rust重拳出击)

    给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。 不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 说明 : 为什么返回数值是整数,但输出的答案是

    2024年02月09日
    浏览(51)
  • day55 最长递增子序列 最长连续递增子序列 最长重复子数组

    题目链接 300 最长递增子序列 题意 找到整数数组nums的最长严格递增子序列的长度(子序列并不改变原始的顺序,但是可以删除元素) 动态规划 动规五部曲 1)dp数组及下标i的含义 dp[i] 表示以nums[i]为结尾的最长递增子序列的长度 2)dp数组初始化 根据定义 长度至少是1  dp

    2024年04月11日
    浏览(61)
  • leetcode:无重复字符的最长字串(详解)

    给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 HashMapCharacter, Integer map = new HashMap();创建一个HashMap,用于存储字符及其最后一次出现的位置。 int max = 0;: 用于记录最长子串的长度。 int start = 0;: 用于记录当前子串的起始位置。 for (int i = 0; i s.length(); i

    2024年02月22日
    浏览(38)
  • LeetCode 3 无重复字符的最长子串

    给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 示例 2: 示例 3: 提示: 0 = s.length = 5 * 104 s 由英文字母、数字、符号和空格组成 依次遍历字符串,如果这个字符在子串里,则把子串的这个字符之前的都删除,加新的字符,否则继续遍历即可。

    2024年02月07日
    浏览(37)
  • LeetCode 3. 无重复字符的最长子串

    力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 我们需要找的是含重复元素的最长子串,当然直接暴力求解固然简单。但是可能引发的情况是超时,而且面试官想看到的也不是让你去暴力解决这类问题。因此我们使用哈希+滑动窗口的思想来解决。 使用哈希表的缘故是更

    2024年02月09日
    浏览(42)
  • 【Leetcode】3. 无重复字符的最长子串

    给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。 示例1: 示例2: 示例3: 提示 : 0 = s . l e

    2024年02月10日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包