当前位置：首页 > news >正文

美团2024年春招第一场笔试【前端移动端方向】编程题题解Java

news 2025/7/23 16:30:57

1、小美的平衡矩阵

在这里插入图片描述
前缀和，时间复杂度为O(n^3)

对于每个矩形，已知边长k，只用每次遍历矩形的左上顶点，就可以确定整个矩形范围。
然后统计该矩形中01的具体数量，判断是否相等。而这一步可以使用前缀和，建立数组sum[n+1][n+1]，来统计矩形(1,1)到(n,m)中1的数量。
对于左上顶点(i, j)的矩阵，右下顶点即为(x, y), 其中x=i+k-1,y=j+k-1。
则字符1的数量即为sum[x][y] - sum[x][ j-1] - sum[i-1][y] + sum[ i - 1 ][ j - 1]，字符0的数量为 k*k/2。
特别判断，当矩形边长k为奇数时，矩形内有k*k个点，也是奇数，所以肯定不满足0、1的个数相等，这个是需要特殊判断的。

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[][] sum = new int[n+1][n+1];for(int i = 1; i <= n; i++){char[] ch = in.next().toCharArray();for(int j = 1; j<= n;j++){sum[i][j] = sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+(ch[j-1]-'0');}}for(int k = 1; k <= n; k++){if((k&1) == 1){ // 使用位运算效率高些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, y = j+k-1;if(sum[x][y] - sum[i-1][y] - sum[x][j-1] + sum[i-1][j-1] == k*k/2)ans++;}}System.out.println(ans);}}
}

2、小美的数组询问

在这里插入图片描述
这题很简单，统计0的个数即可，注意使用long类型防止溢出。

import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);long n = in.nextInt();long q = in.nextInt();long cnt = 0;long sum = 0;for(int i = 0;i < n;i++){long x = in.nextInt();if(x == 0)cnt++;sum += x;}while(q > 0){q--;long s = in.nextInt();long t = in.nextInt();long x = sum+cnt*s, y = sum+cnt*t;System.out.println(x + " " + y);}in.close();}
}