热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

leetcode[304]RangeSumQuery2DImmutable

Givena2Dmatrixmatrix,findthesumoftheelementsinsidetherectangledefinedbyitsupperleftcorner(

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

技术分享图片
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:

Given matrix = [
[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]
]
sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12

 

Note:


  1. You may assume that the matrix does not change.

  2. There are many calls to sumRegion function.

  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

题目大意:

求解一个矩阵范围内的数字和。

解法:

构造一个二维数组和[sum+1][col+1],sum[i+1][j+1]表示从matrix[0][0]到matrix[i][j]的数字之和。

class NumMatrix {
private int m,n;
int[][] sum;
public NumMatrix(int[][] matrix) {
m=matrix.length;
n=(m==0?0: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];
}
}

  


推荐阅读
  • 在1995年,Simon Plouffe 发现了一种特殊的求和方法来表示某些常数。两年后,Bailey 和 Borwein 在他们的论文中发表了这一发现,这种方法被命名为 Bailey-Borwein-Plouffe (BBP) 公式。该问题要求计算圆周率 π 的第 n 个十六进制数字。 ... [详细]
  • 网络流24题——试题库问题
    题目描述:假设一个试题库中有n道试题。每道试题都标明了所属类别。同一道题可能有多个类别属性。现要从题库中抽取m道题组成试卷。并要求试卷包含指定类型的试题。试设计一个满足要求的组卷算 ... [详细]
  • 二维码的实现与应用
    本文介绍了二维码的基本概念、分类及其优缺点,并详细描述了如何使用Java编程语言结合第三方库(如ZXing和qrcode.jar)来实现二维码的生成与解析。 ... [详细]
  • 本文详细介绍了C++中的构造函数,包括其定义、特点以及如何通过构造函数进行对象的初始化。此外,还探讨了转换构造函数的概念及其在不同情境下的应用,以及如何避免不必要的隐式类型转换。 ... [详细]
  • 本文详细介绍了iOS应用的生命周期,包括各个状态及其转换过程中的关键方法调用。 ... [详细]
  • importjava.io.*;importjava.util.*;publicclass五子棋游戏{staticintm1;staticintn1;staticfinalintS ... [详细]
  • 解决Visual Studio Code中PHP Intelephense误报问题
    PHP作为一种高度灵活的编程语言,其代码结构可能导致Intelephense插件在某些情况下报告不必要的错误或警告。自1.3.3版本起,Intelephense引入了多个配置选项,允许用户根据具体的工作环境和编程风格调整这些诊断信息的显示。 ... [详细]
  • 3DSMAX制作超现实的体育馆模型
    这篇教程是向脚本之家的朋友介绍3DSMAX制作超现实的体育馆模型方法,教程制作出来的体育馆模型非常地不错,不过教程有点难度,需要有一定基础的朋友学习,推荐到脚本之家,喜欢的朋友可 ... [详细]
  • 默认情况下,Git 使用 Nano 编辑器进行提交信息的编辑,但如果您更喜欢使用 Vim,可以通过简单的配置更改来实现这一变化。本文将指导您如何通过修改全局配置文件来设置 Vim 作为默认的 Git 提交编辑器。 ... [详细]
  • 探讨如何在映射文件中处理重复的属性字段,以避免数据操作时出现错误。 ... [详细]
  • 为何Compose与Swarm之后仍有Kubernetes的诞生?
    探讨在已有Compose和Swarm的情况下,Kubernetes是如何以其独特的设计理念和技术优势脱颖而出,成为容器编排领域的领航者。 ... [详细]
  • 本文探讨了程序员这一职业的本质,认为他们是专注于问题解决的专业人士。文章深入分析了他们的日常工作状态、个人品质以及面对挑战时的态度,强调了编程不仅是一项技术活动,更是个人成长和精神修炼的过程。 ... [详细]
  • 本文介绍了如何通过C#语言调用动态链接库(DLL)中的函数来实现IC卡的基本操作,包括初始化设备、设置密码模式、获取设备状态等,并详细展示了将TextBox中的数据写入IC卡的具体实现方法。 ... [详细]
  • 本文将从基础概念入手,详细探讨SpringMVC框架中DispatcherServlet如何通过HandlerMapping进行请求分发,以及其背后的源码实现细节。 ... [详细]
  • Windows操作系统提供了Encrypting File System (EFS)作为内置的数据加密工具,特别适用于对NTFS分区上的文件和文件夹进行加密处理。本文将详细介绍如何使用EFS加密文件夹,以及加密过程中的注意事项。 ... [详细]
author-avatar
轰炸籹厕所744
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有