1143. Longest Common Subsequence 1035. Uncrossed Lines 53. Maximum Subarray

这篇具有很好参考价值的文章主要介绍了1143. Longest Common Subsequence 1035. Uncrossed Lines 53. Maximum Subarray。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1143. Longest Common Subsequence

Given two strings text1 and text2, return the length of their longest common subsequenceIf there is no common subsequence, return 0.

subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

  • For example, "ace" is a subsequence of "abcde".

common subsequence of two strings is a subsequence that is common to both strings.

1143. Longest Common Subsequence 1035. Uncrossed Lines 53. Maximum Subarray,java,开发语言 

 

There are two main cases to determine the recursive formula:

1. text1[i - 1] is the same as text2[j - 1]

2. text1[i - 1] is not the same as text2[j - 1].

If text1[i - 1] and text2[j - 1] are the same, then a common element is found, so dp[i][j] = dp[i - 1][j - 1] + 1;

If text1[i - 1] and text2[j - 1] are not the same, then look at the longest common subsequence of text1[0, i - 2] and text2[0, j - 1] and the longest common subsequence of text1[0, i - 1] and text2[0, j - 2] and take the largest.  i.e., dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

1143. Longest Common Subsequence 1035. Uncrossed Lines 53. Maximum Subarray,java,开发语言

2-dimensional DP:

Time complexity: O(m x n)

Space complexity: O(m x n)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # 创建一个二维数组 dp,用于存储最长公共子序列的长度
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]
        
        # 遍历 text1 和 text2,填充 dp 数组
        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                if text1[i - 1] == text2[j - 1]:
                    # 如果 text1[i-1] 和 text2[j-1] 相等,则当前位置的最长公共子序列长度为左上角位置的值加一
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    # 如果 text1[i-1] 和 text2[j-1] 不相等,则当前位置的最长公共子序列长度为上方或左方的较大值
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        # 返回最长公共子序列的长度
        return dp[len(text1)][len(text2)]

 

1-dimensional DP:

Time complexity: O(m x n)

Space complexity: O(m)

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [0] * (n + 1)  # 初始化一维DP数组
        
        for i in range(1, m + 1):
            prev = 0  # 保存上一个位置的最长公共子序列长度
            for j in range(1, n + 1):
                curr = dp[j]  # 保存当前位置的最长公共子序列长度
                if text1[i - 1] == text2[j - 1]:
                    # 如果当前字符相等,则最长公共子序列长度加一
                    dp[j] = prev + 1
                else:
                    # 如果当前字符不相等,则选择保留前一个位置的最长公共子序列长度中的较大值
                    dp[j] = max(dp[j], dp[j - 1])
                prev = curr  # 更新上一个位置的最长公共子序列长度
        
        return dp[n]  # 返回最后一个位置的最长公共子序列长度作为结果

 

1035. Uncrossed Lines

You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.

We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:

  • nums1[i] == nums2[j], and
  • the line we draw does not intersect any other connecting (non-horizontal) line.

Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).

Return the maximum number of connecting lines we can draw in this way.

1143. Longest Common Subsequence 1035. Uncrossed Lines 53. Maximum Subarray,java,开发语言 

 Its  literaly like to get longest common subsequence from  "adb" and "abd"

It's exactly the same as the last question.

class Solution:
    def maxUncrossedLines(self, nums1: List[int], nums2: List[int]) -> int:
        m = len(nums1)
        n = len(nums2)

        dp = [[0] * (n + 1) for _ in range(m + 1)]
       
        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] = max(dp[i - 1][j], dp[i][j - 1])
        
        return dp[-1][-1]

 

53. Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

1143. Longest Common Subsequence 1035. Uncrossed Lines 53. Maximum Subarray,java,开发语言

 第二次还没ac 老了老了

dp:文章来源地址https://www.toymoban.com/news/detail-770077.html

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = [float('-inf')] * len(nums) # 不能 -inf
        dp[0] = nums[0]
        result = dp[0]  #初始化 ,必须要有 ,不能直接max(dp)

        for i in range(1, len(nums)):
            dp[i] = max(nums[i], dp[i - 1] + nums[i]) # 不是dp[i]是num[i] !!!!!!!!!!

            if dp[i] > result:
                result = dp[i]
        
        return result

