max-square

[Golang Theme Learning month] Over the weekend, I have done several dynamic programming questions and released a super exquisite teaching version, which has a very good response. Next, I will use two languages to brush the coding questions, respectively GO and JAVA.

$\color{red}{if you are not familiar with dynamic programming, please refer to this chapter ~}$

Liver for many days – dynamic planning ten even – super delicate analysis | brush title punch card

$\color{green}{😄 😄 😄 ~}$

What problem can I choose to do dynamic programming?

Counting 1.

• How many ways can I get to the bottom right corner
• How many ways can I pick the sum of k numbers yes is sum

2. Find the maximum and minimum

• The maximum numeric sum of the path from the upper left corner to the lower right corner
• Maximum ascending subsequence length

3. Seek existence

• Stone game, whether the first hand will win
• Can we pick k numbers such that the sum is sum

4. Comprehensive application

• Dynamic planning + hash
• Dynamic programming + recursion
• .

Leecode 221. Maximum square

In a two-dimensional matrix of ‘0’ and ‘1’, find the largest square containing only ‘1’ and return its area.

Example 1:

Input: matrix = [[” 1 “, “0”, “1”, “0” and “0”], [” 1 “, “0”, “1”, “1”, “1”], [” 1 “, “1”, “1”, “1”, “1”], [” 1 “, “0”, “0”, “1”, “0”]]

Output: 4

Input: matrix = [[“0″,”1”],[“1″,”0”]

Output: 1.

Example 3:

Input: matrix = [[“0”]]

Output: 0

Tip:

m == matrix.length

n == matrix[i].length

1 <= m, n <= 300

Matrix [I][j] = ‘0’ or ‘1’

—

$\ color {green} {! 😄 😄 😄 ~}$

Reference code

The language version

func maximalSquare(matrix [][]byte) int {
    dp := make([] []int.len(matrix))
    maxSide := 0
    for i := 0; i < len(matrix); i++ {
        dp[i] = make([]int.len(matrix[i]))
        for j := 0; j < len(matrix[i]); j++ {
            dp[i][j] = int(matrix[i][j] - '0')
            if dp[i][j] == 1 {
                maxSide = 1}}}for i := 1; i < len(matrix); i++ {
        for j := 1; j < len(matrix[i]); j++ {
            if dp[i][j] == 1 {
                dp[i][j] = min(min(dp[i- 1][j], dp[i][j- 1]), dp[i- 1][j- 1]) + 1
                if dp[i][j] > maxSide {
                    maxSide = dp[i][j]
                }
            }
        }
    }
    return maxSide * maxSide
}

func min(x, y int) int {
    if x < y {
        return x
    }
    return y
}





Copy the code

$\color{red}{NICE too simple 😄 😄 😄 ~}$

Java version

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSide = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return maxSide;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int[][] dp = new int[rows][columns];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1;
                    } else {
                        dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1; } maxSide = Math.max(maxSide, dp[i][j]); }}}int maxSquare = maxSide * maxSide;
        returnmaxSquare; }}Copy the code

❤ ️ ❤ ️ ❤ ️ ❤ ️

Thank you very much talent can see here, if this article is written well, feel that there is something to ask for praise 👍 for attention ❤️ for share 👥 for handsome Oba I really very useful!!

If there are any mistakes in this blog, please comment, thank you very much!

At the end of this article, I recently compiled an interview material “Java Interview Process Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, databases, data structures and so on. How to obtain: GitHub github.com/Tingyu-Note… , more attention to the public number: Ting rain notes, one after another.