代码随想录第五十二天——最长递增子序列,最长连续递增序列,最长重复子数组
leetcode 300. 最长递增子序列
题目链接:最长递增子序列
- dp数组及下标的含义
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度 - 递推公式
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值
所以`if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1) - dp数组初始化`
每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是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);}if (dp[i] > result) result = dp[i]; // 取长的子序列
}
整体代码如下:
class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;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);}if (dp[i] > result) result = dp[i]; // 取长的子序列}return result;}
};
时间复杂度: O(n^2)
空间复杂度: O(n)
leetcode 674. 最长连续递增序列
题目链接:最长连续递增序列
本题要求子序列是连续递增,所以只需要比较 nums[i]和 nums[i-1]
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};
时间复杂度:O(n)
空间复杂度:O(n)
leetcode 718. 最长重复子数组
题目链接:最长重复子数组
- dp数组及下标的含义
dp[i][j]:以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j] - 确定递推公式
当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1 - dp数组初始化
dp[i][0] 和dp[0][j]初始化为0 - 遍历顺序
外层for循环遍历A,内层for循环遍历B
版本一:二维数组
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 res = 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;}if (dp[i][j] > res) res = dp[i][j];}}return res;}
};
时间复杂度:O(n × m),n 为A长度,m为B长度
空间复杂度:O(n × m)
版本二:滚动数组
dp[i][j]由dp[i - 1][j - 1]推出,压缩为一维数组,dp[j]由dp[j - 1]推出。
遍历B数组的时候,就要从后向前遍历,这样避免重复覆盖
class Solution {
public:int findLength(vector<int>& A, vector<int>& B) {vector<int> dp(vector<int>(B.size() + 1, 0));int res = 0;for (int i = 1; i <= A.size(); i++) {for (int j = B.size(); j > 0; j--) {if (A[i - 1] == B[j - 1]) {dp[j] = dp[j - 1] + 1;} else dp[j] = 0; // 注意这里不相等的时候要有赋0的操作if (dp[j] > res) res = dp[j];}}return res;}
};
时间复杂度:O(n × m),n 为A长度,m为B长度
空间复杂度:O(m)
相关文章:
代码随想录第五十二天——最长递增子序列,最长连续递增序列,最长重复子数组
leetcode 300. 最长递增子序列 题目链接:最长递增子序列 dp数组及下标的含义 dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度递推公式 位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 1 的最大值 所以if (nums[i] > nums[j]) dp[i]…...
【大数据架构】OLAP实时分析引擎选型
OLAP引擎面临的挑战 常见OLAP引擎对比 OLAP分析场景中,一般认为QPS达到1000就算高并发,而不是像电商、抢红包等业务场景中,10W以上才算高并发,毕竟数据分析场景,数据海量,计算复杂,QPS能够达到1…...
代码随想录刷题题Day29
刷题的第二十九天,希望自己能够不断坚持下去,迎来蜕变。😀😀😀 刷题语言:C Day29 任务 ● 01背包问题,你该了解这些! ● 01背包问题,你该了解这些! 滚动数组 …...
CVE-2023-51385 OpenSSH ProxyCommand命令注入漏洞
一、背景介绍 ProxyCommand 是 OpenSSH ssh_config 文件中的一个配置选项,它允许通过代理服务器建立 SSH 连接,从而在没有直接网络访问权限的情况下访问目标服务器。这对于需要经过跳板机、堡垒机或代理服务器才能访问的目标主机非常有用。 二、漏洞简…...
如何寻找到相对完整的真正的游戏的源码 用来学习?
在游戏开发的学习之路上,理论与实践是并重的两个方面。对于许多热衷于游戏开发的学习者来说,能够接触到真实的、完整的游戏源码无疑是一个极好的学习机会。但问题来了:我们该如何寻找到这些珍贵的资源呢? 开源游戏项目 GitHub:地…...
数模学习day11-系统聚类法
本文参考辽宁石油化工大学于晶贤教授的演示文档聚类分析之系统聚类法及其SPSS实现。 目录 1.样品与样品间的距离 2.指标和指标间的“距离” 相关系数 夹角余弦 3.类与类间的距离 (1)类间距离 (2)类间距离定义方式 1.最短…...
SpringBoot+Redis实现接口防刷功能
场景描述: 在实际开发中,当前端请求后台时,如果后端处理比较慢,但是用户是不知情的,此时后端仍在处理,但是前端用户以为没点到,那么再次点击又发起请求,就会导致在短时间内有很多请求…...
TensorRT加速推理入门-1:Pytorch转ONNX
这篇文章,用于记录将TransReID的pytorch模型转换为onnx的学习过程,期间参考和学习了许多大佬编写的博客,在参考文章这一章节中都已列出,非常感谢。 1. 在pytorch下使用ONNX主要步骤 1.1. 环境准备 安装onnxruntime包 安装教程可…...
springboot常用扩展点
当涉及到Spring Boot的扩展和自定义时,Spring Boot提供了一些扩展点,使开发人员可以根据自己的需求轻松地扩展和定制Spring Boot的行为。本篇博客将介绍几个常用的Spring Boot扩展点,并提供相应的代码示例。 1. 自定义Starter(面试常问) Sp…...
19道ElasticSearch面试题(很全)
点击下载《19道ElasticSearch面试题(很全)》 1. elasticsearch的一些调优手段 1、设计阶段调优 (1)根据业务增量需求,采取基于日期模板创建索引,通过 roll over API 滚动索引; (…...
向爬虫而生---Redis 拓宽篇3 <GEO模块>
前言: 继上一章: 向爬虫而生---Redis 拓宽篇2 <Pub/Sub发布订阅>-CSDN博客 这一章的用处其实不是特别大,主要是针对一些地图和距离业务的;就是Redis的GEO模块。 GEO模块是Redis提供的一种高效的地理位置数据管理方案,它允许我们存储和查询…...
Vue项目里实现json对象转formData数据
平常调用后端接口传参都是json对象,当提交表单遇到有附件需要传递时,通常是把附件上传单独做个接口,也有遇到后端让提交接口一并把附件传递到后端,这种情况需要把参数转成formData的数据,需要用到new FormData()。json…...
leetcode刷题记录
栈 2696. 删除子串后的字符串最小长度 哈希表 1. 两数之和 用map来保存每个数和他的索引 383. 赎金信 用map来存储字符的个数 链表 2. 两数相加 指针的移动 动态规划 53. 最大子数组和 2707. 字符串中的额外字符 递归 101. 对称二叉树 数学 1276. 不浪费原料的汉堡…...
SpringMVC通用后台管理系统源码
整体的SSM后台管理框架功能已经初具雏形,前端界面风格采用了结构简单、 性能优良、页面美观大的Layui页面展示框架 数据库支持了SQLserver,只需修改配置文件即可实现数据库之间的转换。 系统工具中加入了定时任务管理和cron生成器,轻松实现系统调度问…...
深度解析Dubbo的基本应用与高级应用:负载均衡、服务超时、集群容错、服务降级、本地存根、本地伪装、参数回调等关键技术详解
负载均衡 官网地址: http://dubbo.apache.org/zh/docs/v2.7/user/examples/loadbalance/ 如果在消费端和服务端都配置了负载均衡策略, 以消费端为准。 这其中比较难理解的就是最少活跃调用数是如何进行统计的? 讲道理, 最少活跃数…...
备战2024美赛数学建模,文末获取历史优秀论文
总说(历年美赛优秀论文可获取) 数模的题型千变万化,我今天想讲的主要是一些「画图」、「建模」、「写作」和「论文结构」的思路,这些往往是美赛阅卷官最看重的点,突破了这些点,才能真正让你的美赛论文更上…...
Java加密解密大全(MD5、RSA)
目录 一、MD5加密二、RSA加解密(公加私解,私加公解)三、RSA私钥加密四、RSA私钥加密PKCS1Padding模式 一、MD5加密 密文形式:5eb63bbbe01eeed093cb22bb8f5acdc3 import java.math.BigInteger; import java.security.MessageDigest; import java.security…...
C语言程序设计考试掌握这些题妥妥拿绩点(写给即将C语言考试的小猿猴们)
目录 开篇说两句1. 水仙花数题目描述分析代码示例 2. 斐波那契数列题目描述分析代码示例 3. 猴子吃桃问题题目描述分析代码示例 4. 物体自由落地题目描述分析代码示例 5. 矩阵对角线元素之和题目描述分析代码示例 6. 求素数题目描述分析代码示例 7. 最大公约数和最小公倍数题目…...
编译ZLMediaKit(win10+msvc2019_x64)
前言 因工作需要,需要ZLMediaKit,为方便抓包分析,最好在windows系统上测试,但使用自己编译的第三方库一直出问题,无法编译通过。本文档记录下win10上的编译过程,供有需要的小伙伴使用 一、需要安装的软件…...
JS-基础语法(一)
JavaScript简单介绍 变量 常量 数据类型 类型转换 案例 1.JavaScript简单介绍 JavaScript 是什么? 是一种运行在客户端(浏览器)的编程语言,可以实现人机交互效果。 JS的作用 JavaScript的组成 JSECMAScript( 基础语法 )…...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
Caliper 配置文件解析:config.yaml
Caliper 是一个区块链性能基准测试工具,用于评估不同区块链平台的性能。下面我将详细解释你提供的 fisco-bcos.json 文件结构,并说明它与 config.yaml 文件的关系。 fisco-bcos.json 文件解析 这个文件是针对 FISCO-BCOS 区块链网络的 Caliper 配置文件,主要包含以下几个部…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...
多元隐函数 偏导公式
我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式,给定一个隐函数关系: F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 🧠 目标: 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z、 …...
Java后端检查空条件查询
通过抛出运行异常:throw new RuntimeException("请输入查询条件!");BranchWarehouseServiceImpl.java // 查询试剂交易(入库/出库)记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...
数据库正常,但后端收不到数据原因及解决
从代码和日志来看,后端SQL查询确实返回了数据,但最终user对象却为null。这表明查询结果没有正确映射到User对象上。 在前后端分离,并且ai辅助开发的时候,很容易出现前后端变量名不一致情况,还不报错,只是单…...
