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

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 的情况。通过三个主要步骤来解决这个问题：

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

什么是前缀和矩阵

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

前缀和矩阵的构建

给定一个大小为 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，因为这些位置不可能有左上方的矩阵。

解决方案

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

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

代码实现

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];}}// 遍历每个可能的子矩阵边长 kfor (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);}}
}

代码解析

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

总结

任何子矩阵的元素和。
3. 遍历子矩阵：

• 对于每个可能的子矩阵，计算其元素和 sum。
• 检查该和是否等于 k*k/2，如果是，则计数器 ans 增加。

总结

通过使用前缀和矩阵，可以高效地计算出所有边长为 k 的子矩阵中包含特定数量 1 的情况。这种方法大大减少了时间复杂度，能够在合理的时间内解决较大的输入规模。