最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

每日播报!【算法训练营day53】LeetCode1143. 最长公共子序列 LeetCode1035. 不相交的线 LeetCode53. 最大子序和

来源：博客园

LeetCode1143. 最长公共子序列

题目链接：1143. 最长公共子序列

独上高楼，望尽天涯路

和之前那道题思路又不太一样了，第一次接触还是挺难想出来的。

慕然回首，灯火阑珊处

首先是dp数组以及下标的含义。


(资料图片仅供参考)

dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列长度为dp[i][j]。

然后是确定递推公式。

主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同，那就看看截止到text1[i - 2]与text2[j - 1]的最长公共子序列和 text1[i - 1]与text2[j - 2]的最长公共子序列，取最大的。

这种解题思路只能多做，多见，多积累。

class Solution {public:    int longestCommonSubsequence(string text1, string text2) {        vector> dp(text1.size() + 1, vector(text2.size() + 1, 0));        for (int i = 1; i < text1.size() + 1; i++) {            for (int j = 1; j < text2.size() + 1; j++) {                if (text1[i - 1] == text2[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[text1.size()][text2.size()];    }};

LeetCode1035. 不相交的线

题目链接：1035. 不相交的线

独上高楼，望尽天涯路

和上一道题不能说很像，只能说一模一样。

慕然回首，灯火阑珊处

代码都不用改。

class Solution {public:    int maxUncrossedLines(vector& nums1, vector& nums2) {        vector> dp(nums1.size() + 1, vector(nums2.size() + 1, 0));        for (int i = 1; i <= nums1.size(); i++) {            for (int j = 1; j <= nums2.size(); j++) {                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[nums1.size()][nums2.size()];    }};

LeetCode53. 最大子序和

题目链接：53. 最大子序和

独上高楼，望尽天涯路

这次思路想对了一半，没有接着想下去，感觉还是没有到开窍的那个点。

慕然回首，灯火阑珊处

首先是确定dp数组以及下标的含义。

dp[i]：以nums[i]为结尾的最大连续子序列和为dp[i]。

为了通过dp[i-1] + nums[i]推导出dp[i]，所以一定是要以nums[i]为结尾，同时应该想到答案需要用result变量在遍历过程中获得。

然后是确实递推公式。

dp[i]只有两个方向可以推出来：

  • dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
  • nums[i]，即：从头开始计算当前连续子序列和

一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

这里不需要去考虑nums[i]的正负，因为限制条件是nums[i]为结尾，所以必须带着nums[i]；需要考虑的是要不要带着dp[i-1]，即之前的最大连续子序列和，用max来做决定，最后要最大的那个就行了。

class Solution {public:    int maxSubArray(vector& nums) {        vector dp(nums.size(), 0);        dp[0] = nums[0];        int result = dp[0];        for (int i = 1; i < nums.size(); i++) {            dp[i] = max(dp[i - 1] + nums[i], nums[i]);            if (result < dp[i]) {                result = dp[i];            }         }        return result;    }};

关键词： 独上高楼 灯火阑珊处 望尽天涯路