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循环,外循环表示子矩阵的左上角(x1,y1),内循环表示子矩阵的右下角(x2,y2) 两个for循环遍历,计算子矩阵的元素总和 四个变量,暴力破解的时间复杂度为O(…...
elementUi el-radio神奇的:label与label不能设置默认值
问题:最近项目遇到一个奇葩的问题:红框中列表的单选按钮无法根据需求设置默认选中,但是同样是设置开启状态的单选框可以设置默认状态 原因:开始同样是和开启/关闭状态一样也把红框中列表的默认值设置为数字模式,但是由…...
git仓库清理
关于git仓库的清理,主要就是清理git仓库里面的大的二进制文件。网上查了很多教程,很多都是用:git filter-branch.清理仓库中的大文件。 我尝试着本地测试了一下,发现是真慢呀。 方法一、git filter-branch step1:查…...
从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入门基础(二)数组操作
入门基础(二) NumPy是Python中一个重要的数学运算库,它提供了了一组多维数组对象和一组用于操作这些数组的函数。以下是一些NumPy的主要特点: 多维数组对象:NumPy的核心是ndarray对象,它是一个多维数组对…...
【LeetCode每日一题】——1572.矩阵对角线元素的和
文章目录 一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【题目提示】七【解题思路】八【时间频度】九【代码实现】十【提交结果】 一【题目类别】 矩阵 二【题目难度】 简单 三【题目编号】 1572.矩阵对角线元素的和 四【题目描述】 给你一…...
牛客网Verilog刷题——VL55
牛客网Verilog刷题——VL55 题目答案 题目 请用Verilog实现4位约翰逊计数器(扭环形计数器),计数器的循环状态如下: 电路的接口如下图所示: 输入输出描述: 信号类型输入/输出位宽描述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内容 视频教程 定义 调用活动是在一个流程定义中调用另一个独立的流程定义,通常可以定义一些通用的流程作为 这种调用子流程,供其他多个流程定义复用。这种子流…...
java 并发
目录 什么是线程?什么是进程?为什么要有线程?有什么关系与区别?什么是守护线程?如何创建、启动 Java 线程?线程池参数详细解释Callable接口和Future类偏向锁 / 轻量级锁 / 重量级锁synchronized 和 java.ut…...
【MySQL】DDL和DML
4,DDL:操作数据库 我们先来学习DDL来操作数据库。而操作数据库主要就是对数据库的增删查操作。 4.1 查询 查询所有的数据库 SHOW DATABASES; 运行上面语句效果如下: 上述查询到的是的这些数据库是mysql安装好自带的数据库,我们以后不要操…...
使用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自定义绘制线段 并且删除指定的已绘制的点位
效果:点击表格可实现选中地图点位,删除按钮点击可删除对应点位并且重新绘制线段,点击确定按钮 保存已经绘制的点位信息传给父组件 并且该组件已实现回显 完整的组件代码如下 文件名称为: leafletMakePointYt <!--* Descripti…...
ChatGPT辅助写论文:提升效率与创造力的利器
写作是人类最重要的交流方式之一,也是学术研究中不可或缺的环节。然而,写作并不是一件容易的事情,尤其是对于科研人员来说,他们需要花费大量的时间和精力来撰写高质量的论文,并且面临着各种各样的挑战,如语…...
面试攻略,Java 基础面试 100 问(六)
JAVA 泛型 泛型提供了编译时类型安全检测机制,该机制允许程序员在编译时检测到非法的类型。泛型的本 质是参数化类型,也就是说所操作的数据类型被指定为一个参数。比如我们要写一个排序方法, 能够对整型数组、字符串数组甚至其他任何类型的…...
Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...
视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
是否存在路径(FIFOBB算法)
题目描述 一个具有 n 个顶点e条边的无向图,该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序,确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数,分别表示n 和 e 的值(1…...
回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
