当前位置: 首页 > news >正文

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)

相关文章:

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

题目1&#xff1a;1143 最长公共子序列 题目链接&#xff1a;最长公共子序列 对题目的理解 返回两个字符串的最长公共子序列的长度&#xff0c;如果不存在公共子序列&#xff0c;返回0&#xff0c;注意返回的是最长公共子序列&#xff0c;与前一天的最后一道题不同的是子序…...

ubuntu中删除镜像和容器、ubuntu20.04配置静态ip

1 删除镜像 # 短id sudo docker rmi 镜像id # 完整id sudo docker rmi 镜像id# 镜像名【REPOSITORY:TAG】 sudo docker rmi redis:latest2 删除容器 # 删除某个具体容器 sudo docker rm 容器id# 删除Exited状态/未运行的容器&#xff0c;三种命令均可 sudo docker rm docker …...

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

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

JOSEF约瑟 同步检查继电器DT-13/200 100V柜内安装,板前接线

系列型号 DT-13/200同步检查继电器; DT-13/160同步检查继电器; DT-13/130同步检查继电器; DT-13/120同步检查继电器; DT-13/90同步检查继电器; DT-13/254同步检查继电器; 同步检查继电器DT-13/200 100V柜内板前接线 一、用途 DT-13型同步检查继电器用于两端供电线路的…...

龙迅#LT8311X3 USB中继器应用描述!

1. 概述 LT8311X3是一款USB 2.0高速信号中继器&#xff0c;用于补偿ISI引起的高速信号衰减。通过外部下拉电阻器选择的编程补偿增益有助于提高 USB 2.0 高速信号质量并通过 CTS 测试。 2. 特点 • 兼容 USB 2.0、OTG 2.0 和 BC 1.2• 支持 HS、FS、LS 信令 • 自动检测和补偿 U…...

eclipse jee中 如何建立动态网页及服务的设置问题

第一次打开eclipse 时&#xff0c;设置工作区时&#xff0c;一定是空目录 进入后 File-----NEW------Dynamic Web Project 填 项目名&#xff0c;不要有大写 m1 next next Generate前面打对勾 finish 第一大步&#xff1a; window----Preferences type filter text 处填 :Serve…...

一张网页截图,AI帮你写前端代码,前端窃喜,终于不用干体力活了

简介 众所周知&#xff0c;作为一个前端开发来说&#xff0c;尤其是比较偏营销和页面频繁改版的项目&#xff0c;大部分的时间都在”套模板“&#xff0c;根本没有精力学习前端技术&#xff0c;那么这个项目可谓是让前端的小伙伴们看到了一丝丝的曙光。将屏幕截图转换为代码&a…...

处理k8s中创建ingress失败

创建ingress&#xff1a; 如果在创建过程中出错了&#xff1a; 处理方法就是&#xff1a; kubectl get ValidatingWebhookConfiguration kubectl delete -A ValidatingWebhookConfiguration ingress-nginx-admission 然后再次创建&#xff0c;发现可以&#xff1a;...

Redis高可用集群架构

高可用集群架构 哨兵模式缺点 主从切换阶段&#xff0c; redis服务不可用&#xff0c;高可用不太友好只有单个主节点对外服务&#xff0c;不能支持高并发单节点如果设置内存过大&#xff0c;导致持久化文件很大&#xff0c;影响数据恢复&#xff0c;主从同步性能 高可用集群…...

JAVA常见问题解答:解决Java 11新特性兼容性问题的六个步骤

引言&#xff1a; 随着技术的不断发展&#xff0c;Java作为一种被广泛使用的编程语言&#xff0c;也在不断更新和改进。Java 11作为Java的最新版本&#xff0c;带来了许多新的特性和改进。然而&#xff0c;对于一些老旧的Java应用程序来说&#xff0c;升级到Java 11可能会带来一…...

【C语言】深入理解指针(1)

目录 前言 &#xff08;一&#xff09;内存与地址 从实际生活出发 地址 内存 内存与地址关系密切 &#xff08;二&#xff09;指针变量 指针变量与取地址操作符 指针变量与解引用操作符 指针的大小 指针的运算 指针 - 整数 指针-指针 指针的关系运算 指针的类型的…...

MySQL的系统信息函数

系统信息函数让你更好的使用MySQL数据库 1、version()函数 查看MySQL系统版本信息号 select version();2、connection_id()函数 查看当前登入用户的连接次数 直接调用CONNECTION_ID()函数--不需任何参数--就可以看到当下连接MySQL服务器的连接次数&#xff0c;不同时间段该…...

python中.format() 方法

.format() 方法是一种用于格式化字符串的方法&#xff0c;它允许将变量的值插入到字符串中的占位符位置上。该方法可以接受一个或多个参数&#xff0c;并根据给定的格式规则将它们插入到字符串中。 下面是一些使用 .format() 方法的示例&#xff1a; # 基本用法 name "…...

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

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

服务器中深度学习环境的配置

安装流程 11.17 日&#xff0c;周末去高校参加学术会议&#xff0c;起因&#xff0c; 由于使用了某高校内的公共有线网络&#xff0c; 远程连接服务器后&#xff0c;黑客利用 ssh 开放的 22 端口&#xff0c; 篡改了主机的配置&#xff0c; 使得只要一连上网络&#xff0c; 服…...

html实现各种好看的鼠标滑过图片特效模板

文章目录 1.鼠标悬浮效果1.1 渐动效果1.2 渐变效果1.3 边框效果1.4 线行效果1.5 图标效果1.6 块状效果1.7 边线效果1.8 放大效果1.9 渐出效果1.10 痕迹效果1.11 交叉效果1.12 着重效果1.13 详展效果1.14 能动效果1.15 明细效果 2.主要源码2.1 源代码 源码下载 作者&#xff1a;…...

leetcode:LCR 122. 路径加密python3解法)

难度&#xff1a;简单 假定一段路径记作字符串 path&#xff0c;其中以 "." 作为分隔符。现需将路径加密&#xff0c;加密方法为将 path 中的分隔符替换为空格 " "&#xff0c;请返回加密后的字符串。 示例 1&#xff1a; 输入&#xff1a;path "a.a…...

vue中实现纯数字键盘

一、完整 代码展示 <template><div class"login"><div class"login-content"><img class"img" src"../../assets/image/loginPhone.png" /><el-card class"box-card"><div slot"hea…...

C#简化工作之实现网页爬虫获取数据

1、需求 想要获取网站上所有的气象信息&#xff0c;网站如下所示&#xff1a; 目前总共有67页&#xff0c;随便点开一个如下所示&#xff1a; 需要获取所有天气数据&#xff0c;如果靠一个个点开再一个个复制粘贴那么也不知道什么时候才能完成&#xff0c;这个时候就可以使用C…...

回顾过去的五年

回顾过去的五年 不知不觉&#xff0c;一晃就5年了。孩子也慢慢的长大了&#xff0c;都快和我一样高了。 2017-2019年依旧服务于原公司。后来公司停业了&#xff0c;得到了相应的赔偿。在家里呆了几个月&#xff0c;变成了无业游民。陪伴家人&#xff0c;也会收到家人的鞭策。…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

《基于Apache Flink的流处理》笔记

思维导图 1-3 章 4-7章 8-11 章 参考资料 源码&#xff1a; https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...