镇江哪里做网站,竞价排名是什么意思,wordpress模板代码,seo网络推广怎么做统计全1子矩阵个数 思路1#xff1a;首先考虑深度优先模拟#xff0c;从【0#xff0c;0】出发向下、右扩展#xff0c;符合条件res#xff0c;最后输出res#xff0c;比较直观#xff0c;但重复进行了大量节点遍历操作#xff0c;时间复杂度较高#xff0c;数据量大时…统计全1子矩阵个数 思路1首先考虑深度优先模拟从【00】出发向下、右扩展符合条件res最后输出res比较直观但重复进行了大量节点遍历操作时间复杂度较高数据量大时会超时
class Solution {unordered_setintset;int res0;void get(vectorvectorint mat,int start_r,int start_c,int row,int col){if(rowmat.size()||colmat[0].size()||set.count(start_r(start_c((rowcol*151)*151))*151)) return;for(int istart_r;irow;i){if(!mat[i][col]) return;}for(int istart_c;icol;i){if(!mat[row][i]) return;}res;set.insert(start_r(start_c((rowcol*151)*151))*151);get(mat,start_r,start_c,row1,col);get(mat,start_r,start_c,row,col1);}
public:int numSubmat(vectorvectorint mat) {for(int i0;imat.size();i){for(int j0;jmat[0].size();j){get(mat,i,j,i,j);}}return res;}
};思路2单考虑行或列时每增加1个1结果增加 行或列1个数1那么多行多列时每增加一行或一列增加12…n*m1加列时n为行数m为原来列数实际上情景就是第一个图的拓展只不过矩形中的1实际上是长度相等的全1矩形
因而仅需要使用一个二维数组tmp存储target[i][j]及前有几个连续的1然后从上到下加上min(tmp[i][j],tmp_pre_min)即可
class Solution {
public:int numSubmat(vectorvectorint mat) {int n mat.size();int m mat[0].size();vectorvectorint row(n, vectorint(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(vectorvectorint mat) {int n mat.size();int m mat[0].size();vectorvectorint row(n, vectorint(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; stackpairint, 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;}
};
