【LeetCode每日一题】——304.二维区域和检索-矩阵不可变

文章目录

  • 一【题目类别】
  • 二【题目难度】
  • 三【题目编号】
  • 四【题目描述】
  • 五【题目示例】
  • 六【题目提示】
  • 七【解题思路】
  • 八【时间频度】
  • 九【代码实现】
  • 十【提交结果】

一【题目类别】

  • 矩阵

二【题目难度】

  • 中等

三【题目编号】

  • 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 (蓝色矩形框的元素总和)

六【题目提示】

  • m = = m a t r i x . l e n g t h m == matrix.length m==matrix.length
  • n = = m a t r i x [ i ] . l e n g t h n == matrix[i].length n==matrix[i].length
  • 1 < = m , n < = 200 1 <= m, n <= 200 1<=m,n<=200
  • − 1 0 5 < = m a t r i x [ i ] [ j ] < = 1 0 5 -10^5 <= matrix[i][j] <= 10^5 105<=matrix[i][j]<=105
  • 0 < = r o w 1 < = r o w 2 < m 0 <= row1 <= row2 < m 0<=row1<=row2<m
  • 0 < = c o l 1 < = c o l 2 < n 0 <= col1 <= col2 < n 0<=col1<=col2<n
  • 最多调用 1 0 4 次 s u m R e g i o n 方法 最多调用 10^4 次 sumRegion 方法 最多调用104sumRegion方法

七【解题思路】

  • 利用前缀和的思想
  • 新建一个二维数组,这个二维数组比原来的二维数组多一列,因为二维数组的每个位置都存储了之前元素的和,故多添加的一列就存储了原来二维数组最后一列的元素及之前值的和,我们只需要按照这个规律遍历填充这个新的二维数组即可
  • 对于传入的二维区域,我们只需要逐行的利用前缀和进行计算求和
  • 最后返回结果即可

八【时间频度】

  • 时间复杂度: O ( m n ) O(mn) O(mn) m 、 n m、n mn分别为传入的二维数组的行数和列数
  • 空间复杂度: O ( m n ) O(mn) O(mn) m 、 n m、n mn分别为传入的二维数组的行数和列数

九【代码实现】

  1. Java语言版
class NumMatrix {

    int[][] sums;

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

}
  1. C语言版
typedef struct 
{
    int** sums;
    int sumsSize;
} NumMatrix;


NumMatrix* numMatrixCreate(int** matrix, int matrixSize, int* matrixColSize) 
{
    int m = matrixSize;
    int n = matrixColSize[0];
    NumMatrix* obj = (NumMatrix*)malloc(sizeof(NumMatrix));
    obj->sums = (int**)malloc(sizeof(int*) * m);
    obj->sumsSize = m;
    for(int i = 0;i < m;i++)
    {
        obj->sums[i] = (int*)malloc(sizeof(int) * (n + 1));
    }
    for(int i = 0;i < m;i++)
    {
        for(int j = 0;j < n;j++)
        {
            obj->sums[i][j + 1] = obj->sums[i][j] + matrix[i][j];
        }
    }
    return obj;
}

int numMatrixSumRegion(NumMatrix* obj, int row1, int col1, int row2, int col2) 
{
    int res = 0;
    for(int i = row1;i <= row2;i++)
    {
        res += obj->sums[i][col2 + 1] - obj->sums[i][col1];
    }
    return res;
}

void numMatrixFree(NumMatrix* obj) 
{
    for(int i = 0;i < obj->sumsSize;i++)
    {
        free(obj->sums[i]);
    }
    free(obj);
}
  1. Python语言版
class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m = len(matrix)
        n = len(matrix[0])
        self.sums = [[0] * (n + 1) for _ in range(m)]
        for i in range(0, m):
            for j in range(0, n):
                self.sums[i][j + 1] = self.sums[i][j] + matrix[i][j]

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        res = 0
        for i in range(row1, row2 + 1):
            res += self.sums[i][col2 + 1] - self.sums[i][col1]
        return res
  1. C++语言版
class NumMatrix {
public:
    vector<vector<int>> sums;

    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        sums.resize(m, vector<int>(n + 1));
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                sums[i][j + 1] = sums[i][j] + matrix[i][j];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        int res = 0;
        for(int i = row1;i <= row2;i++){
            res += sums[i][col2 + 1] - sums[i][col1];
        }
        return res;
    }
};

十【提交结果】

  1. Java语言版
    在这里插入图片描述

  2. C语言版
    在这里插入图片描述

  3. Python语言版
    在这里插入图片描述

  4. C++语言版
    在这里插入图片描述

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

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

相关文章

(学习笔记-进程管理)进程

进程 我们编写的代码只是一个存储在硬盘的静态文件&#xff0c;通过编译后会生成二进制可执行文件&#xff0c;当我们运行这个可执行文件后&#xff0c;它会被装载到内存中&#xff0c;接着CPU会执行程序中的每一条指令&#xff0c;那么这个运行中的程序就被称为进程。 现在我…

关于docker的一些深入了解

本文将深入介绍一下docker方面的知识&#xff0c;不尽完全&#xff0c;慢慢完善。 进程 进程的概念 在介绍docker的相关知识前&#xff0c;先了解一下相关概念。进程就是系统中正在运行的程序&#xff0c;进程是操作系统的概念&#xff0c;每当我们执行一个程序时&#xff0…

【unity】Pico VR 开发笔记(视角移动)

【unity】Pico VR 开发笔记&#xff08;视角移动&#xff09; 视角移动是简单的基础功能&#xff0c;这里区别于头显定位获得的小范围位移&#xff0c;是长距离不影响安全边界的位移方式。的常见的位移方式有两种&#xff0c;其一是触发后瞬间传送到指定位置&#xff0c;其次是…

Linux: 设置qmake的Qt版本

Qt开发&#xff0c;qmake会对应一个Qt版本&#xff0c;有时候需要切换这个版本&#xff0c;例如把qmake从Qt5.12切换到Qt5.9, 怎么操作呢&#xff1f; 案例如下&#xff1a; 银河麒麟V10系统&#xff0c;下载安装了Qt5.9.8&#xff0c;但是检查qmake发现它使用的是5.12.8&…

OPC DA 客户端与服务器的那点事

C#开发OPC客户端&#xff0c;使用OPCDAAuto.dll。在开发过程中偶遇小坎坷&#xff0c;主要记录一下问题解决办法。 1、建立客户端&#xff0c;参考链接。建立WinFrom工程&#xff0c;将博客中代码全部复制即可运行&#xff1a; https://www.cnblogs.com/kjgagaga/p/17011730.…

Java阶段五Day19

Java阶段五Day19 问题解析 需求单查询列表功能的bug 业务逻辑&#xff1a; 需要用户登录&#xff0c;师傅入驻&#xff0c;审核入驻通过 查询师傅详情&#xff08;areaIds&#xff0c;categoryIds&#xff09; demand-server-dao-impl 包含持久层实现 requestOrderMappe…

Vue——formcreate表单设计器自定义组件实现(二)

前面我写过一个自定义电子签名的formcreate表单设计器组件&#xff0c;那时初识formcreate各种使用也颇为生疏&#xff0c;不过总算套出了一个组件不是。此次时隔半年又有机会接触formcreate&#xff0c;重新熟悉和领悟了一番各个方法和使用指南。趁热打铁将此次心得再次分享。…

身体原来是一份宝贵的“情绪地图”, 疾病都在教导我们如何与世界相处

当我们生病时 很多时候&#xff0c;是一个契机 让我们来倾听自己内心的压抑的真实 聆听身体的声音 身体能够教会我们如何对待情绪 进而教导我们如何与世界相处 -1- 身体上&#xff0c;有你的情绪地图 皮肤是身体的镜子&#xff0c;身体则是心灵的镜子。生病&#xff0c…

什么是微服务

微服务的架构特征&#xff1a; 单一职责&#xff1a;微服务拆分粒度更小&#xff0c;每一个服务都对应唯一的业务能力&#xff0c;做到单一职责自治&#xff1a;团队独立、技术独立、数据独立&#xff0c;独立部署和交付面向服务&#xff1a;服务提供统一标准的接口&#xff0…

《Java-SE-第二十八章》之CAS

前言 在你立足处深挖下去,就会有泉水涌出!别管蒙昧者们叫嚷:“下边永远是地狱!” 博客主页&#xff1a;KC老衲爱尼姑的博客主页 博主的github&#xff0c;平常所写代码皆在于此 共勉&#xff1a;talk is cheap, show me the code 作者是爪哇岛的新手&#xff0c;水平很有限&…

