【LeetCode每日一题】二维前缀和基本概念与案例
二维前缀和
根据某个块块 的 左上角坐标,和右下角坐标 求出 块块的累加和。

304. 二维区域和检索 - 矩阵不可变
/*** @param {number[][]} matrix*/
var NumMatrix = function(matrix) {let row = matrix.length;let col = matrix[0].length;// 初始化一个二维数组,用来存储每个位置的累加和。let sum = new Array(row+1).fill(0);for(let i = 0; i < sum.length; i++){sum[i] = new Array(col+1).fill(0);}for(let i = 1; i <= row; i++){for(let j = 1; j <= col; j++){sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + matrix[i-1][j-1];}}this.sum = sum;
};/** * @param {number} row1 * @param {number} col1 * @param {number} row2 * @param {number} col2* @return {number}*/
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {return this.sum[row2+1][col2+1] - this.sum[row1][col2+1] - this.sum[row2+1][col1] + this.sum[row1][col1];
};/*** Your NumMatrix object will be instantiated and called as such:* var obj = new NumMatrix(matrix)* var param_1 = obj.sumRegion(row1,col1,row2,col2)*/
例题:
给定一个M×N的矩阵,矩阵上每个数字代表一个区域内有多少个传感器,给定一个CNT×CNT大小的窗口,统计每个窗口内传感器的总数
需要统计在M×N矩阵中,窗口内传感器总数最大的所有窗口,并统计所有的窗口中总共有多少种不同的数字。
- 遍历一次二维数组,记录二维数组的前缀和。记录为preSum
- 遍历preSum,从 i :cnt → len,j:cnt → len ,计算每个小窗口的区间和。记录为cntSum
- 最后遍历cntSum数组,找到最大的窗口,并且用set记录窗口的数字总量。
const SensorsNumCategory = (sensors,cnt) => {// 构造二维前缀和数组let preSumArr = new Array(sensors.length+1);let len = sensors[0].length;for(let i = 0; i < sensors.length+1; i++){preSumArr[i] = new Array(len+1).fill(0);}for(let i = 1; i < preSumArr.length; i++){for(let j = 1;j < preSumArr[i].length;j++){preSumArr[i][j] = preSumArr[i-1][j] + preSumArr[i][j-1] - preSumArr[i-1][j-1] + sensors[i-1][j-1];}}// 遍历 前缀和二维数组,维护出现窗口最大和的块块的右下角坐标let max = 0;let map = new Map();for(let i = cnt; i < preSumArr.length; i++){for(let j = cnt; j < preSumArr[i].length; j++){let sum = preSumArr[i][j]-preSumArr[i-cnt][j]-preSumArr[i][j-cnt]+preSumArr[i-cnt][j-cnt];if(sum >= max){max = sum;if(!map.has(max)){map.set(max,[])}map.get(max).push([i,j])}}}let arr = map.get(max);let res = [];for(let i = 0; i < arr.length; i++){[x,y] = arr[i];res.push(...getElem([x-cnt,y-cnt],cnt,sensors));}// 对数组元素进行去重return Array.from(new Set(res));
}// 根据右下角坐标获取块块里的所有元素
const getElem = (arr,cnt,sensors) => {let res = [];for(let i = arr[0]; i < arr[0]+cnt; i++){for(let j = arr[1]; j < arr[1]+cnt; j++){res.push(sensors[i][j])}}return res;
}
console.log(SensorsNumCategory([[1,3,4], [3,2,5],[1,6,1]],2))
相关文章:
【LeetCode每日一题】二维前缀和基本概念与案例
二维前缀和 根据某个块块 的 左上角坐标,和右下角坐标 求出 块块的累加和。 304. 二维区域和检索 - 矩阵不可变 /*** param {number[][]} matrix*/ var NumMatrix function(matrix) {let row matrix.length;let col matrix[0].length;// 初始化一个二维数组&am…...
计算机网络——网络安全
计算机网络——网络安全 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家, [跳转到网站](https://www.captainbed.cn/qianqiu) 小程一言专栏链接: [link](http://t.csdnimg.cn/ZUTXU) 网络安全何…...
SQl 注入 - 利用报错函数updatexml及extracevalue
环境准备:构建完善的安全渗透测试环境:推荐工具、资源和下载链接_渗透测试靶机下载-CSDN博客 一、updatexml() 函数 1. 使用前提: 在 MySQL 高版本中(大于5.1版本)添加了对 XML 文档进行查询和修改的函数,包括 updatexml() 和 extractvalue()。 2. 显示错误处理: 在…...
ChatGPT高效提问—prompt实践(生成VBA)
ChatGPT高效提问—prompt实践(生成VBA) 2. 生成VBA函数操作Excel 当前Excel表格数据无背景颜色,区分不明显。假如我们想美化数据展示效果,把标题行设置为浅蓝色,其余奇数行设置为橙色,该怎么操作呢?这次我们基于ChatGPT写一个prompt来创建VBA函数。 输入prompt…...
Ps:直接从图层生成文件(图像资源)
通过Ps菜单:文件/导出/将图层导出到文件 Layers to Files命令,我们可以快速地将当前文档中的每个图层导出为同一类型、相同大小和选项的独立文件。 Photoshop 还提供了一个功能,可以基于文档中的图层或图层组的名称,自动生成指定大…...
springboot-接入ai机器人 汇总
鱼聪明 Java SDKGitHub - liyupi/yucongming-java-sdk: 鱼聪明 AI 的 Java SDK,几行代码使用 AI 助手能力!...
蓝桥杯嵌入式第9届真题(完成) STM32G431
蓝桥杯嵌入式第9届真题(完成) STM32G431 题目 分析和代码 main.h /* USER CODE BEGIN Header */ /********************************************************************************* file : main.h* brief : Header for main.c file.* …...
电商小程序03登录页面开发
目录 1 创建应用2 创建页面3 首页功能搭建4 登录页搭建5 设置叠加效果总结 小程序开发在经过需求分析和数据源设计之后,就可以进入到页面开发的阶段了。首先我们需要开发登录的功能。 登录功能要求用户输入用户名和密码,勾选同意用户协议和隐私协议&…...
聊聊PowerJob的CleanService
序 本文主要研究一下PowerJob的CleanService CleanService Slf4j Service public class CleanService {private final DFsService dFsService;private final InstanceInfoRepository instanceInfoRepository;private final WorkflowInstanceInfoRepository workflowInstance…...
Qt QML学习(一):Qt Quick 与 QML 简介
参考引用 QML和Qt Quick快速入门全面认识 Qt Widgets、QML、Qt Quick 1. Qt Widgets、QML、Qt Quick 区别 1.1 QML 和 Qt Quick 是什么关系? 1.1.1 从概念上区分 QML 是一种用户界面规范和标记语言,它允许开发人员创建高性能、流畅的动画和具有视觉吸引…...
Kylin系统下Qt的各种中文问题解决思路
一、编译生成的程序运行,中文乱码 这个比较简单。 Windows下基本就是编码格式设置。ini中文问题,见QSettings读取ini中文key方法。 其他Linux版本没玩过,不清楚。Kylin系统下基本就是缺中文的字库。找个好的中文字库,放到目录下即可,系统目录/usr/lib/fonts,qt的安装目…...
C 练习实例69-约瑟夫环
题目:有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。 代码: #include <stdio.h> int main() {int n8;int table[n]…...
【Qt Design】界面介绍
文章目录 前言Widget Box(工具箱)对象查看器Qt Design属性编译器sizePolicy内容 信号/槽编辑器资源浏览器ui文件编辑完窗口后查看代码在Pycharm中添加QtDesign 前言 Widget Box(工具箱) 提供很多控件 对象查看器 对象查看区域…...
Makefile编译原理 make 中的路径搜索_1
一.make中的路径搜索 问题:在实际的工程项目中,所有的源文件和头文件都放在同一个文件夹中吗? 实验1 : VPATH 引子 mhrubuntu:~/work/makefile1/17$ ll total 28 drwxrwxr-x 4 mhr mhr 4096 Apr 22 00:46 ./ drwxrwxr-x 7 mhr m…...
蓝桥杯每日一题------背包问题(一)
点击可观看配套视频讲解 背包问题 阅读小提示:这篇文章稍微有点长,希望可以对背包问题进行系统详细的讲解,在看的过程中如果有任何疑问请在评论区里指出。因为篇幅过长也可以进行选择性阅读,读取自己想要的那一部分即可。 前言…...
面试 JavaScript 框架八股文十问十答第八期
面试 JavaScript 框架八股文十问十答第八期 作者:程序员小白条,个人博客 相信看了本文后,对你的面试是有一定帮助的!关注专栏后就能收到持续更新! ⭐点赞⭐收藏⭐不迷路!⭐ 1)实现call、apply…...
【机器学习】单变量线性回归
文章目录 线性回归模型(linear regression model)损失/代价函数(cost function)——均方误差(mean squared error)梯度下降算法(gradient descent algorithm)参数(parame…...
《计算思维导论》笔记:10.4 关系模型-关系运算
《大学计算机—计算思维导论》(战德臣 哈尔滨工业大学) 《10.4 关系模型-关系运算》 一、引言 本章介绍数据库的基本数据模型:关系模型-关系运算。 二、什么是关系运算 在数据库理论中,关系运算(Relational Operatio…...
QT+OSG/osgEarth编译之八十四:osgdb_osg+Qt编译(一套代码、一套框架,跨平台编译,版本:OSG-3.6.5插件库osgdb_osg)
文章目录 一、osgdb_osg介绍二、文件分析三、pro文件四、编译实践一、osgdb_osg介绍 osgDB是OpenSceneGraph(OSG)库中的一个模块,用于加载和保存3D场景数据。osgDB_osg是osgDB模块中的一个插件,它提供了对OSG格式的支持。 OSG格式是OpenSceneGraph库使用的一种二进制文件…...
【Redis快速入门】初识Redis、Redis安装、图形化界面
个人名片: 🐼作者简介:一名大三在校生,喜欢AI编程🎋 🐻❄️个人主页🥇:落798. 🐼个人WeChat:hmmwx53 🕊️系列专栏:🖼️…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
Leetcode 3577. Count the Number of Computer Unlocking Permutations
Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接:3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯,要想要能够将所有的电脑解锁&#x…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
unix/linux,sudo,其发展历程详细时间线、由来、历史背景
sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...
七、数据库的完整性
七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
