- 浏览: 173475 次
- 性别:
- 来自: 济南
文章分类
最新评论
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
典型的二维动态规划的问题。我们构造一个二维的dp数组,dp[i][j]代表到点(i , j)时由1构成的正方形的最大长度。当char[i][j] 为0时,dp[i][j]在当前点只能为0;如果char[i][j]为1时,dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1,我们只能选择一个最小的正方形,然后加1,每次都用一个max来记录当前的最大值。最后返回max * max即可。代码如下:
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.
典型的二维动态规划的问题。我们构造一个二维的dp数组,dp[i][j]代表到点(i , j)时由1构成的正方形的最大长度。当char[i][j] 为0时,dp[i][j]在当前点只能为0;如果char[i][j]为1时,dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1,我们只能选择一个最小的正方形,然后加1,每次都用一个max来记录当前的最大值。最后返回max * max即可。代码如下:
public class Solution { public int maximalSquare(char[][] matrix) { if(matrix == null || matrix.length == 0) return 0; int m = matrix.length; int n = matrix[0].length; int max = 0; int[][] dp = new int[m][n]; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(i == 0 || j == 0) { dp[i][j] = matrix[i][j] - '0'; } else if(matrix[i][j] == '0') { dp[i][j] = 0; } else { dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1; } if(dp[i][j] > max) max = dp[i][j]; } } return max * max; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 226You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 333Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 512Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 430Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 620Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 532Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 861Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 735You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For a undirected graph with tre ...
相关推荐
Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:单调栈 Island Perimeter:简单对比(map+zip的使用) or 遍历查找 Max Area of Island:DFS(本来想用DP,发现出不来) Number ...
数据挖掘相关内容Redundancy-Aware Maximal Cliques,关于最大派系
The set of maximal frequent subgraphs is much smaller to that of the set of frequent subgraphs, thus providing ample scope for pruning. MARGIN is a maximal subgraph mining algorithm that moves among ...
maximal square. Use dynamic programming. use just O(n) space. The extra space equals matrix col length. majority element ii . 使用 "摩尔投票法"。 LCA 二叉树最近共同祖先问题. 递归结题的思路,在左子树、...
关于论文MaPle A Fast Algorithm for Maximal Pattern-based Clustering∗的翻译
2017 A Maximal Clique Based Multiobjective Evolutionary algorithm for overlapping community detection 论文PPT讲解
关于最大流网络算法的一些介绍,是外国文献,最大网络流的应用
Maximal Beasts
韩国人写的流数据分析SCI论文,2013年发表
纳米尺寸效应新应用:单键比热,强度,及应变极限,孙长庆,,Specific heat, strength, and maximal strain of atomic bond in an impurity-free monatomic chain.
非齐次分数次 Schr,张军勇,郑继强,本文考虑如下极大不等式$$ ig|sup_{0<t<1}|e^{itsqrt{1+(-Delta)^ lpha}}f(x)| ig|_{L^2(B(0,1))}leqC|f|_{H^s(mathbb R^d)},quad orall~fin H^s(mathbb R^d),quad ...
A new maximal-margin spherical-structured multi-class support vector machine Pei-Yi Hao · Jung-Hsien Chiang · Yen-Hsiu Lin Published online: 18 October 2007 © Springer Science+Business Media, LLC ...
一篇流数据分析方面的经典SCI论文,2013年发表的
Interactive image segmentation by maximal similarity based region merging
1.解压文件。运行Matlab,在Matlab中打开.../minepy/matlab/(当前文件夹为matlab); 2.在command window(命令行窗口)中输入:mex mine_mex.c ../libmine/mine.c; 3.测试代码: x = linspace(0, 1, 1001);...
图论资料,仅供学习使用,方便自己平时学习资料查阅,日常讲义积累,请勿用作商业用途,On Sparse Maximal 2-Planar Graphs
We propose a self-stabilizing algorithm for computing a maximal matching in an anony- mous network. The complexity is O(n2) moves with high probability, under the ad- versarial distributed daemon. ...
实现了区域合并的图像分割的经典方法,是Interactive Image Segmentation by Maximal Similarity based Region Merging 论文的源码,可以好好研究
这个文档的质量相当高,不过是纯英文的,但是,我保证你看过之后,肯定会认为这个文档写得实在太好了。