C国演义 [第七章]

这篇具有很好参考价值的文章主要介绍了C国演义 [第七章]。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最长重复子数组

力扣链接

给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。

示例 1:
输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出:3
解释:长度最长的公共子数组是 [3,2,1] 。
示例 2:
输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
输出:5

  • 提示:
    1 <= nums1.length, nums2.length <= 1000
    0 <= nums1[i], nums2[i] <= 100

题目理解

暴力解法就是 用两个for循环遍历两个数组, 然后在套用一个while循环或者for循环从各个起始位置开始判断
这样就相当于套用了三个for循环, 数据大了就会超时

其实本题采用的方法是动态规划, 用个二维dp数组来记录比较情况

步骤

dp含义

重复子数组, 里面有个暗含意思 连续
dp[i][j] — — 以下标 i - 1为结尾的nums1, 以下标 j - 1 结尾的nums2 之间的最长重复子数组的长度

🗨️为啥是以 下标 i - 1结尾 而不是以下标 i 结尾呢??

  • 其实这也是为了方便初始化 和 后续的判断
    后面在 为啥dp数组如此奇怪 中有讲

递推公式

重复子数组, 里面有个暗含意思 连续
那么, 我们处理的方法 就和前面的 连续递增子序列 相同

if(nums1[i - 1] == nums2[j - 1])
	dp[i][j] = dp[i - 1][j - 1] + 1;

🗨️为啥比较的是 nums1[i - 1] 和 nums[j - 1], 而不是 nums1[i] 和 nums[j]呢

  • dp数组的含义是 以下标 i - 1为结尾的nums1, 以下标 j - 1 结尾的nums 之间的最长重复子数组的长度
    因为题目有 连续 的意思, 所以 dp[i][j] 的来源只有一个, 那就是 dp[i - 1][j - 1]
    条件就是判断 当前两数组的值是否相等 — — nums1[i - 1] == nums2[ j - 1]
    如果判断相等, 那么 dp[i][j] 就会在dp[i - 1][j - 1]的基础上 + 1 (两者都回退一步, 同时看看后面的值是否相等)

初始化

C国演义 [第七章]
第一行 和 第一列要初始化一下.
那么我们需要初始化的是 dp[0][j] 和 dp[i][0]
但是, 我们定义的dp数组的含义 — — 以下标 i - 1为结尾的nums1, 以下标 j - 1 结尾的nums2 之间的最长重复子数组的长度
那么, 就是要初始化一下 -1行 和 -1列, 可想而知: 要初始化为 0
其它的要怎么初始化呢? — — 由前面到后面进行推导, 由上面到下面进行推导 — — 反正都是由前面的推导而来, 那么我们就初始化为 0

那么我们就全部都初始化为 0

 vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
为啥dp数组如此奇怪

如果我们的dp数组的含义是 — — 以下标 i为结尾的nums1, 以下标 j为结尾的nums2之间的最长重复子数组的长度
那么, 初始化就要初始化 第1行 和 第 1列
如果nums1[i] 与 nums2[0] 相同的话,对应的 dp[i][0]就要初始为1, 因为此时最长重复子数组为1。 nums2[j] 与 nums1[0]相同的话,同理。

// 要对第一行,第一列经行初始化
for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1;
for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;

遍历顺序

C国演义 [第七章]
是从左上方开始递推的 — — 从前到后, 从上至下开始遍历

代码

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

        }
        
        return result;

    }
};

在这里, 我们也给出 dp数组的含义是 — — 下标以 i - 1为结尾的nums1, 下标以 j - 1为结尾的nums2之间的最长重复子序列的长度👇👇👇

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) 
    {
        vector<vector<int>> dp(nums1.size(), vector<int>(nums2.size(), 0));
        
        // 要对第一行,第一列经行初始化
        for (int i = 0; i < nums1.size(); i++) if (nums1[i] == nums2[0]) dp[i][0] = 1;
        for (int j = 0; j < nums2.size(); j++) if (nums1[0] == nums2[j]) dp[0][j] = 1;
        
        int result = 0;
        for(int i = 0; i < nums1.size(); i++)
        {
            for(int j = 0; j < nums2.size(); j++)
            {
                if(i > 0 && j > 0 && nums1[i] == nums2[j]) // 为了预防i - 1 和 j - 1是负数
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                
                result = max(result, dp[i][j]);
            }

        }
        
        return result;

    }
};

