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…...
C++实现分布式网络通信框架RPC(3)--rpc调用端
目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中,我们已经大致实现了rpc服务端的各项功能代…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
css的定位(position)详解:相对定位 绝对定位 固定定位
在 CSS 中,元素的定位通过 position 属性控制,共有 5 种定位模式:static(静态定位)、relative(相对定位)、absolute(绝对定位)、fixed(固定定位)和…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
goreplay
1.github地址 https://github.com/buger/goreplay 2.简单介绍 GoReplay 是一个开源的网络监控工具,可以记录用户的实时流量并将其用于镜像、负载测试、监控和详细分析。 3.出现背景 随着应用程序的增长,测试它所需的工作量也会呈指数级增长。GoRepl…...
