美团2024年春招第一场笔试【技术】-小美的平衡矩阵

平衡矩阵

小美拿到了一个 n∗n 的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个 i∗i 的完美矩形区域。你需要回答 1≤i≤n 的所有答案。

输入描述：

plaintext
1
2
3
第一行输入一个正整数n，代表矩阵大小。
接下来的n行，每行输入一个长度为n的 01 串，用来表示矩阵。
1\leq n \leq 200

输出描述：

plaintext
1
输出n行，第i行输出i*i的完美矩形区域的数量。

实例

plaintext
1
2
3
4
5
6
7
8
9
10
11
输入例子：
4
1010
0101
1100
0011
输出例子：
0
7
0
1

解题思路

  1. 前缀和计算：我们需要构建一个二维数组来保存从 (0,0) 到 (i,j) 的区域中 1 和 0 的数量之差。这样我们就可以通过矩形区域的差值来判断是否为完美矩形。
  2. 矩形枚举：通过枚举不同尺寸的矩形，检查每个矩形区域内 1 和 0 的数量是否相等。

Java 实现

java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.Scanner;

public class PerfectRectangle {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();  // 读取换行符

        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            for (int j = 0; j < n; j++) {
                matrix[i][j] = line.charAt(j) - '0';
            }
        }

        // 前缀和数组，存储1和0的差值
        int[][] diff = new int[n + 1][n + 1];

        // 计算前缀和：diff[i][j] 表示从 (0,0) 到 (i-1,j-1) 的1和0的差值
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                int val = matrix[i - 1][j - 1] == 1 ? 1 : -1;
                diff[i][j] = diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1] + val;
            }
        }

        // 计算每个尺寸的完美矩形数量
        for (int size = 1; size <= n; size++) {
            int count = 0;

            for (int i = size; i <= n; i++) {
                for (int j = size; j <= n; j++) {
                    int total = diff[i][j] - diff[i - size][j] - diff[i][j - size] + diff[i - size][j - size];
                    if (total == 0) {
                        count++;
                    }
                }
            }

            System.out.println(count);
        }
    }
}

详细解释

  1. 前缀和差值矩阵 diff：diff[i][j] 表示从左上角到 (i-1, j-1) 的矩形区域中，1 和 0 的数量差值。我们使用 1 表示 1，使用 -1 表示 0，因此如果某个子矩形区域的差值为 0，说明这个区域内 1 和 0 的数量相等，即为一个完美矩形。

  2. 矩形枚举：对于每个尺寸 size 的矩形，我们遍历所有可能的起点 (i, j)，通过前缀和差值快速计算出矩形内的 1 和 0 的数量。如果差值为 0，则这个矩形为完美矩形。