代碼隨想錄算法訓練營|第五十四天|300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组。刷题心得(c++)

本文主要是介绍代碼隨想錄算法訓練營|第五十四天|300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组。刷题心得(c++),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

讀題

300.最长递增子序列

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

思想上很簡單,dp[i]表示i之前的包括i的numbers[i]節尾的最長上升子序列的長度

並且透過兩層迴圈,一層遍歷全部,一層遍歷到i,透過比較當前dp[i]還是dp[j] + 1哪個比較大,來更新動態規劃的dp數組數據。

674. 最长连续递增序列

自己看到题目的第一想法

稍微將300轉一下就好,dp[i] 改為到i之前的最長連續子序列長度為dp[i],公式轉為假設nums[i] > nums[i - 1] 就將dp[i] 的值改為前一個值的個數 + 1就好了

718. 最长重复子数组

自己看到题目的第一想法

的確比較有難度,要思考如何去找出重複子序列,但是將nums1以及nums2的對應表畫出來後,會發現可以透過左上角的值來看重複度,假設左上角為1,那就代表前一個num2的值與前一個num1的值相等,所以當前的值如果也相等,那就要基於dp[i - 1][j - 1]的值 + 1,雖然這個想法完整了,但是自己對於下標的定義沒有想的很清楚,主要是透過畫圖模擬,找出規律並推出遞推公式。

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

看完之後,發現卡哥的做法比較直覺一點,但要想到比較難,我的想法主要是透過畫圖推出,而卡哥是直接在整體数組框架上往外擴一層,就免除了我在nums1[i] != nums2[j] 需要做的額外操作,兩者都可以通過,只是方法不同而已,下標的定義也讓我之前比較模糊的定義有了清晰的了解。

300.最长递增子序列 - 實作

思路

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

    dp[i] 代表 i 之前包含i 的number[i] 結尾的最大遞增子序列的長度是多少

  2. 遞推公式

    透過兩層迴圈,一個遍歷numbers.size的數組的長度,一個遍歷到i的長度

    if (number[i] > number[j]) dp[i] = max(dp[i], dp[j] + 1)

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

    每個數做為結尾都至少含有一個,所以將數組初始化為1

  4. 確定遍歷順序

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

    0 到 i - 1 只要都有遍歷到就可以了,往前或往後都沒有關係,但為了方便理解,默認由前往後

Code

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

 

674. 最长连续递增序列 - 實作

思路

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

    dp[i] 代表 i 之前包含i 的number[i] 結尾的最長連續遞增子序列的長度是多少

  2. 遞推公式

    if (number[i] > number[i - 1]) dp[i] = dp[i - 1] + 1;

    假設number[i] > number[i - 1] 代表number[i - 1]之前都是連續遞增的,所以加上當前的數

    如果沒有大於,就維持初始化

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

    每個數做為結尾都至少含有一個,所以將數組初始化為1

  4. 確定遍歷順序

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

Code

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

 

718. 最长重复子数组 - 實作

思路

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

    dp[i][j] 代表 0~ i 的nums1以及 0 ~ j 的nums2最長連續遞增子序列長度為dp[i][j]

  2. 遞推公式

    if(nums1[i] == nums2[j]) { if(i > 0 && j > 0) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] += 1; }

    假設nums1[i] == nums[j] 其中一個不大於 0 則只加一,如果都大於1 則看左上角的數

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

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

  4. 確定遍歷順序

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

Code

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp (nums1.size(), vector<int>(nums2.size(), 0));int result = 0;for(int i = 0; i < nums1.size(); i++) {for(int j = 0; j < nums2.size(); j++) {if(nums1[i] == nums2[j]) {if(i > 0 && j > 0) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] += 1;}if(dp[i][j] > result) result = dp[i][j];}}return result;}
};

 

總結

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

今天第一次做遞增子序列的題目,一開始先看了題解,後面就是一開始的題目轉換思路,以及最長重複子数組則是用畫圖的方式推出解法。

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

今天大概學了2hr,主要是理解子序列的做法該怎麼做。

相關資料

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

300.最长递增子序列

视频讲解:动态规划之子序列问题,元素不连续!| LeetCode:300.最长递增子序列_哔哩哔哩_bilibili

https://programmercarl.com/0300.最长上升子序列.html

674. 最长连续递增序列

视频讲解:动态规划之子序列问题,重点在于连续!| LeetCode:674.最长连续递增序列_哔哩哔哩_bilibili

https://programmercarl.com/0674.最长连续递增序列.html

718. 最长重复子数组

视频讲解:动态规划之子序列问题,想清楚DP数组的定义 | LeetCode:718.最长重复子数组_哔哩哔哩_bilibili

https://programmercarl.com/0718.最长重复子数组.html

这篇关于代碼隨想錄算法訓練營|第五十四天|300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组。刷题心得(c++)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Linux下如何使用C++获取硬件信息

《Linux下如何使用C++获取硬件信息》这篇文章主要为大家详细介绍了如何使用C++实现获取CPU,主板,磁盘,BIOS信息等硬件信息,文中的示例代码讲解详细,感兴趣的小伙伴可以了解下... 目录方法获取CPU信息:读取"/proc/cpuinfo"文件获取磁盘信息:读取"/proc/diskstats"文

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

如何高效移除C++关联容器中的元素

《如何高效移除C++关联容器中的元素》关联容器和顺序容器有着很大不同,关联容器中的元素是按照关键字来保存和访问的,而顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的,本文介绍了如何高效移除C+... 目录一、简介二、移除给定位置的元素三、移除与特定键值等价的元素四、移除满足特android定条件的元

Python获取C++中返回的char*字段的两种思路

《Python获取C++中返回的char*字段的两种思路》有时候需要获取C++函数中返回来的不定长的char*字符串,本文小编为大家找到了两种解决问题的思路,感兴趣的小伙伴可以跟随小编一起学习一下... 有时候需要获取C++函数中返回来的不定长的char*字符串,目前我找到两种解决问题的思路,具体实现如下: