leetcode304. 二维区域和检索 - 矩阵不可变(java)

前缀和数组

  • 二维区域和检索 - 矩阵不可变
    • 题目描述
    • 前缀和
    • 代码演示
  • 一维数组前缀和

二维区域和检索 - 矩阵不可变

难度 - 中等
原题链接 - 二维区域和检索 - 矩阵不可变

题目描述

给定一个二维矩阵 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 (蓝色矩形框的元素总和)

提示:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
-105 <= matrix[i][j] <= 1e5
0 <= row1 <= row2 < m
0 <= col1 <= col2 < n
最多调用 104 次 sumRegion 方法

在这里插入图片描述

前缀和

和一维数组类似.也是先定义一个前缀和数组,求出前缀和的值,然后调用区间值时,就可以用前缀和进行计算.
注意:前缀和数组下标从1开始.
在这里插入图片描述

代码演示

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

一维数组前缀和

leetcode303. 区域和检索 - 数组不可变

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Java抽象类

Java中的抽象类&#xff08;Abstract Class&#xff09;是一种特殊类型的类&#xff0c;它无法被实例化&#xff0c;只能被用作其他类的基础。抽象类用于定义具有共同特征和行为的一组相关类的共同结构和方法。抽象类可以包含抽象方法&#xff08;没有具体实现的方法&#xff0…

VR防地质灾害安全教育:增强自然灾害知识,提高自我保护意识

VR防地质灾害安全教育系统是一种虚拟仿真技术&#xff0c;可以通过虚拟现实技术模拟地震、泥石流、滑坡等地质灾害的发生和应对过程&#xff0c;帮助人们提高应对突发自然灾害的能力。这种系统的优势在于可以增强自然灾害知识&#xff0c;提高自我保护意识&#xff0c;锻炼人们…

MyBatis分页插件PageHelper的使用及特殊字符的处理

目录 一、PageHelper简介 1.什么是分页 2.PageHelper是什么 3.使用PageHelper的优点 二、PageHelper插件的使用 原生limit查询 1. 导入pom依赖 2. Mybatis.cfg.xml 配置拦截器 3. 使用PageHelper进行分页 三、特殊字符的处理 1.SQL注入&#xff1a; 2.XML转义&#…

一、Kafka概述

目录 1.1 定义1.2 消息队列1、传统消息队列的应用场景2、消息队列的两种模式 1.3 Kafka的基础架构 1.1 定义 Kafka传 统定义&#xff1a;Kafka是一个分布式的基于发布/订阅模式的消息队列&#xff08;Message Queue&#xff09;&#xff0c;主要应用于大数据实时处理领域。 K…

ACL2023 Prompt 相关文章速通 Part 1

Accepted Papers link: ACL2023 main conference accepted papers 文章目录 Accepted PapersPrompter: Zero-shot Adaptive Prefixes for Dialogue State Tracking Domain AdaptationQuery Refinement Prompts for Closed-Book Long-Form QAPrompting Language Models for Lin…

【Redis】什么是缓存击穿,如何预防缓存击穿?

【Redis】什么是缓存击穿&#xff0c;如何预防缓存击穿&#xff1f; 缓存击穿是指一个 Key 非常热点&#xff0c;大并发集中对这一个点进行访问&#xff0c;当这个Key 在失效的瞬间&#xff0c;持续的大并发就会穿破缓存&#xff0c;直接请求数据库。缓存击穿和缓存雪崩的区别…

基于FPGA视频接口之HDMI2.0编/解码

简介 为什么要特别说明HDMI的版本,是因为HDMI的版本众多,代表的HDMI速度同样不同,当前版本在HDMI2.1速度达到48Gbps,可以传输4K及以上图像,但我们当前还停留在1080P@60部分,且使用的芯片和硬件结构有很大差别,故将HDMI分为两个部分说明1080@60以下分辨率和4K以上分辨率(…

【WebSocket】前端使用WebSocket实时通信

目录 前言什么是WebSocketWebSocket的工作原理WebSocket与HTTP的关系HTTP建立持久化连接WebSocket类封装 前言 最近写项目&#xff0c;需要实现消息通知和实时聊天的功能&#xff0c;就去了解了一些关于websocket的知识&#xff0c;总结如下。 什么是WebSocket WebSocket 是一…

vscode C++17便捷配置教程(懒人版)

环境链接 以上是已经配置好的c17环境链接&#xff0c;直接下载解压即可&#xff08;注意文件路径上不要带有中文&#xff09; 下载解压之后按照msys64-mingw64-bin路径打开 然后单击该路径右方空白区域可直接复制路径 然后点击开始菜单搜索“环境变量“并打开&#xff08;如…

SQL阶段性优化

&#x1f61c;作 者&#xff1a;是江迪呀✒️本文关键词&#xff1a;MySQL、SQL优化、阶段性优化☀️每日 一言&#xff1a;我们要把懦弱扼杀在摇篮中。 一、前言 我们在做系统的过程中&#xff0c;难免会遇到页面查询速度慢&#xff0c;性能差的问题&#xff0c;…

数据结构基础:P3-树(上)----编程作业02:List Leaves

本系列文章为浙江大学陈越、何钦铭数据结构学习笔记&#xff0c;系列文章链接如下&#xff1a; 数据结构(陈越、何钦铭)学习笔记 文章目录 一、题目描述二、整体思路与实现代码 一、题目描述 题目描述&#xff1a; 给定一棵树&#xff0c;按照从上到下、从左到右的顺序列出所有…

Compressor For Mac强大视频编辑工具 v4.6.5中文版

Compressor for Mac是苹果公司推出的一款视频压缩工具&#xff0c;可以将高清视频、4K视频、甚至是8K视频压缩成适合网络传输或存储的小文件。Compressor支持多种视频格式&#xff0c;包括H.264、HEVC、ProRes和AVC-Intra等&#xff0c;用户可以根据需要选择不同的压缩格式。 …

ModaHub魔搭社区:WinPlan经营大脑预算编制

目录 WinPlan经营大脑预算编制介绍 WinPlan经营大脑预算编制模版 WinPlan经营大脑预算模版管理 WinPlan经营大脑预算数据录入 WinPlan经营大脑预算编制介绍 预算编制时面向企业经营管理场景,创建各个业务单位的目标,包括销售目标、财务目标、人事目标等,实现各个业务单…

华为OD机试 - 最佳植树距离 - 二分查找(Java 2023 B卷 100分)

目录 一、题目描述二、输入描述三、输出描述四、备注说明五、二分查找六、解题思路七、Java算法源码八、效果展示1、输入2、输出3、说明 一、题目描述 按照环保公司要求&#xff0c;小明需要在沙化严重的地区进行植树防沙工作&#xff0c;初步目标是种植一条直线的树带。 由于…

腾讯云和阿里云服务器折扣对比_看看哪家划算?

阿里云服务器和腾讯云服务器根据购买时长可以享受一定的优惠折扣&#xff0c;综合对比下来腾讯云折扣更低&#xff0c;阿腾云来对比下阿里云和腾讯云的云服务器根据购买时长可以享受的常规折扣对比&#xff1a; 目录 阿里云和腾讯云折扣对比 阿里云服务器常规折扣 腾讯云服…

CentOS KVM虚拟安装和开机启动

1. 配置系统 关闭SELinux setenforce 0持久化关闭配置 vi /etc/selinux/config2. 安装虚拟化软件 安装 KVM、QEMU等虚拟化软件。 yum install qemu-kvm qemu-img virt-manager libvirt virt-install virt-viewer 检查LVM模块是否已经加载 lsmod |grep kvm设置开机启动 s…

C语言:选择+编程(每日一练Day8)

目录 选择题&#xff1a; 题一&#xff1a; 题二&#xff1a; 题三&#xff1a; 题四&#xff1a; 题五&#xff1a; 编程题&#xff1a; 题一&#xff1a;字符个数统计 思路一&#xff1a; 题二&#xff1a;多数元素 思路一&#xff1a; 本人实力有限可能对一些…

JavaScript中的this关键字的作用,以及它如何确定其值

聚沙成塔每天进步一点点 ⭐ 专栏简介⭐ this关键字的作用⭐ this的值取决于执行上下文⭐ 示例⭐ 总结⭐ 写在最后 ⭐ 专栏简介 前端入门之旅&#xff1a;探索Web开发的奇妙世界 记得点击上方或者右侧链接订阅本专栏哦 几何带你启航前端之旅 欢迎来到前端入门之旅&#xff01;这…

1448. 统计二叉树中好节点的数目(C++题解)

1448. 统计二叉树中好节点的数目 给你一棵根为 root 的二叉树&#xff0c;请你返回二叉树中好节点的数目。 「好节点」X 定义为&#xff1a;从根到该节点 X 所经过的节点中&#xff0c;没有任何节点的值大于 X 的值。 示例 1&#xff1a; 输入&#xff1a;root [3,1,4,3,nu…

androidStudio或IDEA的通过gitBash打开插件

本人&#xff0c;一个资深的命令行&#xff0c;业余爱好者。常年直接vim&#xff0c;或者shell上服务器阅读代码。比较偏好使用GitBash来打开项目&#xff0c;进行git status&#xff0c;git diff&#xff0c;git add&#xff0c;commit等动作。 基于以上原因&#xff0c;本人开…