AI绘图实战(十二):让AI设计LOGO/图标/标识 | Stable Diffusion成为设计师生产力工具

S&#xff1a;AI能取代设计师么&#xff1f; I &#xff1a;至少在设计行业&#xff0c;目前AI扮演的主要角色还是超级工具&#xff0c;要顶替&#xff1f;除非甲方对设计效果无所畏惧~~ 预先学习&#xff1a; 安装及其问题解决参考&#xff1a;《Windows安装Stable Diffusion …

Kali部署dvwa和pikachu靶场

kali换源 进入 vim /etc/apt/sources.list deb https://mirrors.aliyun.com/kali kali-rolling main non-free contrib deb-src https://mirrors.aliyun.com/kali kali-rolling main non-free contrib替换完后更新源 apt-get upadteDVWA靶场环境搭建 使用git从github上把DV…

项目中引用svg图标,公共组件SvgIcon使用,注册全局组件,使用自定义插件注册全局组件

在开发项目的时候经常会用到svg矢量图,而且我们使用SVG以后&#xff0c;页面上加载的不再是图片资源, 这对页面性能来说是个很大的提升&#xff0c;而且我们SVG文件比img要小的很多&#xff0c;放在项目中几乎不占用资源。 1、安装依赖插件 pnpm install vite-plugin-svg-ic…

以产品经理的角度去讲解原型图---会议OA项目

目录 一.前言 二.原型图 2.1 原型图是什么 3.1 原型图的作用 三.演示讲解 3.1 项目背景 3.2 项目介绍 3.2.1 会议管理&#xff08;会议的发起&#xff0c;通知&#xff09; 3.2.2 投票管理&#xff08;会议的流程重大决策记录&#xff09; 3.2.3 会议室管理 3.2.4 系统管…

2023年第三届工业自动化、机器人与控制工程国际会议 | IET独立出版 | EI检索

会议简介 Brief Introduction 2023年第三届工业自动化、机器人与控制工程国际会议&#xff08;IARCE 2023&#xff09; 会议时间&#xff1a;2023年10月27 -30日 召开地点&#xff1a;中国成都 大会官网&#xff1a;www.iarce.org 2023年第三届工业自动化、机器人与控制工程国际…

Android 获取网络连接状态新方法

一. 问题背景 Android12上&#xff0c;有的app模块判断当前网络的类型和连接状态时&#xff0c;还是使用的旧的API&#xff0c;导致返回的结果不准确&#xff0c;影响代码逻辑判断&#xff0c;本篇文章就这一问题&#xff0c;整理一下判断网络类型和连接状态的新方法。 二. 原因…

Selenium上传文件有多少种方式?不信你有我全!

Selenium 封装了现成的文件上传操作。但是随着现代前端框架的发展&#xff0c;文件上传的方式越来越多样。而有一些文件上传的控件&#xff0c;要做自动化控制会更复杂一些&#xff0c;这篇文章主要讨论在复杂情况下&#xff0c;如何通过自动化完成文件上传 input 元素上传文件…

go env 配置(环境变量)说明

前提&#xff1a;已经安装好 golang 可正确的运行下面这段命令&#xff0c;来查看 go 的配置&#xff1a; go env 输出示例&#xff1a; 以上是我本地(windows)环境下输出的配置信息(环境变量) 我们这次就针对每个配置信息进行一个说明&#xff0c;具体到每个字段是什么意思…

前端(十一)——Vue vs. React:两大前端框架的深度对比与分析

&#x1f60a;博主&#xff1a;小猫娃来啦 &#x1f60a;文章核心&#xff1a;Vue vs. React&#xff1a;两大前端框架的深度对比与分析 文章目录 前言概述原理与设计思想算法生态系统与社区支持API与语法性能与优化开发体验与工程化对比总结结语 前言 在当今快速发展的前端领…

iOS——Block回调

先跟着我实现最简单的 Block 回调传参的使用&#xff0c;如果你能举一反三&#xff0c;基本上可以满足了 OC 中的开发需求。已经实现的同学可以跳到下一节。 首先解释一下我们例子要实现什么功能&#xff08;其实是烂大街又最形象的例子&#xff09;&#xff1a; 有两个视图控…