C国演义 [第七章]

最长公共子序列

力扣链接

给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 .

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串.

例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列.
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列.

示例 1:
输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace” ,它的长度为 3 。
示例 2:
输入:text1 = “abc”, text2 = “abc”
输出:3
解释:最长公共子序列是 “abc” ,它的长度为 3 。
示例 3:
输入:text1 = “abc”, text2 = “def”
输出:0
解释:两个字符串没有公共子序列,返回 0 。

  • 提示:
    1 <= text1.length, text2.length <= 1000
    text1 和 text2 仅由小写英文字符组成

题目理解

这个题目是 不讲究连续 && 公共子序列
由此可以联想到 最长递增子序列
区别就是 : 一个是一个集合, 另一个是两个集合 — — 一个是一维dp数组, 另一个是二维dp数组

步骤

dp含义

dp[i][j] — — 区间为[0, i - 1]的nums1 和 区间为[0, j - 1]的nums2之间的最长公共子序列的长度
这里为啥是区间 i - 1 和 j - 1, 这个在上面已经说过了.

递推公式

无非就两种情况: nums1[i - 1] 和 nums2[j - 1] 是否相等

  • 如果nums1[i - 1] == nums2[j - 1] — — 那么就使用dp[i - 1][j - 1]的情况 — — dp[i - 1][j - 1] + 1
  • 如果nums1[i - 1] != nums2[j - 1] — — 那么就比较 区间为[0, i - 1]的nums1 和 区间为[0, j - 2]的nums2之间的最长公共子序列的长度(dp[i][j - 1]) 和 区间为[0, i - 2]的nums1 和 区间为[0, j - 1]的nums2之间的最长公共子序列的长度(dp[i - 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][j - 1], dp[i -1][j]);

初始化

C国演义 [第七章]
通过递推公式可知, 我们要初始化第一行 和 第一列
即我们需要初始化的是 dp[0][j] 和 dp[i][0]
但是, 我们dp数组的含义是 — — 区间为[0, i - 1]的nums1 和 区间为[0, j - 1]的nums2之间的最长公共子序列的长度
那么, dp[0][j] 的含义就是 -1 行 — — 那就初始化为 0 , dp[i][0]亦是如此
那么, 其他的dp数组呢? — — 由前面递推过来的, 所以就初始化为 0也是可以的

所以, 我们就把 dp数组都初始化为 0

遍历顺序

C国演义 [第七章]
通过递推公式可知, 是 从前到后, 从上至下的顺序 --- --- 从小到大的遍历顺序

代码

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(); i++)
        {
            for(int j = 1; j <= text2.size(); j++)
            {
                if(text1[i - 1] == text2[j - 1])
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                else
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }

        }
        
        return dp[text1.size()][text2.size()];
    }
};

C国演义 [第七章]

总结

通过前面几章的动态规划刷题篇的训练, 我们不难发现

  • dp数组的含义是非常重要的, 这也决定了后面的递推公式的得出
  • 递推公式涉及 i - 1 或者是 j - 1的, 建议从 1开始遍历好一些, 这样也避免了一些情况的讨论

贵有恒,何必三更起五更眠;最无益,只怕一日曝十日寒 — — 毛泽东文章来源地址https://www.toymoban.com/news/detail-498521.html

