- 浏览: 183661 次
- 性别:
- 来自: 济南
文章分类
最新评论
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 265Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 267You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 384Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 374Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 498Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 563Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 475Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 664Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 469The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 429Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 575Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 581Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 426All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 898Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 930Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 602Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 675Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 844Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 783You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 705For a undirected graph with tre ...
相关推荐
java java_leetcode题解之Maximal Square.java
python python_leetcode题解之221_Maximal_Square.py
- Maximal Square:寻找由1组成的最大正方形的面积,需要使用动态规划(Dynamic Programming)的方法来求解。 这些题目不仅考查了候选人对特定数据结构的使用技巧,还涉及到了算法思想的灵活运用,例如动态规划、...
13. **Maximal Square** (最大的正方形) 找到01矩阵中最大的全1子矩阵。可以使用动态规划和单调栈或Morris遍历。 14. **Minimum Cost For Tickets** (最便宜的机票购买方案) 在有限天数内,需要购买多张机票才能...
Square:DP Maximal Rectangle:单调栈(Histogram变形) Largest Rectangle in Histogram:单调栈 Island Perimeter:简单对比(map+zip的使用) or 遍历查找 Max Area of Island:DFS(本来想用DP,发现出不来) Number ...
maximal square. Use dynamic programming. use just O(n) space. The extra space equals matrix col length. majority element ii . 使用 "摩尔投票法"。 LCA 二叉树最近共同祖先问题. 递归结题的思路,在左子树、...
标题"maximal-EE-master.rar_about3kb_massive MIMO_massive MIMO_massiv"中,"maximal-EE-master"可能指的是一个关于最大能效(Maximal Energy Efficiency, maximal EE)的研究项目或者代码库,而".rar"表明这是一...
5. **解调算法**:介绍如MMSE(Minimum Mean Square Error)或LMMSE(Linear Minimum Mean Square Error)等解调算法,以及如何在多径环境下优化它们。 6. **性能分析**:可能包含理论上的性能分析,比如误码率(Bit...
lru缓存leetcode 问题来自 ...文件摘要 image_overlap.cpp ...maximal_square.cpp 给定一个由 0 和 1 填充的二维二进制矩阵,找到仅包含 1 的最大正方形并返回其面积。 例子: 输入: [1 0 1 0 0] [1 0 1
常见的波束形成算法有最小均方误差(Minimum Mean Square Error, MMSE)、最大功率增益(Maximal Ratio Transmission, MRT)和最优化方向性(Optimum Beamforming, BF)等。 3. **动态调整**:由于无线环境的多变性...
6. **信号标准化**:为了消除个体差异和传感器位置的影响,通常需要对EMG信号进行归一化处理,如使用最大幅度(Maximal Voluntary Contraction, MVC)或均方根(Root Mean Square, RMS)等方法。 通过以上步骤,...
"maximal-square.py"是一道矩阵操作的题目,要求找出矩阵中最大的正方形子矩阵,其中所有元素都为1。这题需要用到动态规划和矩阵操作,Python的二维数组操作为解题提供了便利。 "super-ugly-number.py"涉及数论和...
3. **MMRC(Maximal-Ratio Combining)判决**:是一种分集合并技术,通过最大化接收信号的功率来改善接收质量。在多天线接收系统中,MMRC判决结合了各个天线接收到的信号,以提高信噪比和误码率性能。源代码中的MMRC...
常见的空间分集技术包括最大比合并(Maximal Ratio Combining, MRC)、选择式合并(Selection Combining, SC)和等增益合并(Equal Gain Combining, EGC)等。 ##### 2. 空间复用技术 空间复用技术允许在同一时间...
在实际应用中,可能会使用不同的信道模型,如瑞利衰落或多径衰落,并且可能涉及到各种优化策略以提高鲁棒性,例如最小均方误差(Minimum Mean Square Error, MMSE)波束成形或最大信噪比(Maximal Ratio Combining, ...
简化的预编码技术可能包括线性预编码器,如最大功率分配(Maximal Ratio Transmission,MRT)和最小均方误差(Minimum Mean Square Error,MMSE)预编码,它们相对简单且易于实现。此外,基于机器学习的预编码策略也...
最大相关熵(Maximal Correntropy Criterion, MCC)是一种基于概率分布相似度度量的优化准则,它能有效捕捉非高斯噪声特性,尤其对于冲击噪声有良好的抵抗力。在自适应滤波中,MCC可以替代传统的均方误差(Mean ...
5. **最大自愿收缩(Maximal Voluntary Contraction, MVC)**:在肌电分析中,MVC是指个体在特定动作下所能产生的最大肌肉力量。MVC的数据通常用来作为基线,对比其他条件下的肌肉激活程度,评估肌肉的疲劳或功能状态...
例如,最小均方误差(Minimum Mean Square Error,MMSE)检测器和联合检测技术可以有效地处理多用户干扰。 6. **调度策略**:在多用户共享信道的情况下,调度策略决定哪个用户在何时获得服务。优化的调度策略可以...