设计网站推荐 猪,抖音代运营赚钱吗,中小企业为什么要建网站,网站站点创建成功是什么意思#x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;练题 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录 最长递增子序列最长连续递增… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接练题 长路漫漫浩浩万事皆有期待 文章目录 最长递增子序列最长连续递增序列最长重复子数组总结 本期是求子序列的新的一期题目前两道有一些相似之处思路差不多第三道有一点难度但并不意味着第一道没有难度没有做过该类型题的选手并不容易解出题解。 最长递增子序列
300. 最长递增子序列 - 力扣LeetCode
题目大意是给一个数组要求返回最长的递增的序列题目要求是删除中间一些元素或者不删除也可以返回最长的递增的数组长度又是一道这种题目如果你是之前做过类似题目大意的朋友应该知道通常来说要求可以删除中间元素的通常我们都不是真的删除数据而是通过遍历来间接的实现删除中间的数据的过程换句话来说不是真正删除数据而是要删除的数据我们不处理它。
dp数组的含义dp【i】代表到该位置为止i之前包括i的最长的递增子序列是多大。但是需要注意的是整体的最长的递增子序列可不一定是dp数组的最后一个数据因为很可能我们要找的最长递增序列结尾在前面就已经出现了而遍历到数组最后一个位置可能只是不同的递增子序列路线不一定是长的。
递推公式由于递增子序列很有可能不是连续的需要删除部分数据那么我们如何实现这一部分的代码呢答案是用两个循环一个是外层循环控制遍历到数组中的哪一个位置了另一个内层循环是重复遍历从起始位置到i这个位置如果出现前面的0-i的数据比当前遍历到的数小那么递增子序列长度1这也就是相当于不符合条件的数据我们直接略过去符合条件的再使长度1间接的删除了多余数据
也就是 ifnums【j】 nums【i】dp【i】maxdp【i】dp【j】1 取最大值看看它原本的大还是遍历完的最长递增子序列长度大。每次j都会从头开始遍历一次看看这回多出来的那个数据是否能使子序列长度增加。
dp数组初始化dp数组的初始化都是初始化为1这是因为如果只有一个数据的话那么最长递增子序列肯定是1不可能返回0而其他的为什么也初始化为1呢因为如果出现大于1的递增子序列长度那么就一定会被递推公式所覆盖所以我们都初始化为1。
遍历顺序都是从前向后遍历不用多说。
class Solution {
public:int lengthOfLIS(vectorint nums) {vectorintdp(nums.size(),1);int result1;for(int i1;inums.size();i){for(int j0;ji;j){if(nums[i]nums[j])dp[i]max(dp[i],dp[j]1);}if(resultdp[i])resultdp[i];}return result;}
};代码中的result的用处就是记录最长的递增子序列有多长然后最后返回它。
最长连续递增序列
674. 最长连续递增序列 - 力扣LeetCode
这道题和上一道题很像只不过这道题我们要求的是连续的递增子序列了连续的递增子序列我个人认为要比非连续的要好写或者说好想一点。
dp数组含义dp数组的含义和上一道题一样也是到该位置为止i之前包括i的最长的连续递增子序列是多长但是我觉得这种含义太抽象了不利于初学者理解我认为可以将这句话翻译为以i结尾的这条递增序列有多长这其实也就间接的证明了我们之前所说的含义即最后一个下标的dp数组所代表的数据并不一定是最大的。因为它代表的应该是以i为结尾的这条递增序列最长有多长。
递推公式由于是连续的最长递增序列所以我们只看是否是连续递增就可以了那么连续就体现在上一个数字和这一个数字的比较
ifnums【i】nums【i-1】dp【i】dp【i-1】1dp数组初始化和遍历顺序都和上一道题一样不做赘述。
class Solution {
public:int findLengthOfLCIS(vectorint nums) {vectorintdp(nums.size(),1);int result1;for(int i1;inums.size();i){if(nums[i]nums[i-1])dp[i]dp[i-1]1;resultmax(result,dp[i]);}return result;}
};最长重复子数组
718. 最长重复子数组 - 力扣LeetCode
这道题是略有难度的一道题为什么说它略有难度呢并不是递推公式有多难理解而是dp数组的的表示要清楚的想到有一些难度。
dp数组的含义这是给我们两个数组然后让我们求重复的连续部分最长有多长这是我们就需要使用二维数组来表示了其中一维表示一个数组另一维表示另一数组而dp【i】【j】表示的是第一个数组的i-1位置下标对应的第二个数组的j-1下标位置最长的重复子数组有多长那么为什么我们要表示i-1和j-1呢直接表示i和j不好吗这样定义是为了方便dp数组的初始化在下面还有对此处的详解。
递推公式从哪个方向上能够推出dp【i】【j】呢当数组1的i-1下标位置的数字和数组2下标为j-1的位置数字相等的时候不就是说明两数组有一数字重复吗此时就是长度1那么递推公式就理所当然的是 ifnums1【i-1】nums2【j-1】dp【i】【j】dp【i-1】【j-1】1 就是上一个长度再加上这回匹配成功的长度1。
dp数组的初始化看到这里相信大家可能已经带有一些疑问了这样定义dp数组那么当遍历到i和j等于0的时候不就出问题了吗这也正是初始化所要解决的问题正是因为我们这样定义dp数组导致了当i和j其中一个为0时候是非法的所以我们初始化第一行和第一列时候全部初始化为0其余部分因为有递推公式的存在每个位置是依靠前一个位置的值所以i和j非0部分初始化为什么都可以。那么为什么我们要这样定义数组呢因为如果dp【i】【j】就是表示它处在i和j的位置上时候有多长这会导致初始化i和j其一等于0时也就是二维数组的第一行和第一列可能不全为0这会增大初始化的代码强度可能第一个数组i0的时候第二个数组的j对应某位置两数组有数据相等也就是第一行某处有位置应该初始化为1讲到这里大家反复揣摩一下用笔画一下可能就明白了。
遍历顺序遍历顺序还是从前向后两个for循环分别遍历第一个数组和第二个数组从前向后查看是否有相等的元素出现。
class Solution {
public:int findLength(vectorint nums1, vectorint nums2) {vectorvectorintdp(nums1.size()1,vectorint(nums2.size()1,0));int result0;for(int i1;inums1.size();i){for(int j1;jnums2.size();j){if(nums1[i-1]nums2[j-1])dp[i][j]dp[i-1][j-1]1;resultmax(result,dp[i][j]);}}return result;}
};以上就是本章的全部内容子序列问题起初做都没有什么思路要勤加练习思维才能够想出用动态规划解决问题的思路。
总结
今天我们完成了最长递增子序列、最长连续递增序列、最长重复子数组三道题相关的思想需要多复习回顾。接下来我们继续进行算法练习。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
