当前位置:   article > 正文

美团校招机试 - 小美的平衡矩阵(20240309-T1)_一个矩形区域是完美的,当且仅当该区域内 0 的数量恰好等于 1 的数量。

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

题目来源

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

题目描述

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

Java算法源码

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

Python算法源码

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

C算法源码

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

C++算法源码

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小桥流水78/article/detail/774808
推荐阅读
相关标签
  

闽ICP备14008679号