牛客美团2024年春招第一场笔试【技术】解题

本文主要是介绍牛客美团2024年春招第一场笔试【技术】解题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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思路

前缀和

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