Leetcode.1567 乘积为正数的最长子数组长度
题目链接
Leetcode.1567 乘积为正数的最长子数组长度 Rating : 1710
题目描述
给你一个整数数组 nums,请你求出乘积为正数的最长子数组的长度。
一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。
请你返回乘积为正数的最长子数组长度。
示例 1:
输入:nums = [1,-2,-3,4]
输出:4
解释:数组本身乘积就是正数,值为 24 。
示例 2:
输入:nums = [0,1,-2,-3,-4]
输出:3
解释:最长乘积为正数的子数组为 [1,-2,-3] ,乘积为 6 。
注意,我们不能把 0 也包括到子数组中,因为这样乘积为 0 ,不是正数。
示例 3:
输入:nums = [-1,-2,-3,0,1]
输出:2
解释:乘积为正数的最长子数组是 [-1,-2] 或者 [-2,-3] 。
提示:
- 1<=nums.length<=1051 <= nums.length <= 10^51<=nums.length<=105
- −109<=nums[i]<=109-10^9 <= nums[i] <= 10^9−109<=nums[i]<=109
分析:
首先,要想子数组的乘积为正数,那么子数组里面一定不包含 0,而且负数的个数为偶数。
- 我们用
positive记录 正数 的个数 - 我们用
negative记录 负数 的个数 - 我们用
neg_pos(初始为-1)记录 第一个负数出现的位置
在遍历的过程中,会遇到以下三种情况:
nums[i] > 0,遇到正数positive就+1。nums[i] < 0,遇到负数negative就+1,如果此时neg_pos == -1,说明nums[i]是目前遇到的第一个负数,更新neg_pos = i。nums[i] == 0,遇到0,positve重置为0,negative重置为0,neg_pos重置为-1。相当于0把每一个合法的子数组都截开了。
在更新答案ans的时候:
- 如果当前子数组中的负数个数是偶数个,即
negative % 2 == 0,ans = max(ans , positive + negative),即当前整个子数组乘积都是正数。 - 如果当前子数组中的负数个数是奇数个,即
negative % 2 != 0,那么当前子数组就需要剔除一个负数来保证整个子数组乘积为正数,我们就选择剔除 第一个出现的负数。即ans = max(ans , i - neg_pos),剔除了 下标为neg_pos的负数。
时间复杂度:O(n)O(n)O(n)
C++代码:
class Solution {
public:int getMaxLen(vector<int>& nums) {int positive = 0,negative = 0,neg_pos = -1;int ans = 0;int n = nums.size();for(int i = 0;i < n;i++){int x = nums[i];if(x > 0) positive++;else if(x < 0){negative++;if(neg_pos == -1) neg_pos = i;}else{positive = 0;negative = 0;neg_pos = -1;}if(negative % 2 == 0) ans = max(ans,negative + positive);else ans = max(ans,i - neg_pos);}return ans;}
};
Java代码:
class Solution {public int getMaxLen(int[] nums) {int positive = 0;int negative = 0;int neg_pos = -1;int n = nums.length;int ans = 0;for(int i = 0;i < n;i++){int x = nums[i];if(x > 0) positive++;else if(x < 0){negative++;if(neg_pos == -1) neg_pos = i;}else{positive = 0;negative = 0;neg_pos = -1;}if(negative % 2 == 0) ans = Math.max(ans,negative + positive);else ans = Math.max(ans,i - neg_pos);}return ans;}
}
相关文章:
Leetcode.1567 乘积为正数的最长子数组长度
题目链接 Leetcode.1567 乘积为正数的最长子数组长度 Rating : 1710 题目描述 给你一个整数数组 nums,请你求出乘积为正数的最长子数组的长度。 一个数组的子数组是由原数组中零个或者更多个连续数字组成的数组。 请你返回乘积为正数的最长子数组长度…...
部分库与使用方法总结(自用)
1.tqdm tqdm是Python的进度条库,可以在长循环操作中显示进度提示 tqdm.tqdm:传入数字 from tqdm import tqdm for i in tqdm(range(1, 5)):print(i)使用bar_format "{l_bar}{bar}"可以只显示进度条 from tqdm import tqdm for i in tqdm(range(1, 5), ba…...
C++实现日期类
文章目录前言1.日期类的功能分析1.大致分析2.接口设计2.具体实现1.日期类的成员函数和成员变量2.初始化(构造函数)3.对日期进行天数推算4.比较相关的运算符重载5.前置后置自增或自减6.日期相减与流插入流提取1.日期相减2.重载流插入和流提取3.总结前言 之前介绍了C…...
想成为一名专业黑客,但不知道从哪里学起?我来教你。
成为一名黑客需要学什么? 想成为一名专业黑客,但不知道从哪里学起”很多人在后台问过这个问题,今天就为你介绍成为专业黑客必须学习的十个方面的知识,希望能为迷惘中的你指明方向。 想要成为网络hacker黑客?先来学习…...
VMware ESXi 7.0 U3k Unlocker OEM BIOS 集成网卡驱动和 NVMe 驱动 (集成驱动版)
ESXi 7 U3 标准版集成 Intel 网卡、USB 网卡 和 NVMe 驱动 请访问原文链接:https://sysin.org/blog/vmware-esxi-7-u3-sysin/,查看最新版。原创作品,转载请保留出处。 作者主页:www.sysin.org 本次针对 2023-02-21 发布的 ESXi …...
新的计算方法:预测益生菌在不同生长条件下的相互作用
谷禾健康 益生菌可以产生有益的维生素、消化酶、必需氨基酸、免疫调节和抗菌代谢产物,从而促进人体健康,预防肠道炎症性疾病、自身免疫性疾病和胃肠道感染。其宝贵特性已得到健康行业、医疗专业人士和公众的认可。 比起单菌株益生菌,多菌株益…...
python自学之《21天学通Python》(13)——第16章 数据库编程
数据库指的是以一定方式存储在一起、能为多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。而我们平时所说的数据库实际上是包含了数据库管理系统(DBMS)的,数据库管理系统是为管理数据库而设计的软件系统,它一…...
[架构之路-118]-《软考-系统架构设计师》-软架构设计-11-可靠性相关设计
第11节 可靠性相关设计11.1 可靠性基本概念可靠性工程是研究产品生命周期中故障的发生、发展规律,达到预防故障,消灭故障,提高产品可用性的工程技术。信息系统的可靠性是指系统在满足一定条件的应用环境中能够正常工作的能力,可以…...
电阻串联的作用
电阻串联常见作用 第一个作用是:阻抗匹配: 因为信号源的阻抗很低,跟信号线之间阻抗不匹配,串上一个电阻后,可以改善匹配情况,以减少反射,避免振荡等。 常见的阻抗匹配方法 1、使用变压器来做…...
leetcode 1675. Minimize Deviation in Array(最小化数组偏差)
数组里面有n个正整数,里面的数字可以无限次进行如下操作: 1.偶数可以除以2 2.奇数可以乘以2 数组中任意两元素差的最大值称为偏差。 把数组中的元素进行上面2种操作,使偏差最小。 思路: 数组中现有2种数字,一种是奇数…...
特征向量中心度(eigenvector centrality)算法原理与源码解析
前言 随着图谱应用的普及,图深度学习技术也逐渐被越来越多的数据挖掘团队所青睐。传统机器学习主要是对独立同分布个体的统计学习,而图深度学习则是在此基础上扩展到了非欧式空间的图数据之上,通过借鉴NLP和CV方向的模型思想,衍生…...
Vue3 中组件的使用(上)
目录前言:一、什么是组件二、注册组件1. 全局注册2. 局部注册二、传递数据【父 -> 子】1. 字符串数组的形式2. 对象的形式三、组件事件【子 -> 父】1. 字符串数组式声明自定义事件2. 【子组件】触发组件事件3. 【父组件】监听子组件自定义事件4. 组件事件例子…...
spring-boot、spring-cloud、spring-cloud-alibaba版本对应
一、查询 spring-boot(spring-boot-starter-parent) 版本号 https://mvnrepository.com/artifact/org.springframework.boot/spring-boot-starter-parent 二、查询 spring-cloud(spring-cloud-dependencies) 版本号 https://mvnrepository.com/artifact/org.springframework…...
【沐风老师】3DMAX一键楼梯脚本插件StairGenerator使用教程
3DMAX一键楼梯插件StairGenerator,不需要花费太多的时间,轻松从2D平面图生成3D楼梯模型,生成的楼梯模型细节丰富真实。 【主要功能】 1.简单:轻松实现2D到3D建模。 2.具有最详细三维结构的台阶平面图。 3.楼梯各部件完全参数化…...
OpenShift 简介
OpenShift 是红帽 Red Hat 公司基于开源的云平台,是平台即服务(PaaS),是一种容器应用平台。允许开发人员构建、测试和部署云应用。该系统是在 K8S 核心之上添加工具,从而实现更快的应用开发、部署及扩展。 在 OpenShi…...
netty自定义封包实现
文章目录说明分享内置编码器和解码器解码器编码器代码实现创建核心类消息实体类自定义编码类自定义解码类服务端ServerHandler入口类客户端ClientHandler入口类测试参考总结说明 netty是java重要的企业级NIO,使用它可以快速实现很多功能通信功能如:http、…...
ORA error集锦
1、oralce 数据客户端需要安装的问题 保存信息为: “无法连接到数据库,因为数据库客户端软件无法加载。确保已正确安装并配置数据库客户端软件” 从百度网盘下载,并安装win32 oracle client 安装包 2、ORA错误 “执行异常,ORA-00911: inval…...
格雷码的实现
格雷码:任意两个相邻的二进制数之间只有一位不同 想必通信专业的学生应该都接触过格雷码,它出现在数电、通信原理等课程里。 如下图所示一个四位格雷码是什么样子的: 格雷码的特点: 其最大的特点是任意上下相邻的两个码值间&am…...
快到金3银4了,准备跳槽的可以看看
前两天跟朋友感慨,今年的铜九铁十、裁员、疫情导致好多人都没拿到offer!现在已经12月了,具体明年的金三银四只剩下两个月。 对于想跳槽的职场人来说,绝对要从现在开始做准备了。这时候,很多高薪技术岗、管理岗的缺口和市场需求也…...
最新BlackArch发布,提供1400款渗透测试工具
近日,BlackArch Linux新版本发布,此版本为白帽子和安全研究人员提供了大约1400款渗透测试工具,如果你是一位白帽子或者安全研究人员,这个消息无疑会让你很感兴趣。BlackArch Linux是一款基于Arch Linux的发行版,主要面…...
UE5 学习系列(二)用户操作界面及介绍
这篇博客是 UE5 学习系列博客的第二篇,在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下: 【Note】:如果你已经完成安装等操作,可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作,重…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
【HTML-16】深入理解HTML中的块元素与行内元素
HTML元素根据其显示特性可以分为两大类:块元素(Block-level Elements)和行内元素(Inline Elements)。理解这两者的区别对于构建良好的网页布局至关重要。本文将全面解析这两种元素的特性、区别以及实际应用场景。 1. 块元素(Block-level Elements) 1.1 基本特性 …...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
【Go语言基础【12】】指针:声明、取地址、解引用
文章目录 零、概述:指针 vs. 引用(类比其他语言)一、指针基础概念二、指针声明与初始化三、指针操作符1. &:取地址(拿到内存地址)2. *:解引用(拿到值) 四、空指针&am…...
【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论
路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中(图1): mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
