-
输入是一个n*m的矩阵,要求找到其中最大的全0字矩阵
2010-11-25 12:16:23这个题其实就是最大子矩阵,只不过把0的权设为1,其他的权设为负无穷,这样求出来的肯定是最大的全是0的矩阵,仔细看一下我得做法,用的是动态规划。 2,实例代码: [code="C++"] #include const ...1,分析:
这个题其实就是最大子矩阵,只不过把0的权设为1,其他的权设为负无穷,这样求出来的肯定是最大的全是0的矩阵,仔细看一下我得做法,用的是动态规划。
2,实例代码:
#include <cstdio>
const int Max_Int = 0xfffffff;
int map[301][301],opt[301];
int n, m, maxn;
void init( )
{
int i, j, t;
scanf("%d%d", &n, &m);
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; j++ )
{
scanf("%d", &t);
if ( t == 0 )
map[i][j] = 1;
else
map[i][j] = -Max_Int;
}
maxn = 0;
}
void work( )
{
int i, j, k, t;
for (i = 0; i < n; i++)
{
for (j = i; j < n; j++)
{
t = 0;
for ( k = 0; k < m; k++ )
{
if (j == i)
opt[k] = map[i][k];
else
opt[k] += map[j][k];
t += opt[k];
if (t < 0)
t = 0;
if (maxn < t)
maxn = t;
}
}
}
}
void print( )
{
printf("%d", maxn);
}
int main( )
{
init( );
work( );
print( );
return 0;
} -
m*n的矩阵,有一个元素是0,把该元素所在的行和列上的元素全置为0
2020-06-20 20:35:03给定一个m*n的矩阵,如果有一个元素是0,就把该元素所在的行和列上的元素全置为0,要求使用原地算法。 拓展: 你的算法有使用额外的空间吗? 一种比较直接的算法是利用O(m,n)的空间,但是这不是一个好的解法 ...给定一个m*n的矩阵,如果有一个元素是0,就把该元素所在的行和列上的元素全置为0,要求使用原地算法。
拓展:
你的算法有使用额外的空间吗?
一种比较直接的算法是利用O(m,n)的空间,但是这不是一个好的解法
使用简单的改进可以在O(m+n)的空间解决这个问题,但是还不是最佳的解法
你能在常量级的空间复杂度内解决这个问题吗?
输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
法一:用 O(m+n)额外空间
解题思路:两遍扫matrix,第一遍用集合记录哪些行,哪些列有0;第二遍置0
1.计算二维矩阵的行数,列数
2.循环遍历如果某个数是0,记录其行号和列号,放到hashset中
3.循环遍历将hashset中的行号,列号对应的元素置0
import java.util.*; public class Solution { public void setZeroes(int[][] matrix) { Set<Integer>rowset=new HashSet<>(); Set<Integer>colset=new HashSet<>(); int m=matrix.length; int n=matrix[0].length; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(matrix[i][j]==0){ rowset.add(i); colset.add(j); } } } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(rowset.contains(i)||colset.contains(j)){ matrix[i][j]=0; } } } } }
法二:O(1)空间
关键思想: 用matrix第一行和第一列记录该行该列是否有0,作为标志位
但是对于第一行,和第一列要设置一个标志位,为了防止自己这一行(一列)也有0的情况
解题思路:
1.第一列,第一行有0的做标记
2.从第二行,第二列开始,有0的将第一列第一行置0
3.从第二行,第二列开始,第一行第一列有0 的,整行整列都置为0 。
4.当第一行标志位为true,整行为0
5.当第一行标志位为true,整行为0
import java.util.*; public class Solution { public void setZeroes(int[][] matrix) { int m=matrix.length; int n=matrix[0].length; boolean col=false; boolean row=false; //第一列有0,做标记 for(int i=0;i<m;i++){ if(matrix[i][0]==0){ col=true; break; } } //第一行有0,做标记 for(int j=0;j<n;j++){ if(matrix[0][j]==0){ row=true; break; } } //将第一列和第一行置为标记位 for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][j]==0){ matrix[i][0]=matrix[0][j]=0; } } } //置0 for(int i=1;i<m;i++){ for(int j=1;j<n;j++){ if(matrix[i][0]==0||matrix[0][j]==0){ matrix[i][j]=0; } } } //第一行有0,第一行都是0 if(row){ for(int j=0;j<n;j++) { matrix[0][j] = 0; } } //第一列有0,第一列都是0 if(col){ for(int i=0;i<m;i++) { matrix[i][0] = 0; } } } }
-
给定一个N * N的矩阵,在这个加粗样式矩阵中只有0和1两种值,返回边框全是1的最大正方形边长(利用三维数组...
2019-01-25 18:01:20给定一个N * N的矩阵,在这个加粗样式矩阵中只有0和1两种值,返回边框全是1的最大正方形边长(利用三维数组,c语言描述) 例: {0,1,1,1,1} {0,1,0,0,1} {0,1,0,0,1} {0,1,1,1,1} {0,1,0,1,1} 返回4 时间复杂度: O(n...给定一个N * N的矩阵,在这个加粗样式矩阵中只有0和1两种值,返回边框全是1的最大正方形边长(利用三维数组,c语言描述)
例:
{0,1,1,1,1}
{0,1,0,0,1}
{0,1,0,0,1}
{0,1,1,1,1}
{0,1,0,1,1} 返回4
时间复杂度: O(n³)#include <stdio.h> int a[100][100][2] = { 0 }; //初始化三维数组 void piv(int arr[][100],int n) { int row = n - 1; //初始化最下一行 for (int j = n - 1; j >= 0; j--) { int volue = arr[row][j]; if (volue == 1) { if (j == n - 1) { a[row][j][0] = 1; } else { a[row][j][0] = a[row][j + 1][0] + 1; } a[row][j][1] = 1; } } row--; //往上初始化 for (int i = row; i >= 0; i--) { for (int j = n - 1; j >= 0; j--) { int volue = arr[i][j]; if (volue == 1) { if (j == n - 1) { a[i][j][0] = 1; } else { a[i][j][0] = a[i][j + 1][0] + 1; } a[i][j][1] = a[i + 1][j][1] + 1; } } } } /* //打印三维数组 void pivOutput(int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { printf("%d,%d ", a[i][j][0], a[i][j][1]); } printf("\n"); } } */ //判断是否满足,如满足则输出结果并break所有循环 int check(int i, int j, int max) { if (a[i][j][0] >= max && a[i][j][1] >= max) { if (a[i + max - 1][j][0] >= max && a[i][j + max - 1][1] >= max) { printf("%d\n", max); return 1; } } return 0; } int main() { int n, s = 0; scanf("%d", &n); int arr[100][100] = { {0,1,0,1,0}, {1,1,1,1,1}, {0,1,0,1,1}, {0,1,1,1,1}, {0,1,1,1,1} }; int max = n, m = 0; piv(arr, n); //pivOutput(n); while (max >= 2) { for (int i = 0; ; i++) { if (n - i < max) { break; } for (int j = 0; ; j++) { if (n - j < max) { break; } s = check(i, j, max); //退出条件 if (s) { break; } } if (s) { break; } } max--; if (s) { break; } } return 0; }
-
leetcode-----给定一个m*n的矩阵,如果有一个元素是0,就把该元素所在的行和列上的元素全置为0,要求使用...
2020-07-12 10:17:08给定一个m*n的矩阵,如果有一个元素是0,就把该元素所在的行和列上的元素全置为0,要求使用原地算法。 拓展: 你的算法有使用额外的空间吗? 一种比较直接的算法是利用O(m,n)的空间,但是这不是一个好的解法 ...题目描述
给定一个m*n的矩阵,如果有一个元素是0,就把该元素所在的行和列上的元素全置为0,要求使用原地算法。
拓展:
你的算法有使用额外的空间吗?
一种比较直接的算法是利用O(m,n)的空间,但是这不是一个好的解法
使用简单的改进可以在O(m+n)的空间解决这个问题,但是还不是最佳的解法
你能在常量级的空间复杂度内解决这个问题吗?
思路:牺牲第一行第一列的空间,来记录对应行列中是否有0.(空间复杂度:O(1),时间复杂度:O(m*n))
以下面2行3列的矩阵为例
/* 2 0 4
** 3 1 0
** (1)先用flagRow标记第一行是否有0、用flagCol标记第一列是否有0,避免被覆盖
** 此例中flagRow = true(第一行有0);flagCol = false(第一行没有0)
** (2)再遍历矩阵中剩下的部分,如果某个元素matrix[i][j]为0,
** 则将matrix[i][0] = 0; matrix[0][j] = 0(表明对应的行列应该置为0)
** (3)再遍历第一行第一列,将其中值为0对应的行列 置为0
** (4)最后根据flagRow、flagCol处理第一行第一列的元素
*/public void setZeroes(int[][] matrix) { boolean flagRow=false,flagCol=false; int row = matrix.length;//行数 int col = matrix[0].length;//列数 //(1)判断第一行第一列是否有0,避免被覆盖 for(int i=0;i<row;i++){//第一列是否存在零 if(matrix[i][0] == 0){ flagCol = true; //第一列存在零 break; } } for(int j=0;j<col;j++){//第一行是否存在零 if(matrix[0][j] == 0){ flagRow = true;//第一行存在零 break; } } //(2)再遍历矩阵中剩下的部分,用第一行第一列来标记是否存在0 for(int i=1;i<row;i++){ for(int j=1;j<col;j++){ if(matrix[i][j] == 0){ //将第一行第一列中对应的行列标记为0 matrix[i][0] = 0; matrix[0][j] = 0; } } } //(3)遍历第一行第一列,对相应的行列置零 for(int i=1;i<row;i++){ for(int j=1;j<col;j++){ if(matrix[i][0]==0 || matrix[0][j]==0){ matrix[i][j] = 0; //表明对应的i行j列都应置为0 } } } //(4)处理第一行第一列 if(flagRow){//第一行有零元素 for(int i=0;i<col;i++){//将对应的行置零 matrix[0][i] = 0; } } if(flagCol){//第一列有零元素 for(int i=0;i<row;i++){//将对应的列置零 matrix[i][0] = 0; } } }
-
0 1矩阵内寻找最大m*m的全0矩阵块
2014-03-12 10:06:50在一个位图中找面积最大的白色矩形:给你一个NxN的黑白位图(0 1矩阵),找一个面积最大的全白色(全0)的矩形。注意了,是一个矩形,不是任意一个白色相连的区域。 以下想法挺巧妙的,利用找柱状图最大矩形的方法一... -
设一个空矩阵_高等代数|5.4 正定矩阵的相关问题
2020-12-31 08:32:28实对称矩阵是正定的充分必要条件是:的所有顺序主子式全大于0.定理2.实对称矩阵称为正定的,如果实二次型 是正定的.即对于中任意非零列向量 ,有 .定理3.元实对称矩阵A是正定的的充要条件为(1)的正惯性指数为;(2)... -
矩阵(01矩阵中找到k*k的全0子矩阵)
2018-11-03 20:35:26矩阵 Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 0 Accepted Submission(s...有一个二维矩阵,长和宽分别是N,M。矩阵上的每个点有两个状态(0,1),... -
矩阵置0
2020-12-01 12:35:48//给定一个m*n的矩阵,如果有一个元素是0,就把该元素所在的行和列上的元素全置为0,要求使用原地算法。 //拓展: //你的算法有使用额外的空间吗? //一种比较直接的算法是利用O(m,n)的空间,但是这不是一个好的... -
poj 3363 模拟(全0矩阵转换成特定的01矩阵)
2015-04-08 00:02:59题意:给定一个01矩阵,要求从0矩阵变换得到该结果,变换的方法是把一个绝对r*c大小的方格内的元素改变(0变1,1变0)。最少多少步。 思路:实际上这个步数是确定的,而且数据范围比较小,长宽不到100,所以简单... -
找出一个-1,0,1三值矩阵中的最大全1子块
2014-11-16 08:42:12并不要求子块仍为一个矩阵,但要求形状为凸多边形,可进行行列变换,只要求所求子块最大。 我的理解是:用贪心法找出一个连续的最全1块,再进行行列变换保证子块形状为凸。 数据量较大,文件形式给出。 -
矩阵
2019-12-17 16:06:41经常看到一个矩阵的右上角有个T的符号,就是Transposition的首字母。 4.矩阵与数相乘 就是把这个数跟矩阵中的每个数都相乘。 5.两个矩阵相乘 1.首先对于两个矩阵是否可以相乘是有要求的,假设要计算A矩阵乘以B矩阵... -
(最大矩阵)1158 全是1的最大子矩阵
2019-05-17 10:07:22给出1个M*N的矩阵M1,里面的元素只有0或1,找出M1的一个子矩阵M2,M2中的元素只有1,并且M2的面积是最大的。输出M2的面积。 收起 输入 第1行:2个数m,n中间用空格分隔(2 <= m,n <= 500) 第2 - N + 1行:每... -
矩阵相关定义性质全总结
2020-04-27 10:29:56矩阵是线性代数中的核心内容,所以我写这篇文章对矩阵(研究生以下阶段)进行一个完整的叙述。虽然是主要说矩阵,但是我也会将行列式、向量、线性方程组三个方面也包含在内,不过是概述的形式,具体的叙述会另外展开... -
Matrix 矩阵,单位矩阵,Transposition,矩阵与矩阵相乘
2012-12-04 15:11:35参考的是《游戏和图形学的3D数学入门教程》,非常不错的书,推荐阅读,老外很喜欢把一个东西解释的很详细。 1.一个普通的矩阵: 一个4x3的矩阵: ...经常看到一个矩阵的右上角有个T的符号,原来是Tra -
LC-矩阵置0
2021-01-14 00:56:44/*给定一个m*n的矩阵,如果有一个元素是0,就把该元素所在的行和列上的元素全置为0,要求使用原地算法。 拓展: 你的算法有使用额外的空间吗? 一种比较直接的算法是利用O(m,n)的空间,但是这不是一个好的解法 ... -
Leetcode算法Java全解答--73. 矩阵置零
2018-12-16 20:09:19给定一个 m x n 的矩阵,如果一个元素为 0,则将其所在行和列的所有元素都设为 0。请使用原地算法。 进阶: 一个直接的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。 一个简单的改进方案是使用 ... -
关于MATLAB矩阵处理,这儿全了
2020-07-19 22:57:42特殊矩阵 通用的特殊矩阵 zeros函数:产生全0矩阵,即零矩阵。...当矩阵是方阵时,得到一个单位矩阵。 rand函数:产生(0, 1)开区间均匀分布的随机矩阵。 fix(a+(b-a+1)*x): 产生[a,b]区间上均匀分布的随 -
0 1 矩阵查找最大正方形
2017-09-23 09:33:27题目:一个由0 1 矩阵组成的矩阵,如何标记处其中最大的全由1组成的正方形 算法分析: 0.从square的一个顶点考虑这个问题。从这个顶点横向看,是连续的N个1;从N个1组成的行往下看,是N个全是1的行。 1.以矩阵中... -
求0,1矩阵的最大连续全1块(可以非规则)
2010-10-25 13:37:00求0,1矩阵的最大连续全1块(con)给一个的0,1矩阵,求它的面积最大的全1子块。 要求时间。 ------------------------------------------------------------------------ 对矩阵做三次扫描, 扫描的次序都是从左到右... -
选择矩阵(选择矩阵是稀疏的)相关计算
2016-09-09 09:41:17S中的每1列有且只有一个1的元素,其他元素值为0,并标记每个1元素所在的行号,构建1的行号集合F。假设, 则 , 初始化为全0矩阵,则 如: , ,初始化A是全0矩阵,然后 则有 -
可换环上全矩阵代数的乘积零导子
2019-12-29 19:26:23可换环上全矩阵代数的乘积零导子,潘海山,周津名,R是一个含幺可换环,Mn(R)是R上所有nxn矩阵组成的一个R-代数,f是Mn(R)到Mn(R)的一个线性映射,对Mn(R)中的任意矩阵X,Y,如果有XY=0,那么就� -
MATLAB矩阵处理(一)
2019-07-11 22:19:58当矩阵是方阵时,得到一个单位矩阵。 rand函数:产生(0,1)区间均匀分布的随机矩阵。 randn函数:产生均值为0,方差为1的标准正态分布随机矩阵。 zeros函数的调用格式: zeros(m... -
MATLAB(一):矩阵基本操作
2019-04-18 22:47:54MATLAB面向矩阵! MATLAB面向矩阵! MATLAB面向矩阵! 一些特殊矩阵 通用性特殊矩阵 如零矩阵,幺矩阵,单位矩阵等 ...eye函数 :产生对角线为1的矩阵,当矩阵是方阵时,得到一个单位矩阵 rand函数 ... -
两个矩阵面积并——————简单几何
2019-04-01 20:25:23想要把所有情况都考虑出来,但是情况太多了,又看了一眼题,发现数据全是整数,范围才1000,于是开了一个1000*1000的二维矩阵,将在矩阵之间的面积标记为1,其他的标记为0,再看看有多少个1,那么两个矩阵的面积就是... -
矩阵(一):SVD分解
2020-03-12 23:52:45文章目录0 参考链接(尊重原著)1 SVD分解原理2 SVD分解意义3 SVD分解的应用4 SVD数学举例 0 参考链接(尊重原著) 下面这个讲的很好很全面 视觉SLAM常见的QR分解SVD分解等...假设A是一个m∗n阶矩阵,如此则存在一个... -
matlab 二范数_MATLAB矩阵处理(一)
2021-01-22 19:38:16当矩阵是方阵时,得到一个单位矩阵。rand函数:产生(0,1)区间均匀分布的随机矩阵。randn函数:产生均值为0,方差为1的标准正态分布随机矩阵。zeros函数的调用格式:zeros(m):产生m*m零矩阵。zeros(m,n):... -
矩阵的运算和矩阵的秩
2018-11-04 15:36:55矩阵 行阶梯矩阵的定义 1. 全0行的上面都是非0行 2. 非0行的首个非0元一定比上一行的首个非0元更靠右 3. 左上角的元素所在列其他元素皆为0 ...2. 数乘,矩阵各个元素X一个数 3. 乘法,MxN x Nx...
-
【爱码农】C#制作MDI文本编辑器
-
Day2-运算符和变量作业
-
CS学习笔记(续)
-
区块链公开课(中).pdf
-
HW解决方案业务拓展指引.pptx
-
libFuzzer视频教程
-
牛牛量化策略交易
-
win10 系统下一些exe图标不显示的解决办法
-
用研转岗规划——案例2则
-
工资计算
-
CSP201512-1数位之和(C++100分)
-
生益电子首次公开发行股票并在科创板上市招股说明书.pdf
-
2014年重庆理工大学《ERP原理及应用I》两套期末考试试卷.pdf
-
Windows系统管理
-
人事管理系统-Java类代码资源
-
网络标准和网络协议
-
Oracle_11g_Linux到Linux_DataGuard部署
-
分布式事务的概念及特征
-
linux查看进程和kill进程
-
MYSQL长字符截断