• 美团校招机试 - 小美的平衡矩阵（20240309-T1）

    题目来源

    美团校招笔试真题_小美的平衡矩阵

    题目描述

    小美拿到了一个 n * n  的矩阵，其中每个元素是 0 或者 1。

    小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。

    现在，小美希望你回答有多少个 i * i 的完美矩形区域。你需要回答 1 ≤ i ≤ n 的所有答案。

    输入描述

    第一行输入一个正整数 n，代表矩阵大小。

    • 1 ≤ n ≤ 200

    接下来的 n 行，每行输入一个长度为 n 的 01 串，用来表示矩阵。

    输出描述

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

    用例

    输入4
    1010
    0101
    1100
    0011
    输出0
    7
    0
    1
    说明无

    题目解析

    本题需要我们求解 i * i 的完美矩形区域的数量，i 取值 1~n.

    完美矩形区域：当且仅当该区域内 0 的数量恰好等于 1 的数量

    比如下图中黄色部分是一个 2x2 的矩形区域，其中01数量相等，因此是一个完美矩形区域

    因此，本题的关键其实是，求解输入矩阵中，任意 i * i 正方形区域中 '1' 的数量oneCount，如果满足： oneCount * 2 == i * i，则对应正方形区域是完美的。

    那么，如何求解输入矩阵中，任意正方形区域中 '1' 的数量呢？

    我们可以基于“二维数组前缀和”的知识来求解。

    假设 dp[i][j] 表示输入矩阵中以 (0,0)为左上角点，(i,j)为右下角点的矩形中 '1' 的数量。

    比如上图中，dp[1][1] = 2，即以(0,0)为左上角点，(1,1)为左下角点的矩形中 '1' 的数量为 2。

    下图中红色区域1的数量存在关系如下：

    其中橙色区域 是 绿色和蓝色区域的重叠区域，为了避免重复计算，所以要减去。

    即存在状态转移方程如下：

    dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + (matrix[i][j] == '1' ? 1 : 0)

    上面状态转移方程求解i=0, j=0的右下角位置矩形时，会发生越界异常，

    因此我们定义dp二维数组时，需要将dp矩阵的行数、列数都定义为n+1。dp矩阵的第一行和第一列初始为0。

    之后，我们就可以遍历dp中所有正方形，然后基于dp来求解正方形中1的数量。比如下图中：

    我们要求解：边长为 i=2，右下角位置 (r=3, c=2) 的正方形中 '1' 的数量，则有公式如下：

    dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i]

    公式可以对照下图理解： 

    JS(Node)算法源码

    1. const rl = require("readline").createInterface({ input: process.stdin });
    2. var iter = rl[Symbol.asyncIterator]();
    3. const readline = async () => (await iter.next()).value;
    4.  
    5. void (async function () {
    6.   const n = parseInt(await readline());
    7.  
    8.   const matrix = [];
    9.   for (let i = 0; i < n; i++) {
    10.     matrix.push(await readline());
    11.   }
    12.  
    13.   // 二维数组前缀和
    14.   // dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
    15.   const dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
    16.   for (let i = 1; i <= n; i++) {
    17.     for (let j = 1; j <= n; j++) {
    18.       // 此处公式请看图示说明
    19.       dp[i][j] =
    20.         parseInt(matrix[i - 1][j - 1]) +
    21.         dp[i - 1][j] +
    22.         dp[i][j - 1] -
    23.         dp[i - 1][j - 1];
    24.     }
    25.   }
    26.  
    27.   // i 表示正方形边长
    28.   for (let i = 2; i <= n; i += 2) {
    29.     // i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
    30.     console.log(0);
    31.  
    32.     // i 为偶数时
    33.     let count = 0; // 记录01平衡的i*i正方形数量
    34.     for (let r = i; r <= n; r++) {
    35.       for (let c = i; c <= n; c++) {
    36.         // 正方形中1的数量
    37.         const oneCount =
    38.           dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i];
    39.  
    40.         // 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
    41.         if (oneCount * 2 == i * i) {
    42.           count++;
    43.         }
    44.       }
    45.     }
    46.     console.log(count);
    47.   }
    48.  
    49.   // 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
    50.   if (n % 2 != 0) {
    51.     console.log(0);
    52.   }
    53. })();

    Java算法源码

    1. import java.util.Scanner;
    2.  
    3. public class Main {
    4.     public static void main(String[] args) {
    5.         Scanner sc = new Scanner(System.in);
    6.  
    7.         int n = Integer.parseInt(sc.nextLine());
    8.  
    9.         char[][] matrix = new char[n][n];
    10.         for (int i = 0; i < n; i++) {
    11.             matrix[i] = sc.nextLine().toCharArray();
    12.         }
    13.  
    14.         // 二维数组前缀和
    15.         // dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
    16.         int[][] dp = new int[n + 1][n + 1];
    17.         for (int i = 1; i <= n; i++) {
    18.             for (int j = 1; j <= n; j++) {
    19.                 // 此处公式请看图示说明
    20.                 dp[i][j] = (matrix[i - 1][j - 1] - '0') + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    21.             }
    22.         }
    23.  
    24.         // i 表示正方形边长
    25.         for (int i = 2; i <= n; i += 2) {
    26.             // i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
    27.             System.out.println(0);
    28.  
    29.             // i 为偶数时
    30.             int count = 0; // 记录01平衡的i*i正方形数量
    31.             for (int r = i; r <= n; r++) {
    32.                 for (int c = i; c <= n; c++) {
    33.                     // 正方形中1的数量
    34.                     int oneCount = dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i];
    35.  
    36.                     // 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
    37.                     if (oneCount * 2 == i * i) {
    38.                         count++;
    39.                     }
    40.                 }
    41.             }
    42.             System.out.println(count);
    43.         }
    44.  
    45.         // 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
    46.         if (n % 2 != 0) {
    47.             System.out.println(0);
    48.         }
    49.     }
    50. }

    Python算法源码

    1. # 输入获取
    2. n = int(input())
    3. matrix = [input() for _ in range(n)]
    4.  
    5. # 核心代码
    6. if __name__ == '__main__':
    7.     # 二维数组前缀和
    8.     # dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
    9.     dp = [[0] * (n + 1) for _ in range(n + 1)]
    10.  
    11.     for i in range(1, n + 1):
    12.         for j in range(1, n + 1):
    13.             # 此处公式请看图示说明
    14.             dp[i][j] = int(matrix[i - 1][j - 1]) + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]
    15.  
    16.     # i 表示正方形边长
    17.     for i in range(2, n + 1, 2):
    18.         # i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
    19.         print(0)
    20.  
    21.         # i 为偶数时
    22.         count = 0  # 记录01平衡的i*i正方形数量
    23.         for r in range(i, n + 1):
    24.             for c in range(i, n + 1):
    25.                 # 正方形中1的数量
    26.                 oneCount = dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i]
    27.  
    28.                 # 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
    29.                 if oneCount * 2 == i * i:
    30.                     count += 1
    31.  
    32.         print(count)
    33.  
    34.     # 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
    35.     if n % 2 != 0:
    36.         print(0)

    C算法源码

    1. #include 
    2.  
    3. #define MAX_SIZE 201
    4.  
    5. int main() {
    6.     int n;
    7.     scanf("%d", &n);
    8.  
    9.     char matrix[MAX_SIZE][MAX_SIZE] = {'\0'};
    10.     for (int i = 0; i < n; i++) {
    11.         scanf("%s", matrix[i]);
    12.     }
    13.  
    14.     // 二维数组前缀和
    15.     // dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
    16.     int dp[MAX_SIZE][MAX_SIZE] = {0};
    17.     for (int i = 1; i <= n; i++) {
    18.         for (int j = 1; j <= n; j++) {
    19.             // 此处公式请看图示说明
    20.             dp[i][j] = (matrix[i - 1][j - 1] - '0') + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    21.         }
    22.     }
    23.  
    24.     // i 表示正方形边长
    25.     for (int i = 2; i <= n; i += 2) {
    26.         // i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
    27.         puts("0");
    28.  
    29.         // i 为偶数时
    30.         int count = 0; // 记录01平衡的i*i正方形数量
    31.         for (int r = i; r <= n; r++) {
    32.             for (int c = i; c <= n; c++) {
    33.                 // 正方形中1的数量
    34.                 int oneCount = dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i];
    35.  
    36.                 // 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
    37.                 if (oneCount * 2 == i * i) {
    38.                     count++;
    39.                 }
    40.             }
    41.         }
    42.         printf("%d\n", count);
    43.     }
    44.  
    45.     // 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
    46.     if (n % 2 != 0) {
    47.         puts("0");
    48.     }
    49.  
    50.     return 0;
    51. }

    C++算法源码

    1. #include 
    2. using namespace std;
    3.  
    4. int main() {
    5.     int n;
    6.     cin >> n;
    7.  
    8.     vector matrix(n);
    9.     for (int i = 0; i < n; i++) {
    10.         cin >> matrix[i];
    11.     }
    12.  
    13.     // 二维数组前缀和
    14.     // dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
    15.     vectorint>> dp(n + 1, vector<int>(n + 1, 0));
    16.     for (int i = 1; i <= n; i++) {
    17.         for (int j = 1; j <= n; j++) {
    18.             // 此处公式请看图示说明
    19.             dp[i][j] = (matrix[i - 1][j - 1] - '0') + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
    20.         }
    21.     }
    22.  
    23.     // i 表示正方形边长
    24.     for (int i = 2; i <= n; i += 2) {
    25.         // i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
    26.         cout << 0 << endl;
    27.  
    28.         // i 为偶数时
    29.         int count = 0; // 记录01平衡的i*i正方形数量
    30.         for (int r = i; r <= n; r++) {
    31.             for (int c = i; c <= n; c++) {
    32.                 // 正方形中1的数量
    33.                 int oneCount = dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i];
    34.  
    35.                 // 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
    36.                 if (oneCount * 2 == i * i) {
    37.                     count++;
    38.                 }
    39.             }
    40.         }
    41.  
    42.         cout << count << endl;
    43.     }
    44.  
    45.     // 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
    46.     if (n % 2 != 0) {
    47.         cout << 0 << endl;
    48.     }
    49.  
    50.     return 0;
    51. }

  • 相关阅读:
    QtCreator报大量未知标识符错误的解决方法
    sqli-labs/Less-58
    聊聊.NET Core处理全局异常有那些方法
    有限元编程示例
    java计算机毕业设计小区车辆管理系统源程序+mysql+系统+lw文档+远程调试
    【Java面试】Kafka 怎么避免重复消费
    three.js 汽车行驶动画效果
    java-php-python-ssm试卷审批系统计算机毕业设计
    易点易动固定资产管理系统：实现财务与OA系统的无缝对接，高效管理固定资产
    PageHelper详解
  • 原文地址：https://blog.csdn.net/qfc_128220/article/details/139889006