leetCode 674. 最长连续递增序列 动态规划 / 贪心策略
674. 最长连续递增序列 - 力扣(LeetCode)
给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l
和 r
(l < r
)确定,如果对于每个 l <= i < r
,都有 nums[i] < nums[i + 1]
,那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]]
就是连续递增子序列。
示例 1:
输入:nums = [1,3,5,4,7] 输出:3 解释:最长连续递增序列是 [1,3,5], 长度为3。 尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。
示例 2:
输入:nums = [2,2,2,2,2] 输出:1 解释:最长连续递增序列是 [2], 长度为1。
>>思路和分析
本题相对于leetCode 300.最长递增子序列 最大区别在于 “连续”
- 不连续递增子序列的跟前0-i 个状态有关(两个for循环)
- 连续递增的子序列只跟前一个状态有关(一个for循环)
>>方法一:动态规划
1.确定dp数组(dp table)以及下标的含义
- dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]
注意这里的定义,一定是以下标i为结尾,并不是说一定以下标0为起始位置。
2.确定递推公式
如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1
- 即:dp[i] = dp[i - 1] + 1;
3.dp数组初始化
以下标i为结尾的连续递增的子序列长度最少也应该是1,即就是nums[i]这一个元素。所以dp[i]应该初始1;
4.确定遍历顺序
从递推公式上可以看出, dp[i + 1]依赖dp[i],所以一定是从前向后遍历
for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}
}
5.举例推导dp数组
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)
>>方法二:贪心策略
当遇到nums[i] > nums[i - 1]的情况,count++,否则count 为 1,记录下count的最大值即可
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int count=1;int result=1;// 连续子序列最少也是1for(int i=1;i<nums.size();i++) {// 连续记录if(nums[i]>nums[i-1]) count = count + 1;// 不连续,count从头开始else count=1;result = max(count,result);}return result;}
};
- 时间复杂度:O(n)
- 空间复杂度:O(1)
>>来自代码随想录课堂截图:
>>参考和推荐文章、视频
代码随想录 (programmercarl.com)
动态规划之子序列问题,重点在于连续!| LeetCode:674.最长连续递增序列_哔哩哔哩_bilibili
相关文章:
leetCode 674. 最长连续递增序列 动态规划 / 贪心策略
674. 最长连续递增序列 - 力扣(LeetCode) 给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。 连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每…...
数据中台实战(11)-数据中台的数据安全解决方案
0 微盟删库跑路 除了快、准和省,数据中台须安全,避免“微盟删库跑路”。 2020年2月23日19点,国内最大精准营销服务商微盟出现大面积系统故障,旗下300万商户线上业务全停,商铺后台所有数据被清。始作俑者是一位运维&a…...
林沛满-TCP之在途字节数
本文整理自:《Wireshark网络分析的艺术 第1版》 作者:林沛满 著 出版时间:2016-02 我一直谨记斯蒂芬霍金的金玉良言—每写一道数学公式就会失去一半读者。不过为了深度分析网络包,有时候是不得不计算的,好在小学一年级…...
HTTPS 加密工作过程
引言 HTTP 协议内容都是按照文本的方式明文传输的,这就导致在传输过程中出现一些被篡改的情况。例如臭名昭著的运营商劫持。显然, 明文传输是比较危险的事情,为此引入 HTTPS ,HTTPS 就是在 HTTP 的基础上进行了加密, 进一步的来保…...
校招秋招,性格和职业有关系吗?
企业在招聘应届毕业生时不再局限于普通的面试或者笔试,在互联网时代,为了能够更好的匹配需要的优质人才,企业会通过各种测试来提高招聘的准确率以及成功率。也许以前很多人都听说过性格和职业是有一定关系的,但是如何确定自己的性…...
网络和系统操作命令
目录 ping:用于检测网络是否通畅,以及网络时延情况。ipconfig:查看计算机的IP参数配置信息,如IP地址、默认网关、子网掩码等信息。netstat:显示协议统计信息和当前TCP/IP网络连接。tasklist:显示当前运行的…...
刷穿力扣(1~30)
更好的阅读体验 \huge{\color{red}{更好的阅读体验}} 更好的阅读体验 1. 两数之和 哈希表遍历数组,同时用 HashMap 维护已出现过的数及其下标若当前的数 nums[i] 满足 target - nums[i] 曾经出现过,则直接返回否则将其加入到哈希表中。 class Solution …...
栈和队列的基本操作
(一)实验类型:设计性 (二)实验目的: 1.掌握栈和队列的抽象数据类型。 2.掌握实现栈和队列的各种操作的算法。 3.理解栈与递归的关系。 4. 掌握队列的链式存贮结构及基…...
变压器绕组断股往往导致直流电阻不平衡率超标
变压器绕组断股往往导致直流电阻不平衡率超标, 例如, 某电厂 SFPSL—12000/220 型主变压器, 色谱分析结果发现总烃含量急剧增长, 测直流电阻, 其结果是高、 低压侧与制造厂及历年的数值相比较无异常, 但中压…...
stack和queque
1.stack 1.1定义 T 是容器内的数据类型; Container是数据类型的容器适配器 vector和list和stack的区别 1.2 stack的功能 注意这里没有迭代器;原因stack是先进后出的规律;这就规定该容器不可以随机访问; 2. queue...
信息学 学习/复习 抽签器(附源码)
问你一个问题,你考试前怎么复习呀? 效果图 以下是源代码,可自行修改 [C] #include<bits/stdc.h> #include<windows.h> using namespace std; vector<string>item; int main(void) {item.push_back("Manacher"…...
基于LADRC自抗扰控制的VSG三相逆变器预同步并网控制策略(Simulink仿真实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
[0xGame 2023] week1
整理一下,昨天该第二周了。今天应该9点结束提交,等我写完就到了。 PWN 找不到且不对劲的flag 第1题是个nc测试,但也不完全是,因为flag在隐含目录里 高端的syscall 程序使用了危险函数,并且没有canary阻止࿰…...
Matlab矩阵——矩阵行列互换
问题:如何将 1*n 的矩阵转换为指定 M*N 的矩阵,或者将 M*N 的矩阵转换为 1*n 的矩阵? 处理方法:使用 reshape 函数进行矩阵的行列互换 分两种情况如下: 一、将 1*n 的矩阵转换为指定 M*N 的矩阵 假如有4个坐标值&a…...
OpenMesh 网格面片随机赋色
文章目录 一、简介二、实现代码三、实现效果一、简介 OpenMesh中的赋色方式与Easy3D很是类似,它统一有一个属性数组来进行管理,我们在进行赋色等操作时,必须要首先添加该属性才能进行使用,这里也进行记录一下(法向量等特征也是类似的操作)。 二、实现代码 #define _USE_…...
SpringSecurity源码学习一:过滤器执行原理
目录 1. web过滤器Filter1.1 filter核心类1.2 GenericFilterBean1.3 DelegatingFilterProxy1.3.1 原理1.3.2 DelegatingFilterProxy源码 2. FilterChainProxy源码学习2.1 源码2.1.1 doFilterInternal方法源码2.1.1.1 getFilters()方法源码2.1.1.2 VirtualFilterChain方法源码 3…...
8.2 JUC - 4.Semaphore
目录 一、是什么?二、简单使用三、semaphore应用四、Semaphore原理 一、是什么? Semaphore:信号量,用来限制能同时访问共享资源的线程上限 二、简单使用 public class TestSemaphore {public static void main(String[] args) …...
前端try和catch
为什么要使用try catch 使用try...catch语句是为了处理和管理可能会在程序运行过程中发生的异常或错误情况。以下是一些使用try...catch的主要原因: 错误处理:在开发过程中,无法避免地会出现各种错误,如网络请求失败、数据解析错误…...
Unity可视化Shader工具ASE介绍——2、ASE的Shader创建和输入输出
大家好,我是阿赵,这里继续介绍Unity可视化写Shader的ASE插件的用法。上一篇介绍了ASE的安装和编辑器界面分布,这一篇主要是通过一个简单的例子介绍shader的创建和输入输出。 一、ASE的Shader创建 这里先选择Surface类型的Shader,…...
目标检测算法改进系列之Backbone替换为Swin Transformer
Swin Transformer简介 《Swin Transformer: Hierarchical Vision Transformer using Shifted Windows》作为2021 ICCV最佳论文,屠榜了各大CV任务,性能优于DeiT、ViT和EfficientNet等主干网络,已经替代经典的CNN架构,成为了计算机…...
【技术干货】如何通过 DP 实现支持经典蓝牙的联网单品设备与 App 配对
经典蓝牙模块(Classic Bluetooth)主要用于呼叫和音频传输,所以经典蓝牙最主要的特点就是功耗大,传输数据量大。蓝牙耳机、蓝牙音箱等场景大多采用经典蓝牙,因为蓝牙是为传输声音而设计的,是短距离音频传输的…...
【Unity Build-In管线的SurfaceShader剖析_PBS光照函数】
Unity Build-In管线的SurfaceShader剖析 在Unity Build-In 管线(Universal Render Pipeline)新建一个Standard Surface Shader文件里的代码如下:选中"MyPBR.Shader",在Inspector面板,打开"Show generat…...
thinkphp5实现ajax图片上传,压缩保存到服务器
<div class"warp"><input type"file" id"file" accept"image/*" onchange"upimg(this)" /></div> <img src"" /> <script>//上传图片方法function upimg(obj){var fileData obj.…...
王道考研计算机网络——传输层
一、传输层概述 复用:发送方不同的应用进程都可以使用同一个传输层的协议来传送数据 分用:接收方的传输层在去除报文段的首部之后能把数据交给正确的应用进程 熟知端口号就是知名端口号0-1023 客户端使用的端口号是动态变化的,不是唯一确定…...
08 集群参数配置(下)
Kafka Broker不需要太大的堆内存? Kafka Broker不需要太大的堆内存?应该把内存留给页缓存使用? kafka刷盘时宕机 kafka认为写入成功是指写入页缓存成功还是数据刷到磁盘成功算成功呢?还是上次刷盘宕机失败的问题,页…...
mac文件为什么不能拖进U盘?
对于Mac用户来说,可能会遭遇一些烦恼,比如在试图将文件从Mac电脑拖入U盘时,却发现文件无法成功传输。这无疑给用户带来了很大的不便。那么,mac文件为什么不能拖进U盘,看完这篇你就知道了。 一、U盘的读写权限问题 如果…...
RK3568的CAN驱动适配
目录 背景: 1.内核驱动模块配置 2.设备树配置 3.功能测试 4.bug修复 背景: 某个项目上使用RK3568的芯片,需要用到4路CAN接口进行通信,经过方案评审后决定使用RK3568自带的3路CAN外加一路spi转的CAN实现功能,在这个…...
Opengl之立方体贴图
简单来说,立方体贴图就是一个包含了6个2D纹理的纹理,每个2D纹理都组成了立方体的一个面:一个有纹理的立方体。你可能会奇怪,这样一个立方体有什么用途呢?为什么要把6张纹理合并到一张纹理中,而不是直接使用6个单独的纹理呢?立方体贴图有一个非常有用的特性,它可以通过一…...
EF Core报错:Error Number:-2146893019
appsettings.json中的连接字符串要添加上:TrustServerCertificatetrue; 所以这里的连接字符串为:Data SourceLAPTOP-61GDB2Q7\\SQLEXPRESS;Initial CatalogMvcMovie.Data;Persist Security InfoTrue;TrustServerCertificatetrue;User IDsa;Passwordroot…...
QT之可自由折叠和展开的布局
介绍和功能分析 主要是实现控件的折叠和展开,类似抽屉控件,目前Qt自带的控件QToolBox具有这个功能,但是一次只能展开一个,所以针对自己的需求可以自己写一个类似的功能,这里实现的方法比较多,其实原理也比较…...
无锡快速建设网站方法/百度网站推广一年多少钱
• 向指定的txt文件中写入键盘输入的内容,然后再重新读取该文件的内容,显示到控制台上。 • 键盘录入5个学生信息(姓名, 成绩),按照成绩从高到低存入文本文件。 package 复习第七章作业第四答题;import java.io.*; import java.util.*;publ…...
拓者室内设计网站/千锋教育和达内哪个好
系统环境 * 3 Ubuntu 16.04 mysql 8.0.12 docker 18.06.1-ce docker-compose 1.23.0-rc3 *3 > PS ###我用的是虚拟机, 所以起了3个虚拟机,分配 IP如下### 主IP :192.168.100.100 从IP :192.168.100.101、192.168.100.102 #开…...
大型网站开发实战/网络营销手段
刚从微博上看到,大家来围观一下吧~ -------------------------------------------------------------------------------------------------------------------- 我怀着复杂的心情来发这个贴,告诉大家一个你根本就不知道的敦煌!王树彤总裁&am…...
做算命网站挣钱吗/百度云
1、%取余运算符只能用于整型 2、 1) malloc 函数: void *malloc(unsigned int size) 在内存的动态分配区域中分配一个长度为size的连续空间,如果分配成功,则返回所分配内存空间的首地址,否则返回NULL,申请的内存不会…...
网站开发工程师职业定位/新网站推广最直接的方法
20150527.C语言—1人已学习 课程介绍 尹成老师带你步入 C 语言的殿堂,讲课生动风趣、深入浅出,全套视频内容充实,整个教程以 C 语言为核心,完整精彩的演练了数据结构、算法、设计模式、数据库、大数据高并发检索、文件重定向、…...
北京工程质量建设协会网站/企业网站怎么制作
生产者消费者问题是多线程并发中一个非常经典的问题,相信学过操作系统课程的同学都清楚这个问题的根源。本文将就四种情况分析并介绍生产者和消费者问题,它们分别是:单生产者-单消费者模型,单生产者-多消费者模型,多生…...