当前位置: 首页 > news >正文

lc1074.元素和为目标值的子矩阵数量

创建二维前缀和数组

两个for循环,外循环表示子矩阵的左上角(x1,y1),内循环表示子矩阵的右下角(x2,y2)

两个for循环遍历,计算子矩阵的元素总和

四个变量,暴力破解的时间复杂度为O(m^2*n^2)(m、n为matrix数组的行数和列数)

优化

计算每一行的前缀和,而不是整个矩阵的前缀和。

取不同的两个列(j1,j2),计算以这两个列为边界计算每一行的前缀和(这就是二维前缀和)

这样就可以减少一个变量遍历,时间复杂度为O(m^2*n)(m、n为matrix数组的行数和列数)

代码

import org.junit.Test;import java.util.HashMap;
import java.util.Map;public class SubmatrixNumber {@Testpublic void test() {int[][] matrix = new int[][]{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};
//        for (int[] arr:getPrefixAnd(matrix)) {
//            for (int i:arr) {
//                System.out.print(i+" ");
//            }
//            System.out.println();
//        }System.out.println(submatrixNumber(matrix, 0));//4int[][] matrix1 = new int[][]{{1, -1}, {-1, 1}};System.out.println(submatrixNumber(matrix1, 0));//5int[][] matrix2 = new int[][]{{904}};System.out.println(submatrixNumber(matrix2, 0));//0}public static int submatrixNumber(int[][] matrix, int target) {int[][] sum = getPrefixAnd1(matrix);int ans = 0;Map<Integer, Integer> count = new HashMap<>();//负责记录计算出的每两列之间的前缀和出现的次数int endY = 1;while (endY <= matrix[0].length) {for (int startY = 0; startY < endY; startY++) {//两个列的边界int prefixAnd = 0;count.clear();//两个列的边界不同,此时计算出的前缀和不同,负责记录的map集合需要初始化count.put(0, 1);//当矩阵为空时,需要记录0出现了1次for (int k = 1; k <= matrix.length; k++) {//遍历行prefixAnd += (sum[k][endY] - sum[k][startY]);//计算以这两个列为边界计算每一行的前缀和if (count.containsKey(prefixAnd - target)) {//count集合中是否存在key值为temp-target的数,即为temp-target这个数是否是第一次出现ans += count.get(prefixAnd - target);//不是第一次,则取value值加上}count.put(prefixAnd, count.getOrDefault(prefixAnd, 0) + 1);//记录次数加一//defaultValue - 当指定的key并不存在映射关系中,则返回的该默认值//即如果是第一次出现,则默认的次数记为0}}endY++;}return ans;}public static int[][] getPrefixAnd(int[][] matrix) {int[][] sum = new int[matrix.length][matrix[0].length];for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (i == 0 && j > 0) {//第一行sum[i][j] = sum[i][j - 1] + matrix[i][j];} else if (j == 0 && i > 0) {sum[i][j] = sum[i - 1][j] + matrix[i][j];} else if (i == 0 && j == 0) {sum[0][0] = matrix[0][0];} else {sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i][j];}}}return sum;}//sum[0][0] == 0public static int[][] getPrefixAnd1(int[][] matrix) {int[][] sum = new int[matrix.length+1][matrix[0].length+1];for (int i = 1; i <= matrix.length; i++) {for (int j = 1; j <= matrix[0].length; j++) {sum[i][j] = sum[i][j - 1] + matrix[i - 1][j - 1];}}return sum;}
}

相关文章:

lc1074.元素和为目标值的子矩阵数量

创建二维前缀和数组 两个for循环&#xff0c;外循环表示子矩阵的左上角&#xff08;x1,y1&#xff09;&#xff0c;内循环表示子矩阵的右下角&#xff08;x2,y2&#xff09; 两个for循环遍历&#xff0c;计算子矩阵的元素总和 四个变量&#xff0c;暴力破解的时间复杂度为O(…...

elementUi el-radio神奇的:label与label不能设置默认值

问题&#xff1a;最近项目遇到一个奇葩的问题&#xff1a;红框中列表的单选按钮无法根据需求设置默认选中&#xff0c;但是同样是设置开启状态的单选框可以设置默认状态 原因&#xff1a;开始同样是和开启/关闭状态一样也把红框中列表的默认值设置为数字模式&#xff0c;但是由…...

git仓库清理

关于git仓库的清理&#xff0c;主要就是清理git仓库里面的大的二进制文件。网上查了很多教程&#xff0c;很多都是用&#xff1a;git filter-branch.清理仓库中的大文件。 我尝试着本地测试了一下&#xff0c;发现是真慢呀。 方法一、git filter-branch step1&#xff1a;查…...

从0到1开发go-tcp框架【3-读写协程分离、引入消息队列、进入连接管理器、引入连接属性】【基础篇完结】

从0到1开发go-tcp框架【3-读写协程分离、引入消息队列、进入连接管理器、引入连接属性】 1 读写协程分离[v0.7] 添加一个Reader和Writer之间通信的channel添加一个Writer goroutineReader由之前直接发送给客户端改为发送给通信channel启动Reader和Writer一起工作 zinx/znet/co…...

python-爬虫作业

# -*- coding:utf-8 -*-Author: 董咚咚 contact: 2648633809qq.com Time: 2023/7/31 17:02 version: 1.0import requests import reimport xlwt from bs4 import BeautifulSoupurl "https://www.dygod.net/html/gndy/dyzz/" hd {user-Agent:Mozilla/4.0 (Windows N…...

vue3+ts+pinia整合websocket

文章目录 一. 目标二. 前置环境三. websocket通用模板 一. 目标 先有实时数据需要展示. 由于设备量极大且要对设备参数实时记录展示.axios空轮询不太适合. 选择websocket长连接通讯. 使用pinia原因是pinia具备共享数据性质.可以作为消息队列缓存数据,降低渲染压力.同时方便多…...

【微信小程序】保存多张图片到本地相册

<template><view class"container"><u-swiper :list"list" circular radius0 indicator indicatorModedot height950rpx></u-swiper><view class"btn btn2" click"saveFun">保存到相册</view><…...

Python Numpy入门基础(二)数组操作

入门基础&#xff08;二&#xff09; NumPy是Python中一个重要的数学运算库&#xff0c;它提供了了一组多维数组对象和一组用于操作这些数组的函数。以下是一些NumPy的主要特点&#xff1a; 多维数组对象&#xff1a;NumPy的核心是ndarray对象&#xff0c;它是一个多维数组对…...

【LeetCode每日一题】——1572.矩阵对角线元素的和

文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 矩阵 二【题目难度】 简单 三【题目编号】 1572.矩阵对角线元素的和 四【题目描述】 给你一…...

牛客网Verilog刷题——VL55

牛客网Verilog刷题——VL55 题目答案 题目 请用Verilog实现4位约翰逊计数器&#xff08;扭环形计数器&#xff09;&#xff0c;计数器的循环状态如下&#xff1a;   电路的接口如下图所示&#xff1a; 输入输出描述&#xff1a; 信号类型输入/输出位宽描述clkwireInput1系统…...

python中数据可视化

1.掷一个D6和一个D10 50000次的结果 die.py from random import randintclass Die:def __init__(self, num_sides6):self.num_sides num_sidesdef roll(self):return randint(1, self.num_sides) die_visual.py from die import Die from plotly.graph_objs import Bar, L…...

DASCTF 2023 0X401七月暑期挑战赛web复现

目录 <1> Web (1) EzFlask(python原型链污染&flask-pin) (2) MyPicDisk(xpath注入&文件名注入) (3) ez_cms(pearcmd文件包含) (4) ez_py(django框架 session处pickle反序列化) <1> Web (1) EzFlask(python原型链污染&flask-pin) 进入题目 得到源…...

go编译文件

1.编译go文件 go build [go文件]2.执行文件编译文件 ./demo [demo为go文件名称]...

Flowable-子流程-调用活动

目录 定义图形标记XML内容界面操作使用示例子流程设计子流程的XML内容主流程设计主流程的XML内容 视频教程 定义 调用活动是在一个流程定义中调用另一个独立的流程定义&#xff0c;通常可以定义一些通用的流程作为 这种调用子流程&#xff0c;供其他多个流程定义复用。这种子流…...

java 并发

目录 什么是线程&#xff1f;什么是进程&#xff1f;为什么要有线程&#xff1f;有什么关系与区别&#xff1f;什么是守护线程&#xff1f;如何创建、启动 Java 线程&#xff1f;线程池参数详细解释Callable接口和Future类偏向锁 / 轻量级锁 / 重量级锁synchronized 和 java.ut…...

【MySQL】DDL和DML

4&#xff0c;DDL:操作数据库 我们先来学习DDL来操作数据库。而操作数据库主要就是对数据库的增删查操作。 4.1 查询 查询所有的数据库 SHOW DATABASES; 运行上面语句效果如下&#xff1a; 上述查询到的是的这些数据库是mysql安装好自带的数据库&#xff0c;我们以后不要操…...

使用python框架FastAPI

中文文档 Python ORM之SQLAlchemy Fastapi大型项目目录规划 SQL数据库操作 依赖项Depends 待看 和APIRouter from sqlalchemy import create_engine from sqlalchemy.ext.declarative import declarative_base from sqlalchemy.orm import sessionmakerapp FastAPI()SQ…...

Vue实现leafletMap自定义绘制线段 并且删除指定的已绘制的点位

效果&#xff1a;点击表格可实现选中地图点位&#xff0c;删除按钮点击可删除对应点位并且重新绘制线段&#xff0c;点击确定按钮 保存已经绘制的点位信息传给父组件 并且该组件已实现回显 完整的组件代码如下 文件名称为&#xff1a; leafletMakePointYt <!--* Descripti…...

ChatGPT辅助写论文:提升效率与创造力的利器

写作是人类最重要的交流方式之一&#xff0c;也是学术研究中不可或缺的环节。然而&#xff0c;写作并不是一件容易的事情&#xff0c;尤其是对于科研人员来说&#xff0c;他们需要花费大量的时间和精力来撰写高质量的论文&#xff0c;并且面临着各种各样的挑战&#xff0c;如语…...

面试攻略,Java 基础面试 100 问(六)

JAVA 泛型 泛型提供了编译时类型安全检测机制&#xff0c;该机制允许程序员在编译时检测到非法的类型。泛型的本 质是参数化类型&#xff0c;也就是说所操作的数据类型被指定为一个参数。比如我们要写一个排序方法&#xff0c; 能够对整型数组、字符串数组甚至其他任何类型的…...

铭豹扩展坞 USB转网口 突然无法识别解决方法

当 USB 转网口扩展坞在一台笔记本上无法识别,但在其他电脑上正常工作时,问题通常出在笔记本自身或其与扩展坞的兼容性上。以下是系统化的定位思路和排查步骤,帮助你快速找到故障原因: 背景: 一个M-pard(铭豹)扩展坞的网卡突然无法识别了,扩展出来的三个USB接口正常。…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

04-初识css

一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

ABAP设计模式之---“简单设计原则(Simple Design)”

“Simple Design”&#xff08;简单设计&#xff09;是软件开发中的一个重要理念&#xff0c;倡导以最简单的方式实现软件功能&#xff0c;以确保代码清晰易懂、易维护&#xff0c;并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计&#xff0c;遵循“让事情保…...

Angular微前端架构:Module Federation + ngx-build-plus (Webpack)

以下是一个完整的 Angular 微前端示例&#xff0c;其中使用的是 Module Federation 和 npx-build-plus 实现了主应用&#xff08;Shell&#xff09;与子应用&#xff08;Remote&#xff09;的集成。 &#x1f6e0;️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...