【力扣:1504】统计全1子矩阵

2023-11-08 17:04
文章标签 统计 力扣 矩阵 1504

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

统计全1子矩阵个数

在这里插入图片描述
思路1:首先考虑深度优先模拟,从【0,0】出发向下、右扩展,符合条件res++,最后输出res,比较直观,但重复进行了大量节点遍历操作,时间复杂度较高,数据量大时会超时

class Solution {unordered_set<int>set;int res=0;void get(vector<vector<int>>& mat,int start_r,int start_c,int row,int col){if(row>=mat.size()||col>=mat[0].size()||set.count(start_r+(start_c+((row+col*151)*151))*151)) return;for(int i=start_r;i<=row;i++){if(!mat[i][col]) return;}for(int i=start_c;i<=col;i++){if(!mat[row][i]) return;}res++;set.insert(start_r+(start_c+((row+col*151)*151))*151);get(mat,start_r,start_c,row+1,col);get(mat,start_r,start_c,row,col+1);}
public:int numSubmat(vector<vector<int>>& mat) {for(int i=0;i<mat.size();i++){for(int j=0;j<mat[0].size();j++){get(mat,i,j,i,j);}}return res;}
};

思路2:单考虑行或列时每增加1个1,结果增加 行或列1个数+1,那么多行多列时每增加一行或一列增加(1+2+…+n)*(m+1),加列时:n为行数,m为原来列数,实际上情景就是第一个图的拓展,只不过矩形中的1实际上是长度相等的全1矩形
在这里插入图片描述

因而仅需要使用一个二维数组tmp存储target[i][j]及前有几个连续的1,然后从上到下加上min(tmp[i][j],tmp_pre_min)即可
在这里插入图片描述

class Solution {
public:int numSubmat(vector<vector<int>>& mat) {int n = mat.size();int m = mat[0].size();vector<vector<int> > row(n, vector<int>(m, 0));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (j == 0) {row[i][j] = mat[i][j];} else if (mat[i][j]) {row[i][j] = row[i][j - 1] + 1;}else {row[i][j] = 0;}}}int ans = 0;for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {int col = row[i][j];for (int k = i; k >= 0 && col; --k) {col = min(col, row[k][j]);ans += col;}}}return ans;}
};

单调栈优化后代码:

class Solution {
public:int numSubmat(vector<vector<int>>& mat) {int n = mat.size();int m = mat[0].size();vector<vector<int> > row(n, vector<int>(m, 0));for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {if (j == 0) {row[i][j] = mat[i][j];} else if (mat[i][j]) {row[i][j] = row[i][j - 1] + 1;}else {row[i][j] = 0;}}}int ans = 0;for (int j = 0; j < m; ++j) { int i = 0; stack<pair<int, int> > Q; int sum = 0; while (i <= n - 1) { int height = 1; while (!Q.empty() && Q.top().first > row[i][j]) {// 弹出的时候要减去多于的答案sum -= Q.top().second * (Q.top().first - row[i][j]); height += Q.top().second; Q.pop(); } sum += row[i][j]; ans += sum; Q.push({ row[i][j], height }); i++; } } return ans;}
};

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



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

相关文章

hdu1496(用hash思想统计数目)

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

hdu 4565 推倒公式+矩阵快速幂

题意 求下式的值: Sn=⌈ (a+b√)n⌉%m S_n = \lceil\ (a + \sqrt{b}) ^ n \rceil\% m 其中: 0<a,m<215 0< a, m < 2^{15} 0<b,n<231 0 < b, n < 2^{31} (a−1)2<b<a2 (a-1)^2< b < a^2 解析 令: An=(a+b√)n A_n = (a +

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 |

hdu 6198 dfs枚举找规律+矩阵乘法

number number number Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Problem Description We define a sequence  F : ⋅   F0=0,F1=1 ; ⋅   Fn=Fn

两数之和--力扣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: