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;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

招投标系统简介 企业电子招投标采购系统源码之电子招投标系统 —降低企业采购成本 tbms

​功能模块&#xff1a; 待办消息&#xff0c;招标公告&#xff0c;中标公告&#xff0c;信息发布 描述&#xff1a; 全过程数字化采购管理&#xff0c;打造从供应商管理到采购招投标、采购合同、采购执行的全过程数字化管理。通供应商门户具备内外协同的能力&#xff0c;为外…

CSS学习记录(基础笔记)

CSS简介: CSS 指的是层叠样式表* (Cascading Style Sheets)&#xff0c;主要用于设置HTML页面的文字内容&#xff08;字体、大小、对齐方式&#xff09;&#xff0c;图片的外形&#xff08;边框&#xff09; CSS 描述了如何在屏幕、纸张或其他媒体上显示 HTML 元素 CSS 节省…

Pytorch使用VGG16模型进行预测猫狗二分类

目录 1. VGG16 1.1 VGG16 介绍 1.1.1 VGG16 网络的整体结构 1.2 Pytorch使用VGG16进行猫狗二分类实战 1.2.1 数据集准备 1.2.2 构建VGG网络 1.2.3 训练和评估模型 1. VGG16 1.1 VGG16 介绍 深度学习已经在计算机视觉领域取得了巨大的成功&#xff0c;特别是在图像分类任…

ubuntu调整路由顺序

Ubuntu系统跳转路由顺序 1、安装ifmetric sudo apt install ifmetric2、查看路由 route -n3、把Iface下面的eth1调到第一位 sudo ifmetric eth1 0命令中eth1是网卡的名称&#xff0c;更改网卡eth1的跃点数&#xff08;metric值&#xff09;为0&#xff08;数值越小&#xf…

prometheus监控k8s kube-proxy target down

