Golang | LeetCode

Задача: 1277. Count Square Submatrices with All Ones Сложность: medium Если задана матрица m * n из единиц и нулей, верните, сколько квадратных подматриц имеют все единицы. Пример: Input: matrix = [   [0,1,1,1],   [1,1,1,1],   [0,1,1,1] ] Output: 15 👨‍💻 Алгоритм: 1⃣Создайте вспомогательную матрицу dp таких же размеров, что и исходная матрица, для хранения размеров максимальных квадратов. 2⃣Пройдите по каждому элементу матрицы и обновите dp следующим образом: если элемент равен 1, то dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. 3⃣Суммируйте все значения в dp, чтобы получить количество квадратных подматриц, состоящих из всех единиц. 😎 Решение:

func countSquares(matrix [][]int) int {
    m := len(matrix)
    n := len(matrix[0])
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
    }
    count := 0

    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if matrix[i][j] == 1 {
                if i == 0 || j == 0 {
                    dp[i][j] = 1
                } else {
                    dp[i][j] = min(dp[i-1][j], min(dp[i][j-1], dp[i-1][j-1])) + 1
                }
                count += dp[i][j]
            }
        }
    }

    return count
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Ставь 👍 и забирай 📚 Базу знаний