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的发行版,主要面…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
vue3 定时器-定义全局方法 vue+ts
1.创建ts文件 路径:src/utils/timer.ts 完整代码: import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...
selenium学习实战【Python爬虫】
selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
Razor编程中@Html的方法使用大全
文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...
论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...
stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