到了这里,关于C国演义 [第七章]的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构第七章

    图(Graph)G由两个集合V和E组成,记为G=(V, E),其中V是顶点的有穷非空集合,E是V中顶点偶对的有穷集合,这些顶点偶对称为边。V(G)和E(G)通常分别表示图G的顶点集合和边集合,E(G)可以为空集。若EG)为空,则图G只有顶点而没有边。 子图:假设有两个图G=(V,E)和G1=(V1,E1);如果V1

    2024年02月03日
    浏览(63)
  • 第七章 测试

    7.1.1 选择程序设计语言 1. 计算机程序设计语言基本上可以分为汇编语言和高级语言 2. 从应用特点看,高级语言可分为基础语言、结构化语言、专用语言 01 有理想的模块化机制; 02 可读性好的控制结构和数据结构; 03 便于调试和提高软件可靠性; 04 编译程序发现程序错误的

    2024年02月08日
    浏览(77)
  • [JavaScript] 第七章 对象

    🌹作者主页:青花锁 🌹简介:Java领域优质创作者🏆、Java微服务架构公号作者😄 🌹简历模板、学习资料、面试题库、技术互助 🌹文末获取联系方式 📝 [Java项目实战] 介绍Java组件安装、使用;手写框架等 [Aws服务器实战] Aws Linux服务器上操作nginx、git、JDK、Vue等 [Java微服务

    2024年02月02日
    浏览(129)
  • 第七章 面向对象编程(基础)

    (1)类是抽象的,概念的,代表一类事物,比如人类、猫类... 即它是数据类型。 (2)对象是具体的,实际的,代表一个具体事物,即实例。 (3)类是对象的模板,对象是类的一个个体,对应一个实例。 属性是类的一个组成部分,一般是基本数据类型,也可是引用类型(对

    2024年02月06日
    浏览(84)
  • OpenCV:第七章、图像变换

    目录 第七章:图像变换 7.1、基于OpenCV的边缘检测 7.1.1、一般步骤 1、滤波 2、增强 3、检测 7.1.2、canny算子 1、canny算子简介 2、canny边缘检测的步骤 7.2、霍夫变换  7.2.2、OpenCV中的霍夫线变换 7.2.3、霍夫线变换原理        7.2.4、标准霍夫变换:HoughLines()函数    7.2.5、累计概率

    2024年02月03日
    浏览(68)
  • Flink第七章:状态编程

    Flink第一章:环境搭建 Flink第二章:基本操作. Flink第三章:基本操作(二) Flink第四章:水位线和窗口 Flink第五章:处理函数 Flink第六章:多流操作 Flink第七章:状态编程 这次我们来学习Flink中的状态学习部分,创建以下scala文件 这个文件里有几个常用的状态创建 按键分区中值状态编程案

    2024年02月06日
    浏览(65)
  • 第七章 正则表达式

    目录 1.1. 概念: 1.2. 基本正则表达式 1.2.1. 常见元字符 1.2.2. POSIX字符类 1.2.3. 示例 1.3. 扩展正则表达式 1.3.1. 概念 1.3.2. 示例 在进行程序设计的过程中,用户会不可避免地遇到处理某些文本的情况。有的时候,用户还需要查找符合某些比较复杂规则的字符串。对于这些情况,如

    2024年03月17日
    浏览(85)
  • 第七章 高级 OOP 特性

    7.3.3 继承与延迟静态绑定 在创建类层次结构时,有时候回遇到这种情况,即父类方法要使用静态类属性,但静态类属性可能在子类中被覆盖。这和 self 的使用有关。我们看一个例子,其中 Employee 类和 Executive 类都做了一些修改: 执行代码如下: Watching Football  因为

    2024年02月11日
    浏览(51)
  • Oracle 查询优化改写(第七章)

    2024年02月11日
    浏览(44)
  • SpringBoot_第七章(读写分离)

    目录 1:MybatisPlus(读写分离) 1.1:首先创建三个数据库1主2从 1.2:代码实例 1.3:优缺点分析 2:SpringBoot路由数据源(读写分离) 2.1:实现原理 2.2:代码实现 2.3:测试代码  2.4:优缺点分析 这里列举了两种读写分离实现方案,如下 表名是user表 1:导入pom 2:配置spring的主从

    2024年02月06日
    浏览(39)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包