首先描述一下问题
/**
*
* 时间限制(普通/Java):6000MS/20000MS 运行内存限制:65536KByte
* 总提交:131 测试通过:32
* 描述
* 在一个0,1方阵中找出其中最大的全0子矩阵,所谓最大是指O的个数最多
* 输入
* 单组数据第一行为整数N,其中1<=N<=2000,为方阵的大小,紧接着N行每行均有N个0或1,相邻两数间严格用一个空格隔开
* 输出
* 输出仅一行包含一个整数表示要求的最大的全零子矩阵中零的个数
* 样例输入
* 5
* 0 1 0 1 0
* 0 0 0 0 0
* 0 0 0 0 1
* 1 0 0 0 0
* 0 1 0 0 0
* 样例输出
* 9
*/
我的做法是遍历每个点,根据每个点横向和纵向的构造全0矩阵,选取最大的全0矩阵输出
正确性应该是没问题的,不过时间复杂度
遍历的复杂度是o(n^2)然后每个点构造矩形复杂度也是o(n^2)
最大时间复杂度就为n^4
因此求优化
package graph;
/**
*
* 时间限制(普通/Java):6000MS/20000MS 运行内存限制:65536KByte
* 总提交:131 测试通过:32
* 描述
* 在一个0,1方阵中找出其中最大的全0子矩阵,所谓最大是指O的个数最多
* 输入
* 单组数据第一行为整数N,其中1<=N<=2000,为方阵的大小,紧接着N行每行均有N个0或1,相邻两数间严格用一个空格隔开
* 输出
* 输出仅一行包含一个整数表示要求的最大的全零子矩阵中零的个数
* 样例输入
* 5
* 0 1 0 1 0
* 0 0 0 0 0
* 0 0 0 0 1
* 1 0 0 0 0
* 0 1 0 0 0
* 样例输出
* 9
*
* @author Leon.Chen
*
*/
public class AllZeroMatrix {
/**
* 输入矩阵
*/
public int[][] matrix;
/**
* 矩阵最大行
*/
public int maxRow;
/**
* 矩阵最大列
*/
public int maxColumn;
/**
* 被乘数
*/
public int multiplicand;
/**
* 最大全零矩阵
*/
public int totalCount;
/**
* 每个点向下,向右扩张矩形,取最大的矩形
*
* @param row
* @param column
*/
public void spread(int row, int column) {
int rowStart = row;
int rowEnd = row;
while (rowEnd < maxRow) {
if (matrix[rowEnd][column] == 0) {
rowEnd++;
} else {
break;
}
}
this.multiplicand = 0;
spreadMatrixRight(rowStart, rowEnd, column);
int count = (rowEnd - rowStart) * multiplicand;
if (totalCount < count) {
totalCount = count;
}
int columnStart = column;
int columnEnd = column;
while (columnEnd < maxColumn) {
if (matrix[row][columnEnd] == 0) {
columnEnd++;
} else {
break;
}
}
this.multiplicand = 0;
spreadMatrixbelow(columnStart, columnEnd, row);
count = (columnEnd - columnStart) * multiplicand;
if (totalCount < count) {
totalCount = count;
}
}
/**
* 矩阵的向右扩张
*
* @param start
* @param end
* @param column
*/
public void spreadMatrixRight(int start, int end, int column) {
boolean flg = true;
for (int i = start; i < end; i++) {
if (matrix[i][column] == 1) {
flg = false;
break;
}
}
if (flg) {
multiplicand++;
int nextColumn = column;
nextColumn++;
if (nextColumn < maxColumn) {
spreadMatrixRight(start, end, nextColumn);
}
}
}
/**
* 矩阵的向下扩张
*
* @param start
* @param end
* @param row
*/
public void spreadMatrixbelow(int start, int end, int row) {
boolean flg = true;
for (int i = start; i < end; i++) {
if (matrix[row][i] == 1) {
flg = false;
break;
}
}
if (flg) {
multiplicand++;
int nextRow = row;
nextRow++;
if (nextRow < maxRow) {
spreadMatrixbelow(start, end, nextRow);
}
}
}
/**
* 得到最大全零矩阵的大小
*
* @param printMatrix
*/
public void getAllZeroMatrix(int[][] printMatrix) {
matrix = printMatrix;
maxRow = matrix.length;
maxColumn = matrix[0].length;
for (int i = 0; i < maxRow; i++) {
for (int j = 0; j < maxColumn; j++) {
int count = (maxRow - i) * (maxColumn - j);
if (count <= totalCount) {
continue;
}
if (matrix[i][j] != 1) {
spread(i, j);
}
}
}
System.out.println(totalCount);
}
public static void main(String[] args) {
int[][] printMatrix = new int[][]{
{0,1,0,1,0},
{0,0,0,0,0},
{0,0,0,0,1},
{1,0,0,0,0},
{0,1,0,0,0},
};
long start = System.currentTimeMillis();
new AllZeroMatrix().getAllZeroMatrix(printMatrix);
long end = System.currentTimeMillis();
System.out.println((end-start)+"ms");
}
}
分享到:
相关推荐
设矩阵的大小为矩阵中所有元素的和,现输入一个N*N的矩阵,请设计算法计算最大的非空(大小至少是1*1)子矩阵的大小。 例如4×4的矩阵为: 1 0 1 1 1 1 1 1 1 1 1 1 0 1 -6 -8 其最大子矩阵为: 1 0 1 1 1 1 1 1 1 1...
1 i m N and 1 j n N . For convenience, the maximum submatrix sum is 0 if all the integers are negative. Example: For matrix and has the sum of 15. 0270 9262 92 ...
求一个M*N的矩阵的最大子矩阵和。 比如在如下这个矩阵中: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 拥有最大和的子矩阵为: 9 2 -4 1 -1 8 其和为15。 #include using namespace std; int A[55][55]; int main(){ ...
求一个M*N的矩阵的最大子矩阵和。 比如在如下这个矩阵中: 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 拥有最大和的子矩阵为: 9 2 -4 1 -1 8 其和为15。 思路: 首先,这个子矩阵可以是任意大小的,而且起始...
定义子矩阵的和为其所有元素之和,最大子矩阵为子矩阵和值最大的子矩阵。 1. 理解动态规划算法的求解过程。 2. 分析动态规划算法的时间复杂度,比较动态规划算法与其他算法的效率差异。 3. 学会如何利用动态规划算法...
Description 一个长,宽,高分别是m,n,p的长方体被分割成m*n*p个小立方体。每个小立方体内含一个整数。 试着设计一个算法,计算所给长方体的最大子...3,基于“最大子矩阵和”,编写三维的“最大子长方体和”的解法。
给定一个正整数和负整数组成的 N × M 矩阵,编写代码找出元素总和最大的子矩阵。 返回一个数组 [r1, c1, r2, c2],其中 r1, c1 分别代表子矩阵左上角的行号和列号,r2, c2 分别代表右下角的行号和列号。 若有多个...
Description 一个长,宽,高分别是m,n,p的长方体被分割成m*n*p个小立方体。每个小立方体内含一个整数。 试着设计一个算法,计算所给长方体的最大子...3,基于“最大子矩阵和”,编写三维的“最大子长方体和”的解法。
用numpy中的内置函数效率能提高 矩阵计算 用numpy矩阵函数执行效率大幅提升 ...最大最小值 直接用np.max() 或 np.min() 我一开始用错成 minMaxLoc 函数走了很多弯路 当然还有 np.clip()等函数 不一一详述
1、集合划分问题 2、最大子矩阵和 题目描述: 给定一个n*n(0)的矩阵,请找到此矩阵的一个子矩阵,并且此子矩阵的各个元素的和最大,输出这个最大的值。
历届试题 最大子阵 时间限制:1.0s 内存限制:256.0MB 问题描述 给定一个n*m的矩阵A,求A中的一个非空子矩阵,使这个子矩阵中的元素和
1017 最大0,1子矩阵 这题要想不超时,必须DP 1020 最大正方形 这题和1017很相似,不过有更快的解决方法 1021 背包问题 1022 Longest Common Sequence 也可用二叉搜索树(nlog时间)解决,见llj的书 1023 Happy ...
35. 求一个矩阵中最大的二维矩阵(元素和最大).如: 1 2 0 3 4 2 3 4 5 1 1 1 5 3 0 中最大的是: 4 5 5 3 要求:(1)写出算法;(2)分析时间复杂度;
包括0-1背包、无限背包、有限背包、有价值背包、小数背包(贪心即可)等,是极为经典的模型,其转化与优化也是很重要的。 2、最长非降子序列模型 改版:渡河问题、合唱队型等 3、最大子段和模型 改版:K大子段和、...
基于对鞍点矩阵的对称性以及鞍点矩阵的最大特征值与子矩阵特征值之间关系的分析,改进了关于鞍点矩阵最大特征值的下界估计,从而得到一类改进的关于鞍点矩阵最大特征值的区间估计。数值实验中考察了由 P1-P0混合有限元...
的最大方形子矩阵的大小 使用动态规划的矩阵链乘法 找到从矩阵的第一个单元格到达最后一个单元格的最小成本 求矩阵中相邻数构成的最长序列 计算具有给定成本的矩阵中到达目标单元格的路径数 0–1 背包问题 最大化...
0、排序 快速排序 快速排序 第K个数 归并排序 归并排序 逆序对的数量 1、二分 整数二分 数的范围 小数二分 数的三次方根 2、前缀和 一维前缀和 前缀和数组 二维前缀和 子矩阵的和 3、差分 一维差分 差分数组 二分差...
leetcode二维数组为什么要分段树? 也称为区间树 也称为锦标赛树 ...M[0…n-1][0…m-1],并要求查询找到一些子矩形 M[a…b][e…f] 上的总和/最小值/最大值,如以及修改单个矩阵元素的查询(即 M[x] [y] = p