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

Day 53 |● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和

1143.最长公共子序列 

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));int res = 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;res = max(res,dp[i][j]);}else{dp[i][j] = max(dp[i-1][j], dp[i][j-1]);res = max(res,dp[i][j]);} }}return res;}
};

具体思路:

dp[i][j]:对text1的前 i 个长度和对text2的前 j 个长度所能得到的最大公共子序列长度。

因为描述的是长0度不是下标,所以在初始化的时候,dp初始化时候的大小,得加1。

而在推导中 dp[i][j] 的推导过程只会存在如下俩种情况,要么相等了,要么不相等。

相等:因为 ij代表的是长度,则很自然的,如果想表达前 2 个元素,比对的当前第2个元素下标是1,所以当相等,也就是 text1[i-1] == text2[j-1]的时候,那么此时当前dp[i][[j] 位置因为其相同,则一定能够在原先 dp[i-1][j-1]的基础上+1.

不相等:不相等则说明,不能加1,则说明俩个组合不能同时前进后退,而此时的值只能从俩者单独退一步所能获得的最大值来覆盖。

1035.不相交的线

跟上题一模一样

53. 最大子序和

      

class Solution {
public:int maxSubArray(vector<int>& nums) {if(nums.size() == 1) return nums[0];vector<int> dp(nums.size());dp[0] = nums[0];//注意初始化int res = dp[0];//注意初始化for(int i = 1; i < nums.size(); i++){dp[i] = max(dp[i-1] + nums[i], nums[i]);res = max(res, dp[i]);}return res;}
};

具体思路:

dp[i] : (0-i区间所能获得的最大连续子数组值)

dp[i]推导可以通过要么上一个dp[i-1]的值加上当前的值为大,要么直接以当前值为最大,因为若之前的值是负数,则肯定会导致相加变小,那么前面全部抛弃,直接从当前开始。

初始化也很重要,首先是dp[0],从0下标开始,则其值肯定就是nums[0]的值,而res初始化也得是0下标的值,以防万一一直就是负数,如果初始是0的话,0一直大于负数,但是其真正的最大值也就是负数,会导致出问题。

相关文章:

Day 53 |● 1143.最长公共子序列 ● 1035.不相交的线 ● 53. 最大子序和

1143.最长公共子序列 class Solution { public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size()1,vector<int>(text2.size()1,0));int res 0;for(int i 1; i < text1.size(); i){for(int j 1; j <…...

ant-desgin charts双轴图DualAxes,柱状图无法立即显示,并且只有在调整页面大小(放大或缩小)后才开始显示

摘要 双轴图表中&#xff0c;柱状图无法立即显示&#xff0c;并且只有在调整页面大小&#xff08;放大或缩小&#xff09;后才开始显示 官方示例代码 在直接复制&#xff0c;替换为个人数据时&#xff0c;出现柱状图无法显示问题 const config {data: [data, data],xFiel…...

获取别人店铺的所有商品API接口

使用淘宝淘口令接口的步骤通常包括&#xff1a; 注册成为淘宝开放平台的开发者&#xff1a;在淘宝开放平台网站上注册账号并完成认证。 创建应用以获取API密钥&#xff1a;在您的开发者控制台中创建一个应用&#xff0c;并获取用于API调用的密钥&#xff0c;如Client ID和Clie…...

成都正信:亲戚借了钱一直不还怎么委婉的说

在中国传统文化中&#xff0c;亲情关系往往被视为最为重要和敏感的部分。当亲戚间发生借贷时&#xff0c;若出现拖欠不还的情形&#xff0c;处理起来尤为棘手。面对这样的尴尬局面&#xff0c;采取委婉而有效的沟通方式至关重要。 张华最近就遇到了这样的困扰。他的表弟去年因急…...

Truenas入门级教程

Truenas入门教程 前言&#xff1a;系统相关配置 采用I3 4160&#xff0c;采用了2块500G的硬盘&#xff0c;内存为8G&#xff0c;两个网卡只用了其中一个&#xff0c;系统安装的是core版本 硬件采用DELL3020MT机箱&#xff0c;自带3个SATA网口&#xff0c;后期网口不够&#…...

窗口函数dense() over(条件)

力扣题目连接 https://leetcode.cn/problems/rank-scores/ 在 SQL 中&#xff0c;DENSE_RANK() 是一个窗口函数&#xff0c;用于计算结果集中每行的稠密排名&#xff08;dense rank&#xff09;。DENSE_RANK() 函数会为具有相同排序字段值的行分配相同的排名&#xff0c;但不会…...

蓝牙APP开发实现汽车遥控钥匙解锁汽车智能时代

在现代社会&#xff0c;随着科技的不断发展&#xff0c;汽车已经不再是简单的交通工具&#xff0c;而是与智能科技紧密相连的载体。其中&#xff0c;通过开发APP蓝牙程序实现汽车遥控钥匙成为了一种趋势&#xff0c;为车主带来了便捷与安全的体验。虎克技术公司作为行业领先者&…...

第三天 Kubernetes进阶实践

第三天 Kubernetes进阶实践 本章介绍Kubernetes的进阶内容&#xff0c;包含Kubernetes集群调度、CNI插件、认证授权安全体系、分布式存储的对接、Helm的使用等&#xff0c;让学员可以更加深入的学习Kubernetes的核心内容。 ETCD数据的访问 kube-scheduler调度策略实践 预选与…...

redis小结

1.mysql是数据库,redis是数据库&#xff0c;那么什么时候使用应该使用哪种数据库? redis做缓存是为了缓解mysql的压力&#xff0c;在数据库表数据量上千万&#xff0c;并且访问频繁时&#xff0c;mysql压力增大&#xff0c;在有索引的情况下依旧效果不佳&#xff0c;需要使用…...

PHP伪协议详解

PHP伪协议详解 一、前言1.什么是PHP伪协议&#xff1f;2.什么时候用PHP伪协议? 二、常见的php伪协议php://inputphp://filterzip://与bzip2://与zlib://协议data://phar:// 一、前言 1.什么是PHP伪协议&#xff1f; PHP伪协议是PHP自己支持的一种协议与封装协议&#xff0c;…...

进程:守护进程

一、守护进程的概念 守护进程是脱离于终端控制&#xff0c;且运行在后端的进程。&#xff08;孤儿进程&#xff09;守护进程不会将信息显示在任何终端上影响前端的操作&#xff0c;也不会被终端产生的任何信息打断&#xff0c;例如&#xff08;ctrlc&#xff09;.守护进程独立…...

千里马平台项目管理理念

软件项目的成功和失败和技术关系不大&#xff0c;尤其是应用型软件&#xff0c;不可能有技术难关卡死了项目&#xff0c;大部分问题还是出现在项目管理层面。公司的业务形态是帮助客户构建自己的信息化生态圈&#xff0c;项目管理咨询也是其中的核心内容。 我们的软件项目管理理…...

GB 2312字符集:中文编码的基石

title: GB 2312字符集&#xff1a;中文编码的基石 date: 2024/3/7 19:26:00 updated: 2024/3/7 19:26:00 tags: GB2312编码中文字符集双字节编码区位码规则兼容性问题存储空间优化文档处理应用 一、GB 2312字符集的背景 GB 2312字符集是中国国家标准委员会于1980年发布的一种…...

我的创作周年纪念日

机缘 最初成为创作者的初心&#xff1a;整理自己的知识体系&#xff0c;普及前端知识 实战项目中的经验分享日常工作学习过程中的记录通过文章进行技术交流归纳和整理自己的知识体系 收获 创作的过程中收获&#xff1a; 获得了909粉丝的关注获得了很多正向的反馈&#xff0c…...

MySQL为什么要用B+树?

二叉树&#xff08;二叉查找树&#xff09; 平衡二叉树&#xff08;B树就是B-树&#xff09;(解决了二叉查找树的极端情况&#xff09; Q&#xff1a;具体是怎么解决的呢&#xff1f; A&#xff1a; 树左右两边层数相差不大于1一旦符合条件1的时候&#xff0c;就进行左旋/右…...

今天分享一个好看的输入法皮肤相信每个人心里住着一个少女心我们美化一下她吧

标题&#xff1a; 白日梦皮肤上线&#xff0c;百度输入法助你开启梦幻之旅&#xff01; 正文&#xff1a; 大家好呀&#xff01;今天我来给大家安利一款超级梦幻的百度输入法皮肤——“白日梦”系列&#xff01; 这款皮肤的设计灵感来源于我们内心深处的白日梦&#xff0c;充…...

力扣刷题Days11第二题--141. 环形链表(js)

目录 1,题目 2&#xff0c;代码 2.1快慢指针 2.2&#xff0c;哈希表 3&#xff0c;学习与总结 3.1自己尝试写快慢指针 反思 1,题目 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&…...

微信自动回复的设置

最近有客户来咨询&#xff0c;说是因为做内容引流到微信&#xff0c;所以每天很多人加他&#xff0c;每天要手动通过好友申请后打招呼&#xff0c;每天花费大量的时间去回答重复的问题&#xff0c;很机械的重复这些事。就问我们系统有没有能帮她解决这个烦恼的功能。 我说呀&a…...

SpringBoot源码解读与原理分析(一)SpringBoot整体概述

文章目录 第1章 SpringBoot整体概述1.1 Spring Framework1.1.1 Spring Framework的历史1.1.2 IOC与AOP 1.2 Spring Boot与Spring Framework1.3 Spring Boot的核心特性1.4 Spring Boot的体系 第1章 SpringBoot整体概述 Spring Framework 开发团队 支持不依赖外部容器的Web应用程…...

如何选择VR全景设备,才能拍摄高质量的VR全景?

随着VR全景技术的不断成熟和发展&#xff0c;VR全景已经成为了摄影爱好者乐于尝试的新手段&#xff0c;VR全景也为广大用户提供了一个全新的视角来探索世界&#xff0c;如果想要拍摄出高质量的VR全景&#xff0c;选择合适的VR全景拍摄设备以及掌握正确的拍摄技巧才是关键。 VR全…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

c++第七天 继承与派生2

这一篇文章主要内容是 派生类构造函数与析构函数 在派生类中重写基类成员 以及多继承 第一部分&#xff1a;派生类构造函数与析构函数 当创建一个派生类对象时&#xff0c;基类成员是如何初始化的&#xff1f; 1.当派生类对象创建的时候&#xff0c;基类成员的初始化顺序 …...

深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏

一、引言 在深度学习中&#xff0c;我们训练出的神经网络往往非常庞大&#xff08;比如像 ResNet、YOLOv8、Vision Transformer&#xff09;&#xff0c;虽然精度很高&#xff0c;但“太重”了&#xff0c;运行起来很慢&#xff0c;占用内存大&#xff0c;不适合部署到手机、摄…...

如何在Windows本机安装Python并确保与Python.NET兼容

✅作者简介&#xff1a;2022年博客新星 第八。热爱国学的Java后端开发者&#xff0c;修心和技术同步精进。 &#x1f34e;个人主页&#xff1a;Java Fans的博客 &#x1f34a;个人信条&#xff1a;不迁怒&#xff0c;不贰过。小知识&#xff0c;大智慧。 &#x1f49e;当前专栏…...

Vue 3 + WebSocket 实战:公司通知实时推送功能详解

&#x1f4e2; Vue 3 WebSocket 实战&#xff1a;公司通知实时推送功能详解 &#x1f4cc; 收藏 点赞 关注&#xff0c;项目中要用到推送功能时就不怕找不到了&#xff01; 实时通知是企业系统中常见的功能&#xff0c;比如&#xff1a;管理员发布通知后&#xff0c;所有用户…...