leetcode303. 区域和检索 - 数组不可变(java)
前缀和数组的应用
- 区域和检索 - 数组不可变
- 题目描述
- 前缀和数组
- 代码演示
区域和检索 - 数组不可变
难度 - 简单
原题链接 - 区域和检索 - 数组不可变
题目描述
给定一个整数数组 nums,处理以下类型的多个查询:
计算索引 left 和 right (包含 left 和 right)之间的 nums 元素的 和 ,其中 left <= right
实现 NumArray 类:
NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ,包含 left 和 right 两点(也就是 nums[left] + nums[left + 1] + … + nums[right] )
示例 1:
输入:
[“NumArray”, “sumRange”, “sumRange”, “sumRange”]
[[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]]
输出:
[null, 1, -1, -3]
解释:
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))
提示:
1 <= nums.length <= 1e4
-105 <= nums[i] <= 1e5
0 <= i <= j < nums.length
最多调用 104 次 sumRange 方法
前缀和数组
核心思路是我们 new 一个新的数组 preSum 出来,preSum[i] 记录 nums[0…i-1] 的累加和,看图 10 = 3 + 5 + 2:
看这个 preSum 数组,如果我想求索引区间 [1, 4] 内的所有元素之和,就可以通过 preSum[5] - preSum[1] 得出。
:这样,sumRange 函数仅仅需要做一次减法运算,避免了每次进行 for 循环调用,最坏时间复杂度为常数 O(1)。
这个技巧在生活中运用也挺广泛的,比方说,你们班上有若干同学,每个同学有一个期末考试的成绩(满分 100 分),那么请你实现一个 API,输入任意一个分数段,返回有多少同学的成绩在这个分数段内。
代码演示
class NumArray {private int[]preSum;public NumArray(int[] nums) {preSum = new int[nums.length];preSum[0] = nums[0];for(int i = 1; i < nums.length;i++){preSum[i] = preSum[i - 1] + nums[i];}}public int sumRange(int left, int right) { return left != 0 ? preSum[right] - preSum[left - 1] : preSum[right] ;}
}
相关文章:
leetcode303. 区域和检索 - 数组不可变(java)
前缀和数组的应用 区域和检索 - 数组不可变题目描述前缀和数组代码演示 区域和检索 - 数组不可变 难度 - 简单 原题链接 - 区域和检索 - 数组不可变 题目描述 给定一个整数数组 nums,处理以下类型的多个查询: 计算索引 left 和 right (包含 left 和 righ…...
PHP 安装Composer,vue前端依赖包
电脑安装Composer 官网下载:https://getcomposer.org/Composer-Setup.exe 后端安装: 检查是否安装依赖: 安装Composer install 或 Composer i 前端安装: yarn install 安装依赖...
OpenCV项目开发实战--基于Python/C++实现鼠标注释图像和轨迹栏来控制图像大小
鼠标指针是图形用户界面 (GUI) 中的关键组件。没有它,您就无法真正考虑与 GUI 进行交互。那么,让我们深入了解 OpenCV 中鼠标和轨迹栏的内置函数。我们将演示如何使用鼠标来注释图像,以及如何使用轨迹栏来控制图像的大小 我们将使用下图来演示 OpenCV 中鼠标指针和轨迹栏功能…...
❤ Vue使用Eslint检测报错问题和解决
❤ Vue使用Eslint检测报错问题和解决 1、 关闭Eslint检测 关闭ESLint语法检测即可:具体步骤如下: 第一步我们打开setting设置: 打开左上角的file,然后点击setting 接下来进入setting以后我们来看下面操作: eol-l…...
解决运行在微信小程序中报[ app.json 文件内容错误] app.json: app.json 未找到(env: Windows,mp,1.05.2204
找到project.config.json文件夹 添加 "miniprogramRoot": "unpackage/dist/dev/mp-weixin/", 即可...
python 基础 -- 安装Python模块
作为一个流行的开源开发项目,Python拥有一个由贡献者和用户组成的活跃支持社区,他们还根据开源许可条款向其他Python开发人员提供他们的软件。 这允许Python用户有效地共享和协作,从其他人已经创建的常见(有时甚至是罕见的!)问题的解决方案中…...
C语言实现状态机
关于状态机,基础的知识点可以自行理解,讲解的很多,这里主要是想写一个有限状态机FSM通用的写法,目的在于更好理解,移植,节省代码阅读与调试时间,体现出编程之美。 传统的实现方案 if...else : …...
交叉编译工具链arm-linux-gnueabihf的安装-ubuntu 20.04
前面下载安装步骤参考该博主的文章 http://t.csdn.cn/ZbjFX 另:本人对所遇到的环境变量的配置问题作补充 1.修改环境变量 建议直接在.bashrc文件作修改 ,修改方式相同 ( vi :视自己的编辑器而定) sudo vi ~/.bashrc 2.修改环境变量后,可…...
Java的类加载器
类加载 1、ClassLoader 用来加载 Class 文件 2、 系统内置的ClassLoader 通过双亲委托加载指定目录下的class和资源 3、 可以自定义ClassLoader 一般覆盖findClass() 4、ContextClassLoader 与线程相关,可以获取和设置,可以绕过双亲委托的机制。 三个类…...
Stable Diffusion web UI 部署详细教程
前言 本文使用 AutoDL 平台进行 Stable Diffusion web UI 云端部署 AutoDL 官网:AutoDL算力云 | 弹性、好用、省钱。租GPU就上AutoDL Stable Diffusion web UI 官网:AUTOMATIC1111/stable-diffusion-webui: Stable Diffusion web UI (github.com) 步…...
《深度学习计算机视觉 》书籍分享(包邮送书三本)
深度学习计算机视觉介绍 随着计算机技术的发展和进步,计算机视觉领域得到了广泛的关注和研究。而深度学习作为一种强大的机器学习方法,已经成为计算机视觉领域的重要工具之一。本文将介绍深度学习在计算机视觉中的应用和取得的成果。 深度学习是一种模…...
【使用 k 折叠交叉验证的卷积神经网络(CNN)】基于卷积神经网络的无特征EMG模式识别研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
微服务 Nacos配置热部署
在nacos中添加配置文件 在配置列表中添加配置, 注意:项目的核心配置,需要热更新的配置才有放到nacos管理的必要。基本不会变更的一些配置还是保存在微服务本地比较好。 从微服务拉取配置 微服务要拉取nacos中管理的配置,并且与…...
国产调度器之光——Fsched到底有多能打?
这是一篇推荐我们速石自研调度器——Fsched的文章。 看起来在专门写调度器,但又不完全在写。 往下看,你就懂了。 本篇一共五个章节: 一、介绍一下主角——速石自研调度器Fsched 二、只要有个调度器,就够了吗? 三…...
LeetCode:53. 最大子数组和 - Python
53. 最大子数组和 问题描述: 给你一个整数数组 nums ,请你找出一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 子数组 是数组中的一个连续部分。 示例 1: 输入:nums [-…...
网站建设 之 react usestate
react着重在于“不可变动” 如果变动了怎么办呢?那就整个新的 局部变量/函数/jsx-》state/props-〉ref,依次越来越难变 每次state/props,局部变量/函数/jsx都是新的 既然函数是新的,那么就会有一个问题,回调函数用…...
第一讲使用IDEA创建Java工程——HelloWorld
一、前言导读 为了能够让初学者更快上手Java,不会像其他书籍或者视频一样,介绍一大堆历史背景,默认大家已经知道Java这么编程语言了。本专栏只会讲解干货,直接从HelloWord入手,慢慢由浅入深,讲个各个知识点,这些知识点也是目前工作中项目使用的,而不是讲一些老的知识点…...
BootstrapBlazor组件使用:数据注解
文章目录 前言BB数据注解数据注解源码数据注解简介注解简单实例[BB 编辑弹窗](https://www.blazor.zone/edit-dialog)[ValidateForm 表单组件](https://www.blazor.zone/validate-form)使用简介 前言 BootstrapBlazor(一下简称BB)是个特别好用的组件,基本上满足了大…...
MySQL 触发器
文章目录 1.简介2.行级与语句级触发器3.触发时机4.触发器优缺点5.创建触发器语法示例 6.查看触发器7.删除触发器参考文献 1.简介 触发器(Trigger)是与表关联的命名数据库对象,当表发生特定事件时激活。 触发器的一些用途是对要插入表中的值执…...
DPDK主从进程模式 rte_mempool_put失败
版本:19.11.6 情景:主进程应用rte_mempool_create创建mempool,rte_mempool_get获取数据;从进程应用rte_mempool_put归还数据 问题:从进程rte_mempool_put无法归还数据 原因:DPDK通过rte_mempool_ops_tab…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
微信小程序 - 手机震动
一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注:文档 https://developers.weixin.qq…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...
html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用
文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么?1.1.2 感知机的工作原理 1.2 感知机的简单应用:基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

