LeetCode解法汇总307. 区域和检索 - 数组可修改
目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
描述:
给你一个数组 nums ,请你完成两类查询。
- 其中一类查询要求 更新 数组
nums下标对应的值 - 另一类查询要求返回数组
nums中索引left和索引right之间( 包含 )的nums元素的 和 ,其中left <= right
实现 NumArray 类:
NumArray(int[] nums)用整数数组nums初始化对象void update(int index, int val)将nums[index]的值 更新 为valint sumRange(int left, int right)返回数组nums中索引left和索引right之间( 包含 )的nums元素的 和 (即,nums[left] + nums[left + 1], ..., nums[right])
示例 1:
输入: ["NumArray", "sumRange", "update", "sumRange"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] 输出: [null, 9, null, 8]解释: NumArray numArray = new NumArray([1, 3, 5]); numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9 numArray.update(1, 2); // nums = [1,2,5] numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8
提示:
1 <= nums.length <= 3 * 104-100 <= nums[i] <= 1000 <= index < nums.length-100 <= val <= 1000 <= left <= right < nums.length- 调用
update和sumRange方法次数不大于3 * 104
解题思路:
这题数组的长度为310^4,如果时间复杂度是O(n2),则会超时。所以这题一定不能每次都遍历。
但是我们可以发现一个规律,就是update的时候,影响的范围很小,甚至有可能都对sumRange不产生影响,所以,我们可以把影响范围缩减到最小。
我们可以把nums数组划分为k块,暂且用N1,N2,Nk表示,则left和right会出现2种情况。
left和right属于同一块:这种情况,直接求left和right的累加值即可。
left和right不属于同一块:这种情况,求left到其所属块的尾之间的和,right所属的块的头到right之间的和,以及left和right之间的块的和。三者相加,就是最终值。
代码:
class NumArray {private int[] nums;private int[] pieces;private int pieceLength;public NumArray(int[] nums) {this.nums = nums;pieceLength = (int) Math.ceil(Math.sqrt(nums.length));pieces = new int[nums.length / pieceLength + 1];for (int i = 0; i < nums.length; i++) {pieces[i / pieceLength] = pieces[i / pieceLength] + nums[i];}}public void update(int index, int val) {pieces[index / pieceLength] += (val-nums[index]);nums[index] = val;}public int sumRange(int left, int right) {int piece1 = left / pieceLength;int piece2 = right / pieceLength;int sum1 = 0, sum2 = 0, sum3 = 0;if (piece1 == piece2) {for (int i = left; i <= right; i++) {sum1 += nums[i];}} else {for (int i = left; i < pieceLength * (piece1+1); i++) {sum1 += nums[i];}for (int i = pieceLength * piece2; i <= right; i++) {sum3 += nums[i];}for (int i = piece1 + 1; i < piece2; i++) {sum2 += pieces[i];}}int sum = sum1 + sum2 + sum3;return sum;}}
相关文章:
LeetCode解法汇总307. 区域和检索 - 数组可修改
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 描述: 给你一个数…...
Java源码分析:Guava之不可变集合ImmutableMap的源码分析
原创/朱季谦 一、案例场景 遇到过这样的场景,在定义一个static修饰的Map时,使用了大量的put()方法赋值,就类似这样—— public static final Map<String,String> dayMap new HashMap<>(); static {dayMap.put("Monday&q…...
详解自动化测试之 Selenium
目录 1. 什么是自动化 2.自动化测试的分类 3. selenium(web 自动化测试工具) 1)选择 selenium 的原因 2)环境部署 3)什么是驱动? 4. 一个简单的自动化例子 5.selenium 常用方法 5.1 查找页面元素&…...
vue监听对象属性值变化
一、官方文档 二、实现方法 方法一、直接根据watch来监听 export default {data() {return {object: {username: ,password: }}},watch: {object.username(newVal, oldVal) {console.log(newVal, oldVal)}} }方法二:利用watch和computed来实现监听 利用computed定…...
Unicode编码的emoji表情如何在前端页面展示(未完成)
Unicode编码的emoji表情如何在前端页面展示 一、首先几个定义解决办法 一、首先几个定义 U1F601 和 0x1F601 表示同一个 Unicode 代码点,即笑脸 Emoji 的代码点。它们之间的区别在于表示方式和数据类型。 1.U1F601 是一种常见的表示方式,也称为 “U” 标…...
基于SSM的设备配件管理和设备检修系统
末尾获取源码 开发语言:Java Java开发工具:JDK1.8 后端框架:SSM 前端:Vue 数据库:MySQL5.7和Navicat管理工具结合 服务器:Tomcat8.5 开发软件:IDEA / Eclipse 是否Maven项目:是 目录…...
鸿蒙开发|鸿蒙系统项目开发前的准备工作
文章目录 鸿蒙项目开发的基本流程介绍鸿蒙项目开发和其他项目有什么不同成为华为开发者-注册和实名认证1.登录官方网站 鸿蒙项目开发的基本流程介绍 直接上图,简单易懂! 整个项目的开发通过4个模块进行:开发准备、开发应用、运行调试测试和发…...
Evil靶场
Evil 1.主机发现 使用命令探测存活主机,80.139是kali的地址,所以靶机地址就是80.134 fping -gaq 192.168.80.0/242.端口扫描 开放80,22端口 nmap -Pn -sV -p- -A 192.168.80.1343.信息收集 访问web界面 路径扫描 gobuster dir -u http…...
第77题. 组合
原题链接:第77题. 组合 全代码: class Solution { private:vector<vector<int>> result; // 存放符合条件结果的集合vector<int> path; // 用来存放符合条件结果void backtracking(int n, int k, int startIndex) {if (path.size() …...
读书笔记:彼得·德鲁克《认识管理》第21章 企业与政府
一、章节内容概述 企业社会责任最重要的维度之一是政企关系。无论对于企业的顺利运作,还是对于政府的顺利运作,政企关系都至关重要。然而,重商主义典范和宪政主义典范这两种传统理论越来越不适应社会现实,越来越失效。虽然当前尚…...
C/C++疫情集中隔离 2021年12月电子学会青少年软件编程(C/C++)等级考试一级真题答案解析
目录 C/C疫情集中隔离 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C/C疫情集中隔离 2021年12月 C/C编程等级考试一级编程题 一、题目要求 1、编程实现 A同学12月初从国外回来,按照防疫要…...
052-第三代软件开发-系统监测
第三代软件开发-系统监测 文章目录 第三代软件开发-系统监测项目介绍系统监测 关键字: Qt、 Qml、 cpu、 内存、memory 项目介绍 欢迎来到我们的 QML & C 项目!这个项目结合了 QML(Qt Meta-Object Language)和 C 的强大功…...
向量矩阵范数pytorch
向量矩阵范数pytorch 矩阵按照某个维度求和(dim就是shape数组的下标)1. torch1.1 Tensors一些常用函数 一些安装问题cd进不去不去目录PyTorch里面_表示重写内容 在默认情况下,PyTorch会累积梯度,我们需要清除之前的值 范数是向量或…...
NVIDIA Jetson OTA升级
从 JetPack 4.4 开始,可以使用包管理工具升级到下一个 JetPack 版本。请按照以下步骤执行升级。 1,小版本升级 (如,从 JetPack 4.4 升级到 JetPack 4.4.1) 第一步: sudo apt update 第二步: apt list --upgradable 第三步: sudo apt upgrade更新完之后重新启动即可 …...
【算法】算法题-20231118
这里写目录标题 一、16.17. 连续数列二、合并两个有序数组(力扣88)三、存在重复元素(217)四、有效的字母异位词(242) 一、16.17. 连续数列 简单 给定一个整数数组,找出总和最大的连续数列&…...
某60区块链安全之整数溢出漏洞实战学习记录
区块链安全 文章目录 区块链安全整数溢出漏洞实战实验目的实验环境实验工具实验原理攻击过程分析合约源代码漏洞EXP利用 整数溢出漏洞实战 实验目的 学会使用python3的web3模块 学会以太坊整数溢出漏洞分析及利用 实验环境 Ubuntu18.04操作机 实验工具 python3 实验原理…...
图数据库Neo4J 中文分词查询及全文检索(建立全文索引)
Neo4j的全文索引是基于Lucene实现的,但是Lucene默认情况下只提供了基于英文的分词器,下篇文章我们在讨论中文分词器(IK)的引用,本篇默认基于英文分词来做。我们前边文章就举例说明过,比如我要搜索苹果公司&…...
element-china-area-data使用问题
使用CodeToText报错,下载的时候默认下载最新版本的, 稳定版本5.0.2版本才可以 npm install element-china-area-data5.0.2 -S...
248: vue+openlayers 以静态图片作为底图,并在上面绘制矢量多边形
第248个 点击查看专栏目录 本示例是演示如何在vue+openlayers项目中以静态图片作为底图,并在上面绘制矢量多边形。这里主要通过pixels的坐标作为投射,将静态图片作为底图,然后通过正常的方式在地图上显示多边形。注意的是左下角为[0,0]。 直接复制下面的 vue+openlayers源代…...
thinkphp6(TP6)访问控制器报404(Nginx)
起因: 安装thinphp6后,发现无法访问控制器,直接通过URL访问,就报错404。 错误原因: Nginx不支持URL的 PathInfo。 解决方法: 配置伪静态。 伪静态代码: location / {if (!-e $request_filen…...
JavaSec-RCE
简介 RCE(Remote Code Execution),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...
P3 QT项目----记事本(3.8)
3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
