C++ day53 最长公共子序列 不相交的线 最大子序和

题目1:1143  最长公共子序列

题目链接:最长公共子序列

对题目的理解

返回两个字符串的最长公共子序列的长度,如果不存在公共子序列,返回0,注意返回的是最长公共子序列,与前一天的最后一道题不同的是子序列是可以不连续的

动态规划

动规五部曲

1)dp数组及下标i的含义

dp[i][j]:[0,i-1]的nums1和以[0,j-1]的nums2的最长公共子序列的长度

2)递推公式

主要是两种情况,1)元素相同;2)元素不同

3)dp数组初始化

dp[i][0]和dp[0][j]  无意义,但是为了递推公式的需要,均初始化为0,其余下标位置处的数值初始化为任意值均可,但是为了方便起见,均初始化为0。

4)遍历顺序

根据递推公式,由左往右推导遍历,从上到下推导遍历。

5)打印dp数组

最终结果在dp[num1.size()][nums2.size()]

代码

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        //定义并初始化dp数组
        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-1][j],dp[i][j-1]);
            }
        }
        return dp[text1.size()][text2.size()];
    }
};
  • 时间复杂度: O(n * m),其中 n 和 m 分别为 text1 和 text2 的长度
  • 空间复杂度: O(n * m)

题目2:1035  不相交的线

题目链接:不相交的线
对题目的理解

连接数组nums1和nums2中的相同数字代表的点,每条直线不能相交,计算最大连线数

直线不能相交,这就是说明在字符串A中找到一个与字符串B相同的子序列,且这个子序列不能改变相对顺序,只要相对顺序不改变,连接相同数字的直线就不会相交。

本题就是套了一层连线的外壳,代码与上一道题一模一样,就是找两个数组中存在的最大相同子序列的长度。

分析过程与上一道题一模一样

代码

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        //定义并初始化dp数组
        vector<vector<int>> dp(nums1.size()+1,vector<int>(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()];
    }
};
  • 时间复杂度: O(n * m)
  • 空间复杂度: O(n * m)

题目3:53  最大子序和

题目链接:最大子序和

对题目的理解

找出具有最大和的连续子数组(至少包含一个元素),返回最大和,注意子数组是连续的

贪心算法

局部最优:当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小;全局最优:选取最大“连续和”

不断调整最大子序和区间的起始位置,只要连续和还是正数就会对后面的元素起到增大总和的作用。 所以只要连续和为正数就保留。

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int count=0;//记录连续和
        int result = INT_MIN;//记录最大连续和
        for(int i=0;i<nums.size();i++){
            count += nums[i];
            if(count>result) result = count;
            if(count<0) count = 0;//连续和为负数,重新计算连续和
        }
        return result;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

动态规划

动规五部曲

1)dp数组及下标i的含义

dp[i]:以nums[i]结尾(包括nums[i])的最大连续子序列的和

2)递推公式

dp[i]可以从两个方向推导出来

1)延续前面的和:dp[i]=dp[i-1]+nums[i]

2)从nums[i]重新计算:dp[i]=nums[i]

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

3)dp数组初始化

根据递推公式,dp[i]依赖于dp[i-1]   源头是dp[0],根据dp数组定义,dp[0]=nums[0]

非0下标的dp数组,可以初始化为任意值,因为可以在后续计算中被覆盖,但是为了初始化方便,统一初始为nums[0]

4)遍历顺序

根据递推公式,dp[i]依赖于dp[i-1],从前往后遍历

for(i=1;i<nums.size();i++)  注意i从1开始遍历

5)打印dp数组

根据dp数组定义,最终结果不一定是dp[nums[i]-1],应该找每一个i为终点的连续最大子序列,需要把所有结果遍历一遍,求得最大值

代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //定义并初始化dp数组
        vector<int> dp(nums.size(),nums[0]);
        int result = INT_MIN;
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            cout<<dp[i]<<endl;
            result = max(result,dp[i]);
        }
        return result;
    }
};

上述代码会出现如下的案例错误

错误的原因在于:result初始化为最小值,而for循环中计算的是dp[1],就是max(dp[0]+nums[1],nums[1]),是从数组中的第二个元素开始考虑的,如果这样的话,对于只有一个元素的数组根本就没有经过for循环,直接输出了result,所有result不能这样初始化,应该初始化为nums[0],即初始化为数组的第1个元素值,这样才能在数组只有1个元素的情况下,result考虑到第一个元素。

