【美团20240309笔试算法题】小美的完美矩阵

系列文章目录

【美团20240309笔试算法题】小美的MT
【美团20240309笔试算法题】小美的数组询问

目录

• 系列文章目录
• 小美的完美矩阵
• • 样例
  • 分析
  • java代码参考

小美的完美矩阵

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

样例

输入：

• 第一行输入一个正整数n，代表矩阵大小。
• 接下来的n行，每行输入一个长度为n的01 串，用来表示矩阵。

4
1010
0101
1100
0011

输出：

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

0
7
0
1

分析

思路是使用二维前缀和求出每个子矩阵的值，如果值等于矩阵面积i*i的一半，说明0 和 1各占一半。
关于什么是二维前缀和，可以参考这篇文章：【算法】一维前缀和以及二维前缀和

java代码参考

package org.example;

import javax.sound.midi.Soundbank;
import javax.xml.transform.Source;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); //n * n的矩阵
        char[][] a = new char[n + 1][n + 1]; //构造矩阵，这里让矩阵从a[1][1]开始填充，所以矩阵总长度设为n+1
        int[][] s = new int[n + 1][n + 1]; //构造二维前缀和
        //构造矩阵和二维前缀和
        for (int i = 1; i <= n; i++) {
            String line = sc.next(); //题目中每行输入一个数字序列，中间没有空格，所以当做字符串来处理
            for (int j = 1; j <= n; j++) {
                a[i][j] = line.charAt(j - 1);
                int value = a[i][j] == '1' ? 1 : 0;
                s[i][j] = s[i - 1][j] + s[i][j - 1] + value - s[i - 1][j - 1];
            }
        }
        //计算完美矩形区域的数量
        for (int len = 1; len <= n; len++) {
            int cnt = 0;
            //x,y分别代表子矩阵的左上端点，对应右下角的端点则为(x+len-1,y+len -1)
            for (int x = 1; x <= (n - len + 1); x++) {
                for (int y = 1; y <= (n - len + 1); y++) {
                    int sum = s[x + len - 1][y + len - 1] -s[x + len - 1][y - 1] - s[x - 1][y + len - 1] + s[x - 1][y - 1];
                    if (sum * 2 == len * len) { //如果是完美矩阵，那么矩阵里的0的个数和1的个数一样，各一半
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);
        }
    }
}