100道面试必会算法-27-美团2024面试第一题-前缀和矩阵

在这里插入图片描述

问题解读

给定一个 n x n 的二进制矩阵，每个元素是 0 或 1。我们的任务是计算矩阵中所有边长为 k 的子矩阵中，包含特定数量 1 的情况。例如，我们希望找到所有边长为 k 的子矩阵中包含 k*k/2 个 1 的子矩阵数量。

输入格式：


第一行：一个整数 n，表示矩阵的大小。
接下来的 n 行：每行包含一个长度为 n 的二进制字符串，表示矩阵中的一行。

输出格式：


对于每个可能的子矩阵边长 k，输出一个整数，表示边长为 k 且包含特定数量 1 的子矩阵的数量。如果 k 是奇数

计算一个大小为 n x n 的矩阵中，所有边长为 k 的子矩阵中包含特定数量的 1 的情况。通过三个主要步骤来解决这个问题：

读取输入并初始化矩阵：读取一个 n x n 的矩阵，并构建前缀和矩阵 m 和 sum。
计算前缀和：通过构建前缀和矩阵，可以快速计算任何子矩阵的元素和。
检查子矩阵：对于每个可能的子矩阵，检查其是否满足条件。

什么是前缀和矩阵

前缀和矩阵是一种用于快速计算二维数组（矩阵）中子矩阵元素之和的数据结构。通过预先计算和存储每个位置的前缀和，我们可以在常数时间内计算任意子矩阵的元素和。

前缀和矩阵的构建

给定一个大小为 n x n 的矩阵 nums，我们可以构建一个前缀和矩阵 m。前缀和矩阵的每个元素 m[i][j] 表示从矩阵的左上角 (1,1) 到位置 (i,j) 的所有元素的和。其递推公式为：

m[i][j]=m[i−1][j]+m[i][j−1]−m[i−1][j−1]+nums[i][j]

在边界条件下：

m[i][0] 和 m[0][j] 初始为 0，因为这些位置不可能有左上方的矩阵。

解决方案

我们将通过以下步骤来解决这个问题：

读取输入并初始化矩阵：我们将读取输入的矩阵，并使用两个矩阵 nums 和 m 来存储矩阵元素和前缀和。
计算前缀和：前缀和矩阵 m 可以帮助我们快速计算任何子矩阵的元素和。前缀和矩阵的计算公式为： m[i][j]=m[i−1][j]+m[i][j−1]−m[i−1][j−1]+nums[i][j]
检查子矩阵：对于每个可能的子矩阵，我们通过前缀和矩阵快速计算其元素和，并检查其是否满足条件。

代码实现

import java.util.Scanner;

public class Meituan {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        char[] chars;
        int[][] m = new int[n + 1][n + 1];
        int[][] nums = new int[n + 1][n + 1];

        // 初始化矩阵和前缀和矩阵
        for (int i = 1; i <= n; i++) {
            chars = input.next().toCharArray();
            for (int j = 1; j <= n; j++) {
                nums[i][j] = chars[j - 1] - '0';
                m[i][j] = m[i - 1][j] + m[i][j - 1] - m[i - 1][j - 1] + nums[i][j];
            }
        }

        // 遍历每个可能的子矩阵边长 k
        for (int k = 1; k <= n; k++) {
            if (k % 2 != 0) {
                System.out.println(0);
                continue;
            }

            int ans = 0;
            // 遍历每个可能的子矩阵
            for (int i = 1; i + k - 1 <= n; i++) {
                for (int j = 1; j + k - 1 <= n; j++) {
                    int x = i + k - 1;
                    int y = j + k - 1;
                    int sum = m[x][y] - m[i - 1][y] - m[x][j - 1] + m[i - 1][j - 1];
                    if (sum == k * k / 2) ans++;
                }
            }
            System.out.println(ans);
        }
    }
}

代码解析

初始化矩阵和前缀和矩阵：
- nums 用于存储输入的二进制矩阵。
- m 用于存储前缀和矩阵，通过累加计算得到。
计算前缀和：
- 前缀和矩阵 m[i][j] 通过公式 m[i][j] = m[i-1][j] + m[i][j-1] - m[i-1][j-1] + nums[i][j] 计算得到。
- 这样可以在常数时间内计算任何子矩阵的元素和。
遍历子矩阵：
- 对于每个可能的子矩阵，计算其元素和 sum。
- 检查该和是否等于 k*k/2，如果是，则计数器 ans 增加。