热门标签 | 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];
}
}

  


推荐阅读
  • HDU1176:免费馅饼问题的动态规划解法分析
    题目“免费馅饼”通过动态规划方法进行了解析。该问题的时间限制为 Java 2000ms 和其他语言 1000ms,内存限制为 Java 65536K 和其他语言 32768K。本文详细探讨了如何利用动态规划算法高效求解此问题,并对算法的时间复杂度和空间复杂度进行了深入分析。此外,还提供了具体的实现步骤和代码示例,帮助读者更好地理解和应用这一方法。 ... [详细]
  • 本文全面解析了 gRPC 的基础知识与高级应用,从 helloworld.proto 文件入手,详细阐述了如何定义服务接口。例如,`Greeter` 服务中的 `SayHello` 方法,该方法在客户端和服务器端的消息交互中起到了关键作用。通过实例代码,读者可以深入了解 gRPC 的工作原理及其在实际项目中的应用。 ... [详细]
  • C++入门必备:首个博客知识点汇总
    本文总结了C++初学者需要掌握的关键知识点,特别强调了成员类型的区分。其中,protected成员与private成员在本类中的作用相同,但protected成员允许派生类的成员函数访问,而private成员则不允许。此外,文章还介绍了其他重要的C++基础概念,如类的构造函数、析构函数以及继承机制,为初学者提供了一个全面的学习指南。 ... [详细]
  • 在使用Block时,正确的声明方法和确保线程安全是至关重要的。为了保证Block在堆中分配,应使用`copy`修饰符进行声明,因为栈中的Block与栈的生命周期绑定,容易导致内存问题。此外,还需注意Block捕获外部变量的行为,以避免潜在的循环引用和数据不一致问题。建议深入研究相关文档,以掌握更多高级技巧和最佳实践。 ... [详细]
  • 利用树莓派畅享落网电台音乐体验
    最近重新拾起了闲置已久的树莓派,这台小巧的开发板已经沉寂了半年多。上个月闲暇时间较多,我决定将其重新启用。恰逢落网电台进行了改版,回忆起之前在树莓派论坛上看到有人用它来播放豆瓣音乐,便萌生了同样的想法。通过一番调试,终于实现了在树莓派上流畅播放落网电台音乐的功能,带来了全新的音乐享受体验。 ... [详细]
  • 在处理遗留数据库的映射时,反向工程是一个重要的初始步骤。由于实体模式已经在数据库系统中存在,Hibernate 提供了自动化工具来简化这一过程,帮助开发人员快速生成持久化类和映射文件。通过反向工程,可以显著提高开发效率并减少手动配置的错误。此外,该工具还支持对现有数据库结构进行分析,自动生成符合 Hibernate 规范的配置文件,从而加速项目的启动和开发周期。 ... [详细]
  • 概率与期望动态规划的深入探讨与应用分析
    本文深入探讨了概率与期望动态规划的基本原理及其在实际问题中的应用。概率是指某一事件发生的可能性大小,用P(A)表示。若某一事件的所有可能结果共有n种,且每种结果出现的概率相等,而事件A包含其中的m种结果,则该事件的概率P(A)为m/n。例如,在投掷骰子的情况下,如果事件A定义为掷出偶数点,由于共有3种偶数点(2、4、6),而总共有6种可能的结果,因此P(A)为1/2。文章进一步分析了概率与期望动态规划在复杂场景下的建模方法和求解策略,并通过具体实例展示了其在决策优化和风险管理中的应用价值。 ... [详细]
  • 本文详细介绍了 Windows API 中的按钮控件及其应用实例。主要功能包括:1. `CheckDlgButton` 用于更改对话框中按钮的选中状态;2. `CheckRadioButton` 用于设置单选按钮的选中状态。此外,还探讨了按钮控件在实际开发中的多种应用场景,帮助开发者更好地理解和使用这些功能。 ... [详细]
  • 捕获并处理用户输入数字时的异常,提供详细的错误提示与指导
    在用户输入数字时,程序能够有效捕获并处理各种异常情况,如非法字符或格式错误,并提供详尽的错误提示和操作指导,确保用户能够准确输入有效的数字数据。通过这种方式,不仅提高了程序的健壮性和用户体验,还减少了因输入错误导致的系统故障。具体实现中,使用了Java的异常处理机制,结合Scanner类进行输入读取和验证,确保了输入的合法性和准确性。 ... [详细]
  • VC维在机器学习中的应用与解析
    VC维在机器学习中的应用与解析VC维是指在机器学习中,一个假设空间能够正确分类的最大样本数量。具体而言,如果一个假设空间能够将N个样本以所有可能的 \(2^N\) 种方式完全分开,则称该假设空间具有N的VC维。VC维是衡量模型复杂度的重要指标,对于理解模型的泛化能力和过拟合风险具有重要意义。本文详细探讨了VC维的定义、计算方法及其在机器学习中的应用,并通过实例分析展示了其在模型选择和评估中的关键作用。 ... [详细]
  • 二叉树的直径是指树中任意两个叶节点之间最长路径上的节点数量。本文深入解析了计算二叉树直径的算法,并提出了一种优化方法,以提高计算效率和准确性。通过详细的案例分析和性能对比,展示了该优化算法在实际应用中的优势。 ... [详细]
  • 在Python网络编程中,多线程技术的应用与优化是提升系统性能的关键。线程作为操作系统调度的基本单位,其主要功能是在进程内共享内存空间和资源,实现并行处理任务。当一个进程启动时,操作系统会为其分配内存空间,加载必要的资源和数据,并调度CPU进行执行。每个进程都拥有独立的地址空间,而线程则在此基础上进一步细化了任务的并行处理能力。通过合理设计和优化多线程程序,可以显著提高网络应用的响应速度和处理效率。 ... [详细]
  • CAS 机制下的无锁队列设计与实现 ... [详细]
  • 虚拟机网络设置与数据库远程连接优化指南
    本文针对个人计算机上虚拟机网络配置与数据库远程连接的问题,提供了一套详细的优化指南。在探讨远程数据库访问前,需确保网络配置正确,特别是桥接模式的设置。通过合理的网络配置,可以有效解决因虚拟机或网络问题导致的连接失败,提升远程访问的稳定性和效率。 ... [详细]
  • 采购订单条件类型配置的开发流程详解
    为了满足采购业务的需求,需开发新的价格类型。首先,在SPRO配置中定位到相应的配置节点,创建新的条件类型“ZMM00”。接着,创建定价过程“ZMM003”。具体步骤包括:1. 配置条件类型;2. 设置定价过程。此外,还需确保新条件类型与现有系统中的其他模块兼容,以保证整体业务流程的顺畅运行。 ... [详细]
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社区 版权所有