LeetCode1504. Count Submatrices With All Ones
文章目录
- 一、题目
- 二、题解
一、题目
Given an m x n binary matrix mat, return the number of submatrices that have all ones.
Example 1:
Input: mat = [[1,0,1],[1,1,0],[1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2.
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
Example 2:
Input: mat = [[0,1,1,0],[0,1,1,1],[1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3.
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2.
There are 2 rectangles of side 3x1.
There is 1 rectangle of side 3x2.
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.
Constraints:
1 <= m, n <= 150
mat[i][j] is either 0 or 1.
二、题解
class Solution {
public:int numSubmat(vector<vector<int>>& mat) {int res = 0;int m = mat.size(),n = mat[0].size();vector<int> heights(n,0);for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){heights[j] = mat[i][j] == 0 ? 0 : heights[j] + 1;}res += countFromBottom(heights);}return res;}int countFromBottom(vector<int>& heights){int n = heights.size();int res = 0;stack<int> st;for(int i = 0;i < n;i++){while(!st.empty() && heights[i] <= heights[st.top()]){int cur = st.top();st.pop();if(heights[cur] > heights[i]){int left = st.empty() ? -1 : st.top();int len = i - left - 1;int bottom = max(left == -1 ? 0 : heights[left],heights[i]);res += (heights[cur] - bottom) * len * (len + 1) / 2;}}st.push(i);}while(!st.empty()){int cur = st.top();st.pop();int left = st.empty() ? -1 : st.top();int len = n - left - 1;int bottom = left == -1 ? 0 : heights[left];res += (heights[cur] - bottom) * len * (len + 1) / 2;}return res;}
};
相关文章:
LeetCode1504. Count Submatrices With All Ones
文章目录 一、题目二、题解 一、题目 Given an m x n binary matrix mat, return the number of submatrices that have all ones. Example 1: Input: mat [[1,0,1],[1,1,0],[1,1,0]] Output: 13 Explanation: There are 6 rectangles of side 1x1. There are 2 rectangles…...
(每日持续更新)信息系统项目管理(第四版)(高级项目管理)考试重点整理第8章 项目整合管理(九)
博主2023年11月通过了信息系统项目管理的考试,考试过程中发现考试的内容全部是教材中的内容,非常符合我学习的思路,因此博主想通过该平台把自己学习过程中的经验和教材博主认为重要的知识点分享给大家,希望更多的人能够通过考试&a…...
帕金森早期诊断准确率提高至 90.2%,深圳先进院联合中山一院提出 GSP-GCNs 模型
中山大学附属第一医院&中科大先进院等研究团队,提出了一种深度学习模型——图信号处理-图卷积网络 (GSP-GCNs),利用从涉及声调调节的特定任务中获得的事件相关脑电图数据来诊断帕金森病。 震颤、动作迟缓、表情僵硬……提起帕金森病,多数…...
java servlet果蔬产业监管系统Myeclipse开发mysql数据库web结构java编程计算机网页项目
一、源码特点 java Web果蔬产业监管系统是一套完善的java web信息管理系统 serlvetdaobean mvc 模式开发 ,对理解JSP java编程开发语言有帮助,系统具有完整的源代码和数据库,系统主 要采用B/S模式开发。开发环境为TOMCAT7.0,Myeclipse8.5…...
Flask 入门
1. 关于 Flask Flask诞生于2010年, Armin Ronacher的一个愚人节玩笑。不过现在已经是一个用python语言基于Werkzeug工具箱编写的轻量级web开发框架,它主要面向需求简单,项目周期短的小应用。 Flask本身相当于一个内核,其他几乎所…...
微信小程序Skyline在手机端不渲染的问题之一及其解决方式
问题:电脑端是skyline渲染,手机端是webview渲染?如何解? 开发者工具 当前渲染模式:Skyline 当进行预览时手机端却是: 请注意看轮播图的显示情况 请注意看轮播图的显示情况 请注意看轮播图的显示情况 从轮播图上来看,手机端是webview渲染…...
怎样做好Code Review
Code Review方案 定义 Code Review代码评审是指在软件开发过程中,通过对源代码进行系统性检查的过程。通常的目的是查找各种缺陷,包括代码缺陷、功能实现问题、编码合理性、性能优化等;保证软件总体质量和提高开发者自身水平 code review …...
臻于至善,CodeArts Snap 二维绘图来一套不?
前言 我在体验 华为云的 CodeArts Snap 时,第一个例子就是绘制三角函数图像,功能注释写的也很简单。 业务场景中,有一类就是需要产出各种二维图形的,比如,折线图、散点图、柱状图等。 为了提前积累业务素材…...
STM32学习笔记(二) —— 调试串口
我们在调试程序时,经常会使用串口打印相关的调试信息,但是单片机串口不能直接与 PC 端的 USB 接口通讯,需要用到一个USB转串口的芯片来充当翻译的角色。我们使用的开发板上有这个芯片,所以在打印调试信息的时候直接使用USB线连接开…...
Ubuntu20.0.4下设置frpc开机自启动
目录 一、下载frp 二、解压 三、服务端部署 1.配置 2.运行 三、客户端部署 1、配置 2、后台运行 四、开机启动 1、拷贝frpc.service 2、修改配置 3、启用服务 五、ubuntu20.04使用 rc-local.service设置开机启动 1、建立开机服务添加 [Install] 段 2、授权rc-local.service 3、…...
05 Redis之Benchmark+简单动态字符串SDS+集合的底层实现
3.8 Benchmark Redis安装完毕后会自动安装一个redis-benchmark测试工具,其是一个压力测试工具,用于测试 Redis 的性能。 src目录下可找到该工具 通过 redis-benchmark –help 命令可以查看到其用法 3.8.1 测试1 3.9 简单动态字符串SDS 无论是 Redis …...
【C++】priority_queue优先队列
头文件#include <queue> 优先队列具有队列的所有特性,本质是一个堆实现的,和队列基本操作相同: top 访问队头元素 empty 队列是否为空 size 返回队列内元素个数 push 插入元素到队尾 (并排序) emplace 原地构造一个元素并插入队列 pop 弹出队头元素…...
蓝桥杯---三国游戏
问题描述 小蓝正在玩一款游戏。游戏中魏蜀吴三个国家各自拥有一定数量的士兵 X, Y, Z (一开始可以认为都为 0 )。游戏有 n 个可能会发生的事件,每个事件之 间相互独立且最多只会发生一次,当第 i 个事件发生时会分别让 X, Y, Z 增加 Ai , Bi ,Ci 。…...
设计一个分布式ID
为了保证全局唯一性可以用时间作为区分点一部分,时间尽可能细化,可以精确到毫秒,甚至是微秒和纳秒。如果是分布式系统有多态机器,可以根据机器ID再进行以下区分。如哦机器运行的特别快,1毫秒有大量ID生成,可…...
259:vue+openlayers: 显示海量多边形数据,10ms加载完成
第259个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+openlayers项目中通过WebGLVectorLayerRenderer方式加载海量多边形数据。这里相当于将海量的数据放在同一个层的source中,然后通过webglTile的方式渲染出这一层。 本示例数据为5000个多边形,加载速度超级快。 直接…...
Go Zero微服务个人探究之路(十)实战走通微服务前台请求调用的一套流程model->rpc微服务->apiHTTP调用
前言 Go语言凭借低占用,高并发等优秀特性成为后台编程语言的新星,GoZero框架由七牛云技术副总裁团队编写,目前已经成为Go微服务框架里star数量最多的框架 本文记录讲述笔者一步步走通前台向后台发出请求,后台api调用rpc服务的相…...
K8s 安装部署-Master和Minion(Node)
K8s 安装部署-Master和Minion(Node) 操作系统版本:CentOS 7.4 Master :172.20.26.167 Minion-1:172.20.26.198 Minion-2:172.20.26.210(后增加节点) ETCD:172.20.27.218 先安装部署ETCD y…...
从零学习Linux操作系统 第二十部分 mariadb数据库的管理
一、对于数据库的基本介绍 1.什么是数据库 数据库就是个高级的表格软件 2.常见数据库 Mysql Oracle mongodb db2 sqlite sqlserver … 3.Mysql (SUN -----> Oracle) 4.mariadb (Mysql的一种) 数据库中的常用名词 1.字段 :表格中的表头 2.表 &…...
数据脱敏和数据加密有什么区别
数据脱敏:主要是为了兼顾数据安全与数据使用,采用专业的数据脱敏算法。 数据加密:通过对数据进行编码来保护数据,获取实际值的唯一方法是使用解密密钥解码数据。 数据加密是可逆的,数据脱敏是不可逆的。 处理方法不同 保护内容…...
主流排序算法
冒泡排序(Bubble Sort): 基本思想:通过比较相邻元素的大小,不断交换相邻元素的位置,使得较大的元素逐渐“浮”到数组的最后。时间复杂度:O(n^2)。 选择排序(Selection Sort…...
Visual Paradigm 17.0 团队协作新功能实测:手把手教你用项目模板和文件夹管理提效
Visual Paradigm 17.0 团队协作实战指南:从模板配置到文件夹管理的高效工作流在敏捷开发团队中,项目启动速度和资产管理的规范性往往直接影响整体效率。Visual Paradigm 17.0针对这一痛点推出的团队协作增强功能,特别是服务器端项目模板和文件…...
鸿蒙系统微博应用锁常见问题解答
为微博设置应用锁后,不少用户会有各种疑问:忘记密码怎么办?会不会影响消息推送?能不能只锁定某些功能?应用锁耗电吗?本文将针对这些高频问题逐一解答,帮助您更好地使用鸿蒙系统(Harm…...
智慧树自动刷课助手:3步告别手动操作的学习效率工具
智慧树自动刷课助手:3步告别手动操作的学习效率工具 【免费下载链接】zhihuishu 智慧树刷课插件,自动播放下一集、1.5倍速度、无声 项目地址: https://gitcode.com/gh_mirrors/zh/zhihuishu 还在为智慧树平台的重复刷课操作而烦恼吗?智…...
学术写作创新突破!2026全流程AI论文工具精选指南
2026 年 AI 论文写作工具已进入全流程闭环 学术合规时代,千笔 AI(综合评分 99 分)中文学术场景标杆;Grammarly Academic与Elicit为英文论文写作首选;按需求匹配度 - 数据可信度 - 成本承受力三维模型选型,…...
告别鼠标手!5分钟上手开源鼠标连点器MouseClick,轻松实现自动化点击
告别鼠标手!5分钟上手开源鼠标连点器MouseClick,轻松实现自动化点击 【免费下载链接】MouseClick 🖱️ MouseClick 🖱️ 是一款功能强大的鼠标连点器和管理工具,采用 QT Widget 开发 ,具备跨平台兼容性 。软…...
基于Arduino的智能蓝调节拍器:DIY音乐练习伴侣
1. 项目概述:一个能“演奏”蓝调的低成本节拍器玩乐器的人,对节拍器这东西又爱又恨。它像一位严厉的监工,用单调的“嘀嗒”声强迫你跟上节奏。但你想过没有,这个监工其实可以很有趣?几年前,我在练习蓝调吉他…...
上线前最后一道防线,DeepSeek代码审查如何帮你拦截87%的CVE类缺陷?
更多请点击: https://intelliparadigm.com 第一章:上线前最后一道防线,DeepSeek代码审查如何帮你拦截87%的CVE类缺陷? 在软件交付生命周期末期,传统人工代码审计与通用SAST工具常因误报率高、上下文理解弱而漏检高危漏…...
打不开JupyterLab
因为安装某些依赖导致JupyterLab的依赖被动升级或降级,从而影响了JupyterLab的运行,此时可以SSH登录到实例,然后输入jupyter-lab命令进行确认,如果执行命令报错则说明是此问题,那么可以通过pip install jupyterlab再次…...
Windows Cleaner:终极免费系统清理工具,彻底解决C盘空间不足问题
Windows Cleaner:终极免费系统清理工具,彻底解决C盘空间不足问题 【免费下载链接】WindowsCleaner Windows Cleaner——专治C盘爆红及各种不服! 项目地址: https://gitcode.com/gh_mirrors/wi/WindowsCleaner 你是否经常遇到C盘爆红、…...
【大模型聚合平台深度评测:阿里云百炼 vs 腾讯云 ADP,企业如何选型?】
大模型聚合平台深度评测:阿里云百炼 vs 腾讯云 ADP,企业如何选型? 随着大模型技术的快速发展,越来越多的企业开始将 AI 能力融入到业务流程中。然而,面对市场上众多的大模型产品,企业往往面临着 “选择困难…...