prometheus kube-proxy target down 解决 修改配置 kubectl edit cm/kube-proxy -n kube-systemmetricsBindAddress: "0.0.0.0:10249"删除 kube-proxy pod 使之重启应用配置 kubectl delete pod --force `kubectl get pod -n kube-system |grep kube-proxy|awk {pr…

深度学习Redis(3):主从复制

前言 在前面的两篇文章中&#xff0c;分别介绍Redis内存模型和Redis持久化 在Redis的持久化中曾提到&#xff0c;Redis高可用的方案包括持久化、主从复制&#xff08;及读写分离&#xff09;、哨兵和集群。其中持久化侧重解决的是Redis数据的单机备份问题&#xff08;从内存到…

VR实景导航——开启3D可视化实景导航新体验

数字化时代&#xff0c;我们大家出门在外都是离不开各种导航软件&#xff0c;人们对导航的需求也越来越高&#xff0c;而传统的导航软件由于精度不够&#xff0c;无法满足人们对真实场景的需求&#xff0c;这个时候就需要VR实景导航为我们实景指引目的地的所在。 VR实景导航以其…

使用Kmeans算法完成聚类任务

聚类任务 聚类任务是一种无监督学习任务&#xff0c;其目的是将一组数据点划分成若干个类别或簇&#xff0c;使得同一个簇内的数据点之间的相似度尽可能高&#xff0c;而不同簇之间的相似度尽可能低。聚类算法可以帮助我们发现数据中的内在结构和模式&#xff0c;发现异常点和离…

【Linux】进程信号

文章目录 一、信号入门1. 生活角度的信号2. 技术应用角度的信号3. Linux下常见的信号 二、信号产生1. 终端按键产生信号2. 核心转储3. 通过系统调用向进程发信号4. 软件条件产生信号5. 硬件异常产生信号 三、信号保存1. 信号相关概念及内核中的信号表示2. 信号集操作函数3. sig…

java 定时任务不按照规定时间执行

这里写目录标题 使用异步启动可能出现的问题排查代码中添加的定时任务步骤是否正确排查是否任务阻塞&#xff0c;如果定时任务出现异常阻塞后&#xff0c;将不会在次执行java中多个Scheduled定时器不执行为了让Scheduled效率更高&#xff0c;我们可以通过两种方法将定时任务变成…

OLED拼接屏:在广告牌领域的革命性应用,显示、效果

OLED透明屏是一种新型的显示技术&#xff0c;它具有高亮度、高对比度、快速响应和低功耗等优点&#xff0c;可以在透明的基底上显示图像和视频。 OLED透明屏的出现&#xff0c;为我们的生活带来了许多新的可能性。 首先&#xff0c;OLED透明屏可以应用于智能手机和平板电脑等移…

android kernel移植5-RK3568

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言1.添加开发板默认配置文件前言 前面我们已经学会了移植uboot,其实就是把瑞芯微的关于uboot的一些文件的名字和编译指定的文件改为自己定义的问价和名字,那么接下来的Android kernel其实也是…

快速转换PDF文件: Python和PyMuPDF教程

解决问题 有时候将文档上传Claude2做分析&#xff0c;有大小限制&#xff0c;所以需要切割pdf文档为几个小点的文档&#xff0c;故才有了本文章。 如何用Python和PyMuPDF制作你想要大小的PDF&#xff1f; PDF是一种广泛使用的文件格式&#xff0c;可以在任何设备上查看和打印…

CentOS7.3 安装 docker

亲测、截图 阿里云服务器 文章目录 更新源2345 启动开机自启 更新源 sudo yum update -y2 sudo yum install -y yum-utils device-mapper-persistent-data lvm23 sudo yum-config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo4 sudo yum …

如何利用plotly和geopandas根据美国邮政编码(Zip-Code)绘制美国地图

对于我自己来说&#xff0c;该需求源自于分析Movielens-1m数据集的用户数据&#xff1a; UserID::Gender::Age::Occupation::Zip-code 1::F::1::10::48067 2::M::56::16::70072 3::M::25::15::55117 4::M::45::7::02460 5::M::25::20::55455 6::F::50::9::55117我希望根据Zip-…

自动化测试po模式是什么

一、什么是PO模式 全称&#xff1a;page object model 简称&#xff1a;POM/PO PO模式最核心的思想是分层&#xff0c;实现松耦合&#xff01;实现脚本重复使用&#xff0c;实现脚本易维护性&#xff01; 主要分三层&#xff1a; 1.基础层BasePage&#xff1a;封装一些最基…

elasticsearch使用

elasticsearch使用 简介 elasticsearch是一种开源的搜索引擎&#xff0c;可以从海量数据中快速找到需要的内容。 elastic stack&#xff08;ELK)&#xff1a;以ES为核心的技术栈 elasticsearch结合kibana、Logstash、Beats,也就是elastic stack&#xff08;ELK)。被广泛应用…

Blazor第三方组件库推荐:BootstrapBlazor UI

文章目录 前言资源适合人群如何开始环境配置开始新项目Server和Wasm的区别.NET CORE 不支持 7.0运行结果 使用组件发布项目配置到IIS里面 样式问题 前言 Blazor是C#全栈追求极致开发速度的一个前后端不分离的框架&#xff0c;上限是在Winform,WPF,MAUI等宿主环境上面运行的全平…

【iOS】json数据解析以及简单的网络数据请求

文章目录 前言一、json数据解析二、简单的网络数据请求三、实现访问API得到网络数据总结 前言 近期写完了暑假最后一个任务——天气预报&#xff0c;在里面用到了简单的网络数据请求以及json数据的解析&#xff0c;特此记录博客总结 一、json数据解析 JSON是一种轻量级的数据…

flutter 导出iOS问题2

问题1:The Swift pod FirebaseCoreInternal depends upon GoogleUtilities, which does not define modules. To opt into those targets generating module maps (which is necessary to import them from Swift when building as static libraries) 参考 正如上图报错第三方…