LeetCode-Java:303、304区域检索(前缀和)

文章目录

    • 题目
      • 303、区域和检索(数组不可变)
      • 304、二维区域和检索(矩阵不可变)
      • ①303,一维前缀和
      • ②304,二维前缀和
    • 算法
      • 前缀和
        • 一维前缀和
        • 二维前缀和

题目

303、区域和检索(数组不可变)

给定一个整数数组 nums,处理以下类型的多个查询:

  1. 计算索引 leftright (包含 leftright)之间的 nums 元素的 ,其中 left <= right

实现 NumArray 类:

  • NumArray(int[] nums) 使用数组 nums 初始化对象
  • int sumRange(int i, int j) 返回数组 nums 中索引 leftright 之间的元素的 总和 ,包含 leftright 两点(也就是 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))

304、二维区域和检索(矩阵不可变)

给定一个二维矩阵 matrix,以下类型的多个请求:

  • 计算其子矩形范围内元素的总和,该子矩阵的 左上角(row1, col1)右下角(row2, col2)

实现 NumMatrix 类:

  • NumMatrix(int[][] matrix) 给定整数矩阵 matrix 进行初始化
  • int sumRegion(int row1, int col1, int row2, int col2) 返回 左上角 (row1, col1)右下角 (row2, col2) 所描述的子矩阵的元素 总和

示例 1:

在这里插入图片描述

输入: 
["NumMatrix","sumRegion","sumRegion","sumRegion"]
[[[[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]],[2,1,4,3],[1,1,2,2],[1,2,2,4]]
输出: 
[null, 8, 11, 12]

解释:
NumMatrix numMatrix = new NumMatrix([[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (红色矩形框的元素总和)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (绿色矩形框的元素总和)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (蓝色矩形框的元素总和)

①303,一维前缀和

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int len=nums.length;
        int[] answer=new int[len];
        answer[0]=1;
        for(int i=1;i<len;i++){
            answer[i]=nums[i-1]*answer[i-1];
        }
        int R=nums[len-1]; // R存储右侧所有元素乘积
        for (int i = len - 2; i >= 0; i--) {
            answer[i] = answer[i] * R;
            R=R*nums[i];
        }
        return answer;
    }
}

②304,二维前缀和

class NumMatrix {
    int[][] sum;
    public NumMatrix(int[][] matrix) {
        int m=matrix.length,n=matrix[0].length;
        sum=new int[m+1][n+1];
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+matrix[i-1][j-1];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2+1][col2+1]-sum[row1][col2+1]-sum[row2+1][col1]+sum[row1][col1];
    }
}

算法

前缀和

前缀和是一种常见的算法技巧,用于快速计算数组中某个区间内元素的和,通常用于优化处理大量的区间求和问题,比如给定一个数组,询问其中某个连续区间内元素的和。

算法原理: 前缀和的核心思想是通过对数组进行预处理,计算出从数组开头到每个位置的元素累加和,然后利用这些预先计算好的累加和,在O(1)时间内求出任意区间的和。假设给定数组为A,其前缀和数组为prefix,其中prefix[i]表示数组A从0到i的元素和。

一维前缀和

假设给定数组为A = [1, 2, 3, 4, 5],其前缀和数组为prefix = [1, 3, 6, 10, 15]。

但在①②中,A数组的前缀和应当为prefix = [0,1, 3, 6, 10, 15],比原数组要多一个。

在计算任意区间的和时,通过在前缀和数组中添加0,可以统一处理起始位置为0的边界情况,无需单独考虑。例如,对于查询区间[0, 3],直接使用prefix[3]即可得到结果,无需特殊处理。

具体使用的时候建议用草稿纸绘制相关的数组或者矩阵的图形,进行检验。

二维前缀和

二维的前缀和更为复杂,

A = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]

prefix = [ [1, 3, 6], [5, 12, 21], [12, 27, 45] ]

prefix[i] [j] = A[i] [j] + prefix[i-1] [j] + prefix[i] [j-1] - prefix[i-1] [j-1]

可以用下图帮助理解(图源LeetCode:负雪明烛):

至于输出的公式,也类似于上面的用右下角位置加上左上角-1的位置减去区域右上角和左下角:

area=sum[row2+1] [col2+1]-sum[row1] [col2+1]-sum[row2+1] [col1]+sum[row1] [col1](为了方便书写代码,实际矩阵比原矩阵大一圈,所以这里所有的加减都在原矩阵基础上+1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/540288.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

一些 VLP 下游任务的相关探索

一、Image-Text Retrieval (ITR , 图像文本检索) 任务目的&#xff1a; 检索与给定文本最匹配的图像&#xff0c;或者给定图像最匹配的文本。 跨模态图像-文本检索&#xff08;ITR&#xff09;是根据用户给定的一种模态中的表达&#xff0c;从另一模态中检索出相关样本&#x…

工厂方法模式:解锁灵活的对象创建策略

在软件设计中&#xff0c;工厂方法模式是一种非常实用的创建型设计模式&#xff0c;它不仅提升了系统的灵活性&#xff0c;还简化了对象的创建过程。本文将详细探讨工厂方法模式的核心概念、实现方式、应用场景以及与其他设计模式的对比&#xff0c;旨在提供一份全面且实用的指…

flutter中鼠标检测事件的应用---主要在于网页端使用

flutter中鼠标检测事件的应用—主要在于网页端使用 鼠标放上去 主要代码 import package:flutter/material.dart;class CustomStack extends StatefulWidget {override_CustomStack createState() > _CustomStack(); }class _CustomStack extends State<CustomStack>…

MySQL——创建和插入

一、插入数据 INSERT 使用建议; 在任何情况下建议列出列名&#xff0c;在 VALUES 中插入值时&#xff0c;注意值和列的意义对应关系 values 指定的值顺序非常重要&#xff0c;决定了值是否被保存到正确的列中 在指定了列名的情况下&#xff0c;你可以仅对需要插入的列给到…

C++——StackQueue

目录 一Stack 1介绍 2接口 3模拟实现 4栈的oj题 二Queue 1介绍 2接口 3模拟实现 三容器适配器 1再谈栈和队列 四优先级队列 1接口 ​编辑 2仿函数 五dequeue的简单介绍 一Stack 1介绍 先来看看库中对栈的介绍&#xff1a; 1. stack是一种容器适配器&#x…

自养号测评技术:如何快速提高亚马逊、速卖通、沃尔玛新号的权重?

亚马逊平台高度关注买家账号权重&#xff0c;对于希望快速提升listing曝光与销量的卖家而言&#xff0c;拥有高权重买家账号进行下单至关重要。前提是&#xff0c;确保您的listing已经过精细优化。当前&#xff0c;市场上存在众多自养号服务商&#xff0c;然而由于多种原因&…

外汇兑换问题的最优子结构分析

外汇兑换问题的最优子结构分析 一、 当所有交易佣金为零时1.1 伪代码示例&#xff1a;1.2 C代码示例 二、 佣金不为零时的最优子结构性质三、 结论 在考虑外汇兑换问题时&#xff0c;我们面临的是如何通过一系列兑换操作&#xff0c;以最小的成本将一种货币转换为另一种货币。这…

网络变压器(网络隔离变压器)是如何影响网通设备的传输速率的呢?

Hqst华轩盛(石门盈盛)电子导读&#xff1a;今天介绍网络变压器&#xff08;网络隔离变压器/网络滤波器&#xff09;是如何影响网通设备的传输速率的 一、网络变压器&#xff08;网络隔离变压器/网络滤波器&#xff09;的工作原理 网络变压器&#xff08;网络隔离变压器/网络滤…

Docker 学习笔记(六):挑战容器数据卷技术一文通,实战多个 MySQL 数据同步,能懂会用,初学必备

一、前言 记录时间 [2024-4-11] 系列文章简摘&#xff1a; Docker学习笔记&#xff08;二&#xff09;&#xff1a;在Linux中部署Docker&#xff08;Centos7下安装docker、环境配置&#xff0c;以及镜像简单使用&#xff09; Docker 学习笔记&#xff08;三&#xff09;&#x…

arm-linux-gnueabihf-gcc默认目录

默认编译的头文件目录&#xff1a; /usr/local/arm/gcc-linaro-4.9.4-2017.01-x86_64_arm-linux-gnueabihf/arm-linux-gnueabihf/lib 默认编译的库文件目录&#xff1a; /usr/local/arm/gcc-linaro-4.9.4-2017.01-x86_64_arm-linux-gnueabihf/arm-linux-gnueabihf/include/ …

校招生如何准备软件测试、测试开发岗位的面试?

校招生如何准备软件测试、测试开发岗位的面试&#xff1f; 求职建议 大家都很困惑如何学习测试&#xff1f;如何准备测试方面的面试&#xff1f; 我有朋友是做研发的&#xff0c;他认为测试不用准备&#xff0c;直接用开发的简历就行。也有人认为要学习一些测试理论&#xf…

使用 create-vue 脚手架工具创建一个基于 Vite 的项目,并包含加入 Vue Router 等可选项

如果你打算启动一个新项目&#xff0c;你可能会发现使用 create-vue 这个脚手架工具更容易&#xff0c;它能创建一个基于 Vite 的项目&#xff0c;并包含加入 Vue Router 的选项&#xff0c;指令如下&#xff1a; // npm npm create vuelatest// yarn yarn create vue// pnpm …

HTML、CSS --javaweb学习笔记

记录一些重要的知识点 CSS引入方式 行内样式&#xff1a;<h1 style"...">内嵌样式&#xff1a;<style>…</style>外联样式&#xff1a;xxx.css <link href"..."> 颜色表示 关键字&#xff1a;red、green.......rgb表示法&…

java快速构建飞书API消息推送、消息加急等功能

文章目录 飞书机器人自定义机器人自定义应用机器人 自定义应用发送消息普通文本 text富文本 post图片 image文件 file语音 audio视频 media消息卡片 interactive分享群名片 share_chat分享个人名片 share_user 批量发送消息消息加急发送应用内加急发送短信加急 发送电话加急spr…

【随身wifi京东金榜排名】格行vs华为vs上赞随身wifi哪款最好用?格行随身wifi官方正品,格行随身wifi怎么样?

第一名&#xff1a;格行随身wifi 综合分99.1 随身WiFi行业领跑品牌 &#xff0c;15年行业经验 &#xff0c;随身WiFi口碑榜第一名。轻便小巧&#xff0c;支持三网通&#xff0c;可以随时随地提供稳定高速的网络连接。使用目前先进的马维尔芯片&#xff0c;信号稳定&#xff0…

Unet++(pytorch实现)

Unet++网络 Dense connection Unet++继承了Unet的结构,同时又借鉴了DenseNet的稠密连接方式(图1中各种分支)。 作者通过各层之间的稠密连接,互相连接起来,就像Denset那样,前前后后每一个模块互相作用,每一个模块都能看到彼此,那对彼此互相熟悉,分割效果自然就会变好…

位像素海外仓管理系统对接ERP系统教程,一对一教学

在海外仓管理过程中&#xff0c;对接ERP系统的重要性不言而喻的。这种对接不仅能让数据实时共享&#xff0c;还能让海外仓管理者优化整个供应链管理流程。 因此&#xff0c;今天小编就来教大家&#xff0c;海外仓仓库系统是怎么对接ERP物流系统的&#xff1f; 1.分析需求 在对接…

2024年危险化学品经营单位安全管理人员证考试题库及试题解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2024年危险化学品经营单位安全管理人员证考试题库及危险化学品经营单位安全管理人员试题解析是安全生产模拟考试一点通结合&#xff08;安监局&#xff09;特种作业人员操作证考试大纲和&#xff08;质检局&#xff0…

Docker 镜像推送到docker hub

查看容器 #sudo docker ps -a commit容器为镜像 $ sudo docker commit d7b5e8d56a75 ubuntu_pytorch39_v4 #sha256: ********** 查看镜像信息 $ sudo docker images 登录 docker hub $ sudo docker login --username用户名 registry.cn-beijing.aliyuncs.com #密码 为…

2024年mathorcup数学建模思路及论文助攻

题目C题 物流网络分拣中心货量预测及人员排班 电商物流网络在订单履约中由多个环节组成&#xff0c;图1是一个简化的物流网络示意图。其中&#xff0c;分拣中心作为网络的中间环节&#xff0c;需要将包裹按照不同流向进行分拣并发往下一个场地&#xff0c;最终使包裹到达消费者…