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

本文主要是介绍代碼隨想錄算法訓練營|第五十五天|1143.最长公共子序列、1035.不相交的线、53. 最大子序和。刷题心得(c++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

讀題

1143.最长公共子序列

自己看到题目的第一想法

看起來跟最長重複子数組很類似,但是要怎麼去推遞推的狀態沒有想法

看完代码随想录之后的想法

看完之後,大概釐清了整體想法,可以想成說,因為我們要考慮的是不連續的子序列,所以會分成兩種狀態,一個是不相同,不相同的話需要看之前的序列有沒有重複,之前包括兩個方面,縱向與橫向關係,要取最大的,因為這個緣故,在相同的時候,因為之前的數都考慮過縱向與橫向的關係,可以直接從左上角跟重複子序列一樣,求出該值。 至於初始化的部分,在定義下標時,i、j都設定為i - 1 或者說 1 ~ i ,讓後續的遞推公式以及初始化都可以比較簡便。

1035.不相交的线

自己看到题目的第一想法

看到這題,看到卡哥的提示,觀察過後其實就跟最長的公共子序列一樣,如果有一個子序列是共有的,那最長的公共子序列一定是可以連接最多不相交的線,整體的概念是一致的。

53. 最大子序和

看完代码随想录之后的想法

其實整體概念跟連續遞增子序有點像,改為將数組變動 dp[i - 1] + nums[i] 以及 nums[i]的差異,看完程式碼後理解上不會太過於困難。

1143.最长公共子序列 - 實作

思路

  1. 定義DP數組以及下標的含意

    dp[i][j] 代表 0~ i - 1 的text1 以及 0 ~ j - 1 的text2 最长公共子序列長度為dp[i][j]

  2. 遞推公式

    分成兩種狀態相同與不相同

    不相同的話需要看之前的序列有沒有重複,之前包括兩個方面,縱向與橫向關係,要取最大的

    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    相同的時候,因為之前的數都考慮過縱向與橫向的關係,可以直接從左上角跟重複子序列一樣

    dp[i][j] = dp[i - 1][j - 1] + 1;

  3. 根據遞推公式、題意以及定義,確定DP數組如何初始化

    最少為0,所以初始化為0

  4. 確定遍歷順序

    因為需要左上角的數據來進行遍歷,所以是由前往後。

Code

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

1035.不相交的线 - 實作

思路

  1. 定義DP數組以及下標的含意

    dp[i][j] 代表 0~ i - 1 的nums1 以及 0 ~ j - 1 的nums2 最长不相交的线為dp[i][j]

  2. 遞推公式

    分成兩種狀態相同與不相同

    不相同的話需要看之前的序列有沒有重複,之前包括兩個方面,縱向與橫向關係,要取最大的

    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

    相同的時候,因為之前的數都考慮過縱向與橫向的關係,可以直接從左上角跟重複子序列一樣

    dp[i][j] = dp[i - 1][j - 1] + 1;

  3. 根據遞推公式、題意以及定義,確定DP數組如何初始化

    最少為0,所以初始化為0

  4. 確定遍歷順序

    因為需要左上角的數據來進行遍歷,所以是由前往後。

Code

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

53. 最大子序和 - 實作

思路

  1. 定義DP數組以及下標的含意

    dp[i] 代表 i 之前包含i 的number[i] 結尾的最大子序和是多少

  2. 遞推公式

    當前的数加上前面的數比較大還是當前的數比較大,取大的。

    dp[i] = max(dp[i - 1] + nums[i], nums[i])

    if dp [i] > result 更新result

  3. 根據遞推公式、題意以及定義,確定DP數組如何初始化

    將數組初始化為最小值,以及result = nums[0]

  4. 確定遍歷順序

    0 到 i 因為需要前面的數據來進行遍歷,所以是由前往後。

Code

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

總結

自己实现过程中遇到哪些困难

一開始對於最長公共子序列不太了解,但看完講解後,其實就是在重複子序列的基礎上考慮橫向與縱向的關係,以及最大子序和整體很像最長連續子序列,只是思考上需要進行轉換﹐整體而言,今天題目主要是思路上需要做一些改變,不然很容易繞進去。

今日收获,记录一下自己的学习时长

今天大概學習了2hr,整體是很充實的,尤其理解最長公共子序列,在想法上接續到的二題不相交的線就會非常清晰。

相關資料

● 今日学习的文章链接和视频链接

1143.最长公共子序列

视频讲解:动态规划子序列问题经典题目 | LeetCode:1143.最长公共子序列_哔哩哔哩_bilibili

https://programmercarl.com/1143.最长公共子序列.html

1035.不相交的线

视频讲解:动态规划之子序列问题,换汤不换药 | LeetCode:1035.不相交的线_哔哩哔哩_bilibili

https://programmercarl.com/1035.不相交的线.html

53. 最大子序和

视频讲解:看起来复杂,其实是简单动态规划 | LeetCode:53.最大子序和_哔哩哔哩_bilibili

https://programmercarl.com/0053.最大子序和(动态规划).html

这篇关于代碼隨想錄算法訓練營|第五十五天|1143.最长公共子序列、1035.不相交的线、53. 最大子序和。刷题心得(c++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/318690

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C++ 中的 if-constexpr语法和作用

《C++中的if-constexpr语法和作用》if-constexpr语法是C++17引入的新语法特性,也被称为常量if表达式或静态if(staticif),:本文主要介绍C++中的if-c... 目录1 if-constexpr 语法1.1 基本语法1.2 扩展说明1.2.1 条件表达式1.2.2 fa

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++中::SHCreateDirectoryEx函数使用方法

《C++中::SHCreateDirectoryEx函数使用方法》::SHCreateDirectoryEx用于创建多级目录,类似于mkdir-p命令,本文主要介绍了C++中::SHCreateDir... 目录1. 函数原型与依赖项2. 基本使用示例示例 1:创建单层目录示例 2:创建多级目录3. 关键注

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++常见容器获取头元素的方法大全

《C++常见容器获取头元素的方法大全》在C++编程中,容器是存储和管理数据集合的重要工具,不同的容器提供了不同的接口来访问和操作其中的元素,获取容器的头元素(即第一个元素)是常见的操作之一,本文将详细... 目录一、std::vector二、std::list三、std::deque四、std::forwa

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++ 各种map特点对比分析

《C++各种map特点对比分析》文章比较了C++中不同类型的map(如std::map,std::unordered_map,std::multimap,std::unordered_multima... 目录特点比较C++ 示例代码 ​​​​​​代码解释特点比较1. std::map底层实现:基于红黑

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程