到了这里,关于1143. Longest Common Subsequence 1035. Uncrossed Lines 53. Maximum Subarray的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 代码随想录第53天|● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和 动态规划

    dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j] 通过pre记录前一个dp[j-1] 循环中记录cur为dp[i],循环结束后再更新pre=cur。 和最长公共子序列相同 注意pre和cur放置的位置 dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i

    2024年03月08日
    浏览(51)
  • 算法 DAY52 动态规划10 1143.最长公共子序列 1035.不相交的线 53. 最大子数组和

    本题和动态规划:718. 最长重复子数组 (opens new window)区别在于这里不要求是连续的了 1、dp数组 dp[i][j]:长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j] 2、递推公式 因为不强调是连续的,当前dp[i][j] 就有三种路径可以选:dp[i-1][j] dp[i][j-1]

    2024年02月03日
    浏览(62)
  • 代碼隨想錄算法訓練營|第五十五天|1143.最长公共子序列、1035.不相交的线、53. 最大子序和。刷题心得(c++)

    目录 讀題 1143.最长公共子序列 自己看到题目的第一想法 看完代码随想录之后的想法 1035.不相交的线 自己看到题目的第一想法 53. 最大子序和 看完代码随想录之后的想法 1143.最长公共子序列 - 實作 思路 Code 1035.不相交的线 - 實作 思路 Code 53. 最大子序和 - 實作 思路 Code 總結

    2024年02月06日
    浏览(64)
  • 最长递增子序列(Longest Increasing Subsequence)-C语言实现

    前言 最长递增子序列属于经典的动态规划问题,属于约束条件下求最大子集的问题。这里的约束条件意思是,子序列需要严格按照递增条件产生,在这个前提之下,我们要求到最长的子序列。这类问题的衍生问题有很多,其本质都是穷举最大化子集。 问题描述 问题其实非常

    2024年02月02日
    浏览(49)
  • PAT 甲级【1007 Maximum Subsequence Sum】

    本题是考察动态规划与java的快速输入: max[i]表示第i个结尾的最大的连续子串和。b begin[i]表示第[begin[i],i]为最大和的开始位置 超时代码: 未超时: 能用动态规划解决的问题,需要满足三个条件:最优子结构,无后效性和子问题重叠。 具有最优子结构也可能是适合用贪心的

    2024年02月08日
    浏览(38)
  • 01-复杂度2 Maximum Subsequence Sum

    比上一题(01-复杂度1 最大子列和问题),要多记录几个内容 首尾元素,当前子序列开头元素,当前子序列结尾元素,最佳子序列开头元素,current是否在此处清零(则下一个元素是开头元素) 时间复杂度 O(n) 空间复杂度 O(1)

    2024年02月16日
    浏览(41)
  • LeetCode //14. Longest Common Prefix

    Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string “”.   Example 1: Input: strs = [“flower”,“flow”,“flight”] Output: “fl” Example 2: Input: strs = [“dog”,“racecar”,“car”] Output: “” Explanation: There is no common prefix among the inp

    2024年02月15日
    浏览(40)
  • LCS2 - Longest Common Substring II

    洛谷LCS2 - Longest Common Substring II 题目大意 给你一些字符串,求它们的最长公共子串。 字符串个数不超过 10 10 10 ,每个字符串的长度不超过 100000 100000 100000 。 题解 可以先看看LCS - Longest Common Substring。 这题与上面那题类似,只不过要多一些操作。 首先,用第一个字符串建一个

    2024年02月12日
    浏览(33)
  • physical lines & logical lines

    In Python, understanding the difference between physical lines and logical lines is crucial for comprehending the structure of a program. Physical Lines Physical lines refer to the lines you actually see in your text editor. Each of these lines is terminated by a newline character. In other words, every time you hit “Enter” in your code editor, you creat

    2024年02月11日
    浏览(35)
  • Leetcode1143. 最长公共子序列

    解题思路 求两个数组或者字符串的最长公共子序列问题,肯定是要用动态规划的。下面的题解并不难,你肯定能看懂。 首先,区分两个概念:子序列可以是不连续的;子数组(子字符串)需要是连续的; 另外,动态规划也是有套路的:单个数组或者字符串要用动态规划时,

    2024年01月25日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包