代码随想Day52 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
300.最长递增子序列
这道题目的重点在于动态数组的定义
dp[i]:以nums[i]为结尾的最长递增子序列,因为这样定义可以进行递推;
递推:j从0-i进行对比,如果nums[i]大于nums[j],dp[i]=dp[j]+1;
初始化:所有的元素向初始化为1;
遍历顺序:从前到后;
详细代码如下:
class Solution {
public:
int lengthOfLIS(vector<int>& nums)
{if(nums.size()==0) return 0;vector<int>dp(nums.size(), 1); //init as 1int max_len = 1;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}max_len = max(max_len, dp[i]);}return max_len;
}
};
674. 最长连续递增序列
这道题的相比上一题,因为是连续递增,所以只需要和前一个num[i-1]相比即可,不再进行详细分析,详细代码如下:
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums)
{if(nums.size()==0) return 0;vector<int>dp(nums.size(), 1);int max_len = 1;for(int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) dp[i] = dp[i - 1] + 1;max_len = max(max_len, dp[i]);}return max_len;
}};
718. 最长重复子数组
这道题是对两个数组进行判断,因此需要二维数组,分析如下:
dp[i][j]:以A[i-1]为结尾和以B[j-1]为结尾的数组的最长重复子数组长度;i-1的结尾的原因,是这样初始化方便写,而不需要进行额外的判断。
递推:如果两个值相等,则dp[i][j]=dp[i-1][j-1];
初始化:根据递推公式,dp[0][0]应该是0,否则后续就无法得到想要的状态结果;
遍历:进行两层嵌套,从前往后即可;
详细代码如下:
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2)
{//二维dp//dp[i][j]:以A的i-1结尾,B的j-1结尾的最长重复长度//注意这里是为了初始化更方便vector<vector<int>>dp(nums1.size()+1, vector<int>(nums2.size() + 1, 0));int max_len = 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;max_len = max(max_len, dp[i][j]);}}return max_len;
}};
注意,上述代码可以进行空间优化,因为dp[i][j]仅和左上角元素有关,所以可以压缩维度,把i维度压缩,运用滚动数组即可,要注意的是同01背包问题一样,为了不把数据踩踏,里层的循环需要逆向,这样就不会篡改上一层的数据导致错误。
详细代码如下:
class Solution {
public:
int findLength(vector<int>& nums1, vector<int>& nums2)
{vector<int>dp(nums2.size() + 1, 0); //压缩第一个维度int max_len = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j =nums2.size(); j >= 1; j--) //防止踩踏数据{if (nums1[i - 1] == nums2[j - 1]) dp[j] = dp[j - 1] + 1;else dp[j] = 0; //不相等需要赋值以便下次使用max_len = max(max_len, dp[j]);}}return max_len;}
相关文章:
代码随想Day52 | 300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
300.最长递增子序列 这道题目的重点在于动态数组的定义 dp[i]:以nums[i]为结尾的最长递增子序列,因为这样定义可以进行递推; 递推:j从0-i进行对比,如果nums[i]大于nums[j],dp[i]dp[j]1; 初始化…...
使用 pytest 相关特性重构 appium_helloworld
一、前置说明 在 pytest 基础讲解 章节,介绍了 pytest 的特性和基本用法,现在我们可以使用 pytest 的一些机制,来重构 appium_helloworld 。 appium_helloworld 链接: 编写第一个APP自动化脚本 appium_helloworld ,将脚本跑起来 代码目录结构: pytest.ini 设置: [pyt…...
猪目标检测数据集VOC格式600张
猪是一种常见的哺乳动物,通常被人们认为是肉食动物,但实际上猪是杂食性动物,以植物性食物为主,也有偶尔食肉的习性。猪的体型较大,圆胖的体型和圆润的脸庞使其显得憨态可掬。它们主要通过嗅觉来感知周围环境࿰…...
Pandas中concat的用法
Pandas中concat的用法 pd.concat 是 pandas 库中的一个函数,用于将多个 pandas 对象(如 Series、DataFrame)沿指定轴进行合并连接。 pd.concat(objs, axis0, joinouter, ignore_indexFalse, keysNone, levelsNone, namesNone, verify_in…...
【C++】引用详解
前言 在学习C语言时,我们通常会遇到两个数交换的问题,为了实现这一功能,我们会编写一个经典的Swap函数,如下所示: void Swap(int *a, int *b) {int tmp *a;*a *b;*b tmp; } 然而,这个Swap函数看起来可…...
平时的一些思考内容
文章目录 阶乘位运算求概率 阶乘 阶乘是一很迷人的,刚开始的的变化还不是很大,到后面变化类似于直线上升的,不知道现实中哪些实例来表示阶乘。19的阶乘就已经超过了long了,在竞赛或者其他中要求2023或者很大数字的阶乘就需要考虑…...
AIGC时代下,结合ChatGPT谈谈儿童教育
引言 都2024年了,谈到儿童教育,各位有什么新奇的想法嘛 我觉得第一要务,要注重习惯养成,我觉得聊习惯养成这件事情范围有点太大了,我想把习惯归纳于底层逻辑,我们大家都知道,在中国式教育下&a…...
Java中的锁(一)
一、前言 在Java中,锁是用于多线程同步的重要概念。它可以保护共享资源,确保多个线程在访问共享资源时的数据一致性。 共享资源指的是多个线程同时对同一份资源进行访问 (读写操作),被多个线程访问的资源就称为共享资源。 如何保证多个线程访…...
CSS-SVG-环形进度条
线上代码地址 <div class"circular-progress-bar"><svg><circle class"circle-bg" /><circle class"circle-progress" style"stroke-dasharray: calc(2 * 3.1415 * var(--r) * (var(--percent) / 100)), 1000" …...
英语中修饰头发的形容词顺序是怎么样的(加补充)
一、英语描述发型 :漂亮长短形状颜色头发。 例如她有一头美丽的黑色的直发。She has beautiful long straight black hair.二、多个形容词修饰同一名词时的顺序是固定的,其顺序为:①冠词、指示代词、不定代词、物主代词②序数词基数词③一般性描绘形容词…...
python的WebSocket编程详解,案例群聊系统实现
1.websocket相关 1.1为什么要用websocket 如果有需求要实现服务端向客户端主动推送消息时(比如聊天室,群聊室)有哪几种方案 轮训:让浏览器每隔两秒发送一次请求,缺点:有延时,请求太多网站压力…...
flutter学习-day22-使用GestureDetector识别手势事件
文章目录 1. 介绍2. 使用2-1. 单击双击和长按2-2. 拖动和滑动2-3. 缩放 3. 注意点 1. 介绍 在 flutter 中,GestureDetector 是手势识别的组件,可以识别点击、双击、长按、拖动、缩放等手势事件,并且可以与子组件进行交互,构造函数…...
uni-app tabbar组件
锋哥原创的uni-app视频教程: 2023版uniapp从入门到上天视频教程(Java后端无废话版),火爆更新中..._哔哩哔哩_bilibili2023版uniapp从入门到上天视频教程(Java后端无废话版),火爆更新中...共计23条视频,包括:第1讲 uni…...
【Midjourney】Midjourney根据prompt提示词生成人物图片
目录 🍇🍇Midjourney是什么? 🍉🍉Midjourney怎么用? 🔔🔔Midjourney提示词格式 Midjourney生成任务示例 例1——航空客舱与乘客 prompt prompt翻译 生成效果 大图展示 细节大…...
Oracle 拼接字符串
语法 使用||拼接如果内容中有单引号,则可在该单引号前面再加一个单引号进行转义 例子 比如有一个业务是根据需要生成多条插入语句 select insert into des_account_des_role(des_account_id, roles_id) values( || id || , || (select id from des_role where wo…...
探究公有云中的巨人:深入分析大数据产品的架构设计
目录 一、服务器分类 二、公有云基础和产品 网络 vpc专有网络 弹性公网IP(Elastic IP)...
亚马逊云科技 re:Invent 2023 产品体验:亚马逊云科技产品应用实践 王炸产品 Amazon Q,你的 AI 助手
意料之中 2023年9月25日,亚马逊宣布与 Anthropic 正式展开战略合作,结合双方在更安全的生成式 AI 领域的先进技术和专业知识,加速 Anthropic 未来基础模型的开发,并将其广泛提供给亚马逊云科技的客户使用。 亚马逊云科技开发者社…...
并发编程大杀器,京东多线程编排工具asyncTool
一、简介 并发编程大杀器,京东多线程编排工具asyncTool,可以解决任意的多线程并行、串行、阻塞、依赖、回调的并行框架,可以任意组合各线程的执行顺序,带全链路执行结果回调。多线程编排一站式解决方案。 二、特点 多线程编排&am…...
【开源项目】智慧交通~超经典开源项目实景三维数字孪生高速
数字孪生高速运营管理平台,以提升高速公路管理水平和方便出行为主要目标,充分利用云计算、AI、大数据等,实现对高速公路控制、指挥、运营的智能化。飞渡科技以实景三维数据为基础,基于大数据、高分遥感、数据分析以及数据融合等前…...
udp多播/组播那些事
多播与组播 多播(multicast)和组播(groupcast)是相同的概念,用于描述在网络中一对多的通信方式。在网络通信中,单播(unicast)是一对一的通信方式,广播(broad…...
k8s从入门到放弃之Ingress七层负载
k8s从入门到放弃之Ingress七层负载 在Kubernetes(简称K8s)中,Ingress是一个API对象,它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress,你可…...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统
目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索(基于物理空间 广播范围)2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
基于Springboot+Vue的办公管理系统
角色: 管理员、员工 技术: 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能: 该办公管理系统是一个综合性的企业内部管理平台,旨在提升企业运营效率和员工管理水…...
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...
