牛客美团2024年春招第一场笔试【技术】解题_输出n行,第i行输出i*i的完美矩形区域的数量。

1.小美的平衡矩阵

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

输出描述：
输出n行，第i行输出i*i的完美矩形区域的数量
例子：
输入例子：
4
1010
0101
1100
0011
输出例子：
0
7
0
1

1.1解题思路

1.1.1条件：

1.通过题目我们知道0和1相等才是完美矩形区域，所以我们只需求出矩阵的1的个数就可以了，这时我们可以想到前缀和（专门求矩阵的和）
2.第i行输出i*i的完美矩形区域的数量，得知到这个是确定矩阵边长大小，边长范围是1到n，边长奇数的一定不可能0和1相等

1.2思路

前缀和

1. 构建前缀和矩阵：建立数组 S [ n ] [ m ] 来统计矩形 ( 1 , 1 ) 到(n,m) 中1 的数量左上矩阵，只用每次遍历矩形的左上定点，就可以确定整个矩形大小
2. 然后统计该矩形中 01 的具体数量，判断是否相等，左上顶点 ( i , j ) 的矩阵，右下顶点即为 ( x , y ) ，其中 x = i + k − 1 , y = j + k − 1
3. 字符 1 的数量即为 s [ x ] [ y ] − s [ i − 1 ] [ y ] − s [ x ] [ j − 1 ] + s [ i − 1 ] [ j − 1 ]，字符 0 的数量为 k × k/ 2
   

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    static int n = 201;
    static int sum[][] = new int[n][n];
    static int a [][] = new int[n][n];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int row = in.nextInt();
        char[][] charArray = new char[row][];
        in.nextLine();
        // 循环读取每一行的字符串，并转换为字符数组
        for (int i = 0; i < row; i++) {
            String line = in.nextLine(); // 读取一行字符串
            charArray[i] =
                line.toCharArray(); // 将字符串转换为字符数组，并存储在二维数组中

        }
        for (int i = 0 ; i < row; i++) {
            for (int j = 0; j < row; j++) {
                a[i + 1][j + 1] = Integer.parseInt(Character.toString(charArray[i][j]));
                sum[i + 1][j + 1] = sum[i][j + 1] + sum[i + 1][j] + a[i + 1][j + 1] - sum[i][j];
            }
        }
        //k是边长
        for (int k = 1; k <= row; k++) {
            if ((k & 1) == 1) { // 当边长为奇数时
                System.out.println(0); // 字符 1的数量不可能等于字符 0的数量
                // 在循环中的话，这里应该是 continue; 
                continue;
            }
            int count = 0;
            for (int i = 1; i + k - 1 <= row ; i++ ) {
                for (int j = 1; j + k - 1 <= row ; j++) {
                    int x = i + k - 1;
                    int y = j + k - 1;
                    //核心部分
                    if (sum[x][y] - sum[i - 1][y] - sum[x][j - 1] + sum[i - 1][j - 1] ==
                            (k * k / 2)  ) {
                        count++;
                    }
                }
            }
            System.out.println(count);
        }

    }
}
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
46
47
48
49
50

2.小美的数组询问

小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间[