力扣1504.统计全1子矩形

2024-06-22 20:04
文章标签 统计 力扣 矩形 1504

本文主要是介绍力扣1504.统计全1子矩形,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

力扣1504.统计全1子矩形

  • 开一个二维数组存每个点从它本身开始向左有多少连续的1

    • 遍历矩形右下角(i,j) 再遍历行k in i
    • 每一行的矩形数量 minx = min(minx,left(k,j))
  •   class Solution {public:int numSubmat(vector<vector<int>>& mat) {int n = mat.size();int m = mat[0].size();vector<vector<int>> left(n,vector<int>(m));int cnt=0;for(int i=0;i<n;i++){cnt = 0;for(int j=0;j<m;j++){if(mat[i][j] == 1) cnt ++;else cnt = 0;left[i][j] = cnt;}}int res=0,minx;for(int i=0;i<n;i++){for(int j=0;j<m;j++){minx = INT_MAX;for(int k=i;k>=0;k--){minx = min(minx,left[k][j]);res += minx;}}}return res;}};
    

这篇关于力扣1504.统计全1子矩形的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1085274

相关文章

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

两数之和--力扣1

两数之和 题目思路C++代码 题目 思路 根据题目要求,元素不能重复且不需要排序,我们这里使用哈希表unordered_map。注意题目说了只对应一种答案。 所以我们在循环中,使用目标值减去当前循环的nums[i],得到差值,如果我们在map中能够找到这个差值,就说明存在两个整数的和为目标值。 如果没有找到,就将当前循环的nums[i]以及下标i放入map中,以便后续查

Python脚本:TXT文档行数统计

count = 0 #计数变量file_dirs = input('请输入您要统计的文件根路径:')filename = open(file_dirs,'r') #以只读方式打开文件file_contents = filename.read() #读取文档内容到file_contentsfor file_content in file_contents:

力扣第347题 前K个高频元素

前言 记录一下刷题历程 力扣第347题 前K个高频元素 前K个高频元素 原题目: 分析 我们首先使用哈希表来统计数字出现的频率,然后我们使用一个桶排序。我们首先定义一个长度为n+1的数组,对于下图这个示例就是长度为7的数组。为什么需要一个长度为n+1的数组呢?假如说总共有三个数字都为1,那么我们需要把这个1放在数组下标为3的位置,假如说数组长度为n,对于这个例子就是长度为3,那么它的

【Python 千题 —— 算法篇】字符统计

Python 千题持续更新中 …… 脑图地址 👉:⭐https://twilight-fanyi.gitee.io/mind-map/Python千题.html⭐ 题目背景 在编程中,对字符串的字符统计是一个常见任务。这在文本处理、数据分析、词频统计、自然语言处理等领域有广泛应用。无论是统计字母出现的频率,还是分析不同字符类型的数量,字符串字符统计都是非常有用的技术。 字符统