[LeetCode221. 最大正方形] | 刷题打卡

微芒不朽

发布于 2022-09-13 10:04:34

3400

发布于 2022-09-13 10:04:34

文章被收录于专栏：前端进阶-詹躲躲前端进阶-詹躲躲

一、题目描述：

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。示例 1：输入：

matrix = [
 ["1","0","1","0","0"],
 ["1","0","1","1","1"],
 ["1","1","1","1","1"],
 ["1","0","0","1","0"]
]
输出：4

示例 2：输入：

matrix = [
 ["0","1"],
 ["1","0"]
]
输出：1

示例 3：输入：

matrix = [
 ["0"]
]
输出：0

提示：

    m == matrix.length
    n == matrix[i].length
    1 <= m, n <= 300
    matrix[i][j] 为 '0' 或 '1'

二、思路分析：

2.1 动态规划法分析：

1.如果matrix[i][j]等于0，那么就不用看了，直接等于0。

2.如果matrix[i][j]等于1，那么我们将matrix[[i][j]] 分别往上和往左进行延伸，直到碰到一个0为止。

3.当前数组为1的时候 dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 //判断左上，左下，右上是否有0

三、AC 代码：

javascript解法

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function (matrix) {
    if (!matrix.length || !matrix[0].length) return 0
    var maxSlideLen = 0, //记录最长边
        dp = Array(matrix.length); //构建dp数组
    for (var i = 0; i < matrix.length; i++) {
        dp[i] = Array(matrix[0].length).fill(0); //填充每一位为0
        for (let j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] === 1) {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1; // 第一列和第一行的dp值为1
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 //判断左上，左下，右上是否有0
                }
                maxSlideLen = Math.max(maxSlideLen, dp[i][j]) //更新最大边长
            }
        }
    }
    return maxSlideLen ** 2 //求最大边长面积
};

python解法

class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if len(matrix)==0 or len(matrix[0])==0:
            return 0
        maxSlide=0
        rows,cols = len(matrix),len(matrix[0])
        dp = [[0]*(cols+1) for i in range(rows+1)]
        for i in range(1,rows+1):
            for j in range(1,cols+1):
                if matrix[i-1][j-1] == '1':
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1 ## 判断左上，左下，右上是否有0
                    maxSlide = max(maxSlide, dp[i][j]) ## 更新最大边长
        return maxSlide*maxSlide

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-03-07，如有侵权请联系 cloudcommunity@tencent.com 删除

python