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 泛型 泛型提供了编译时类型安全检测机制,该机制允许程序员在编译时检测到非法的类型。泛型的本 质是参数化类型,也就是说所操作的数据类型被指定为一个参数。比如我们要写一个排序方法, 能够对整型数组、字符串数组甚至其他任何类型的…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
Linux应用开发之网络套接字编程(实例篇)
服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案
问题描述:iview使用table 中type: "index",分页之后 ,索引还是从1开始,试过绑定后台返回数据的id, 这种方法可行,就是后台返回数据的每个页面id都不完全是按照从1开始的升序,因此百度了下,找到了…...
渲染学进阶内容——模型
最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
镜像里切换为普通用户
如果你登录远程虚拟机默认就是 root 用户,但你不希望用 root 权限运行 ns-3(这是对的,ns3 工具会拒绝 root),你可以按以下方法创建一个 非 root 用户账号 并切换到它运行 ns-3。 一次性解决方案:创建非 roo…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