代码改正如下:

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //定义并初始化dp数组
        vector<int> dp(nums.size(),nums[0]);
        int result = nums[0];
        for(int i=1;i<nums.size();i++){
            dp[i]=max(dp[i-1]+nums[i],nums[i]);
            cout<<dp[i]<<endl;
            result = max(result,dp[i]);
        }
        return result;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/219431.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

uniapp 在线预览PDF

1、官网地址&#xff1a; https://mozilla.github.io/pdf.js/getting_started/ 2、解压文件到static中 3、定义查看组件FilePreview <template><view><web-view :src"allUrl"></web-view></view> </template><script> e…

(04730)电路分析基础之电阻、电容及电感元件

04730电子技术基础 语雀&#xff08;完全笔记&#xff09; 电阻元件、电感元件和电容元件的概念、伏安关系&#xff0c;以及功率分析是我们以后分析电 路的基础知识。 电阻元件 电阻及其与温度的关系 电阻 电阻元件是对电流呈现阻碍作用的耗能元件&#xff0c;例如灯泡、…

mongoose学习记录

mongoose安装和连接数据库 npm i mongoose导入mongoose const mongoose require(mongoose) mongoose.set("strictQuery",true)连接数据库 mongoose.connect(mongodb:127.0.0.1:27017/test)设置回调 mongoose.connection.on(open,()>{console.log("连接成…

弱口令防护和网站防盗链有什么用

弱口令防护主要针对用户账户的安全。弱口令是指容易被猜测或破解的密码&#xff0c;如常见的密码、简单的数字序列或字典中的单词等。弱口令防护的目的是防止恶意用户或攻击者通过猜测或暴力破解密码的方式获取合法用户的账户权限。通过实施强密码策略、密码复杂度要求和账户锁…

centos 7.9 二进制部署 kubernetes 1.27.7

文章目录 1. 预备条件2. 基础配置2.1 配置root远程登录2.2 配置主机名2.3 安装 ansible2.4 配置互信2.5 配置hosts文件2.6 关闭防firewalld火墙2.7 关闭 selinux2.8 关闭交换分区swap2.9 修改内核参数2.10 安装iptables2.11 开启ipvs2.12 配置limits参数2.13 配置 yum2.14 配置…

【JavaEE进阶】 Spring核⼼与设计思想

文章目录 &#x1f332;Spring 是什么&#xff1f;&#x1f384;什么是IoC呢&#xff1f;&#x1f388;传统程序开发&#x1f388;传统程序开发的缺陷&#x1f388;如何解决传统程序的缺陷&#xff1f;&#x1f388;控制反转式程序开发&#x1f388;对⽐总结规律 &#x1f340;…

十二、FreeRTOS之FreeRTOS任务相关API函数

本节需要掌握以下内容&#xff1a; 1&#xff0c;FreeRTOS任务相关API函数介绍&#xff08;熟悉&#xff09; 2&#xff0c;任务状态查询API函数实验&#xff08;掌握&#xff09; 3&#xff0c;任务时间统计API函数实验&#xff08;掌握&#xff09; 4&#xff0c;课堂总结…

【鸿蒙应用开发】开发环境搭建及IDE安装使用

1.下载安装包 安装包下载地址&#xff1a; 点击跳转下载页面 可以根据自己的操作系统选择对应版本下载。 本文以Windows安装为例&#xff0c;Mac安装方式相同 2. 安装 下载好后&#xff0c;打开安装包&#xff0c;进入安装界面&#xff1a; 点击Next&#xff0c;进入安…

vue创建项目,使用可视化界面安装插件

安装项目&#xff1a; vue create vue-app 选择默认配置就行&#xff0c;也可以按需选择自定义配置 vue ui通过可视化管理项目 通过可视化安装全家桶插件

Spring Cloud 配置 Druid(二)

不废话&#xff0c;直接上代码&#xff0c; Nacos搭建的微服务&#xff0c;可以看Spring Cloud 配置 Nacos&#xff08;一&#xff09;-CSDN博客 一&#xff0c;pom文件 spring-cloud-starter-alibaba-nacos-discovery 和 spring-cloud-starter-openfeign 都是基于spring-cl…

95所双一流高校参与,“搜索界奥林匹克”决出28个获奖团队

只需要回答几个问题&#xff0c;就能生成个性化的简历&#xff0c;还提供优化建议&#xff0c;安排AI模拟面试。这样的效率神器&#xff0c;就出现第二届百度搜索创新大赛的赛场上。 &#x1f680; 来自南京航空航天大学的“肝到凌晨”团队&#xff0c;利用文心一言插件平台“…

【新手解答8】深入探索 C 语言:递归与循环的应用

C语言的相关问题解答 写在最前面问题&#xff1a;探索递归与循环在C语言中的应用解析现有代码分析整合循环示例代码修改注意事项结论 延伸&#xff1a;递归和循环的退出条件设置解析使用递归使用循环选择适合的方法 写在最前面 一位粉丝私信交流&#xff0c;回想起了当初的我C…

ORACLE使用Mybatis-plus批量插入

ORACLE使用mybatis-plus自带的iservice.saveBatch方法时&#xff0c;会报DML Returing cannot be batch错误&#xff1a; 推测原因是oracle不支持insert into table_name (,) values &#xff08;&#xff0c;&#xff09;,&#xff08;&#xff09;的写法。且oracle不会自动生…

【C语言】超详解,让你C语言成功入门(五)——操作符

目录 1.算术操作符2.移位操作符2.1左移操作符<<2.2右移操作符>> 3.位操作符4.赋值操作符5.单目操作符5.1单目操作符介绍5.2sizeof 和 数组 6.关系操作符7.逻辑操作符8.条件操作符&#xff08;三目操作符&#xff09;9.逗号表达式10.下标引用、函数调用和结构体11.表…

基于DotNetty实现一个接口自动发布工具 - 通信实现

基于 DotNetty 实现通信 DotNetty : 是微软的 Azure 团队&#xff0c;使用 C#实现的 Netty 的版本发布。是.NET 平台的优秀网络库。 项目介绍 OpenDeploy.Communication 类库项目,是通信相关基础设施层 Codec 模块实现编码解码 Convention 模块定义约定,比如抽象的业务 Handle…

华为手环 8 五款免费表盘已上线,请注意查收

华为手环 8&#xff0c;作为一款集时尚与实用于一体的智能手环&#xff0c;不仅具备强大的功能&#xff0c;还经常更新的表盘样式&#xff0c;让用户掌控时间与健康的同时&#xff0c;也能展现自己的时尚品味。这不&#xff0c;12 月官方免费表盘又上新了&#xff0c;推出了五款…

批量AI创作文案的工具,批量AI创作文章的软件

人工智能&#xff08;AI&#xff09;的应用不断拓展&#xff0c;其中批量AI创作逐渐成为许多文本创作者和企业编辑的热门选择。面对海量的文章需求&#xff0c;批量AI创作工具能够高效、快速地生成大量文本内容&#xff0c;从而减轻创作者的工作负担。本文将专心分享批量AI创作…

Linux last命令教程:如何查看用户的登录和注销历史(附案例详解和注意事项)

Linux last命令介绍 last命令在Linux中用于显示自文件/var/log/wtmp创建以来所有用户的登录和注销列表。可以给出一个或多个用户名作为参数&#xff0c;以显示他们的登录&#xff08;和注销&#xff09;时间和主机名。 Linux last命令适用的Linux版本 last命令在大多数Linux…

高温老化房稳定性、应用领域

高温老化房控制系统的稳定性主要有四点: 1. 温度控制:控制系统确保老化室内的温度在整个老化试验过程中保持稳定并在期望的范围内。这种稳定性对于准确可靠的测试结果至关重要。 2. 湿度控制:控制系统同时保持老化室内湿度水平稳定。这一点很重要&#xff0c;因为某些材料或产…

UE5 - 把ArchvizExplorer项目改造成自己的数字孪生项目 - 开发记要

参考&#xff1a; https://blog.csdn.net/qq_17523181/article/details/133853099 https://blog.csdn.net/qq_17523181/article/details/134455597 1. 安装项目 https://www.unrealengine.com/marketplace/zh-CN/product/archviz-explorer https://karldetroit.com/archviz-exp…