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，要求使用原地算法。

拓展：

你的算法有使用额外的空间吗？

一种比较直接的算法是利用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的最大正方形边长（利用三维数组，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;
}

题目描述

给定一个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;
            }
        }
    }