美团校招机试 - 小美的平衡矩阵（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)算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  const n = parseInt(await readline());

  const matrix = [];
  for (let i = 0; i < n; i++) {
    matrix.push(await readline());
  }

  // 二维数组前缀和
  // dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
  const dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(0));
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= n; j++) {
      // 此处公式请看图示说明
      dp[i][j] =
        parseInt(matrix[i - 1][j - 1]) +
        dp[i - 1][j] +
        dp[i][j - 1] -
        dp[i - 1][j - 1];
    }
  }

  // i 表示正方形边长
  for (let i = 2; i <= n; i += 2) {
    // i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
    console.log(0);

    // i 为偶数时
    let count = 0; // 记录01平衡的i*i正方形数量
    for (let r = i; r <= n; r++) {
      for (let c = i; c <= n; c++) {
        // 正方形中1的数量
        const oneCount =
          dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i];

        // 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
        if (oneCount * 2 == i * i) {
          count++;
        }
      }
    }
    console.log(count);
  }

  // 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
  if (n % 2 != 0) {
    console.log(0);
  }
})();

Java算法源码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = Integer.parseInt(sc.nextLine());

        char[][] matrix = new char[n][n];
        for (int i = 0; i < n; i++) {
            matrix[i] = sc.nextLine().toCharArray();
        }

        // 二维数组前缀和
        // dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
        int[][] dp = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                // 此处公式请看图示说明
                dp[i][j] = (matrix[i - 1][j - 1] - '0') + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
            }
        }

        // i 表示正方形边长
        for (int i = 2; i <= n; i += 2) {
            // i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
            System.out.println(0);

            // i 为偶数时
            int count = 0; // 记录01平衡的i*i正方形数量
            for (int r = i; r <= n; r++) {
                for (int c = i; c <= n; c++) {
                    // 正方形中1的数量
                    int oneCount = dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i];

                    // 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
                    if (oneCount * 2 == i * i) {
                        count++;
                    }
                }
            }
            System.out.println(count);
        }

        // 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
        if (n % 2 != 0) {
            System.out.println(0);
        }
    }
}

Python算法源码

# 输入获取
n = int(input())
matrix = [input() for _ in range(n)]

# 核心代码
if __name__ == '__main__':
    # 二维数组前缀和
    # dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
    dp = [[0] * (n + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, n + 1):
            # 此处公式请看图示说明
            dp[i][j] = int(matrix[i - 1][j - 1]) + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]

    # i 表示正方形边长
    for i in range(2, n + 1, 2):
        # i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
        print(0)

        # i 为偶数时
        count = 0  # 记录01平衡的i*i正方形数量
        for r in range(i, n + 1):
            for c in range(i, n + 1):
                # 正方形中1的数量
                oneCount = dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i]

                # 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
                if oneCount * 2 == i * i:
                    count += 1

        print(count)

    # 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
    if n % 2 != 0:
        print(0)

C算法源码

#include <stdio.h>

#define MAX_SIZE 201

int main() {
    int n;
    scanf("%d", &n);

    char matrix[MAX_SIZE][MAX_SIZE] = {'\0'};
    for (int i = 0; i < n; i++) {
        scanf("%s", matrix[i]);
    }

    // 二维数组前缀和
    // dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
    int dp[MAX_SIZE][MAX_SIZE] = {0};
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 此处公式请看图示说明
            dp[i][j] = (matrix[i - 1][j - 1] - '0') + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
        }
    }

    // i 表示正方形边长
    for (int i = 2; i <= n; i += 2) {
        // i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
        puts("0");

        // i 为偶数时
        int count = 0; // 记录01平衡的i*i正方形数量
        for (int r = i; r <= n; r++) {
            for (int c = i; c <= n; c++) {
                // 正方形中1的数量
                int oneCount = dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i];

                // 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
                if (oneCount * 2 == i * i) {
                    count++;
                }
            }
        }
        printf("%d\n", count);
    }

    // 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
    if (n % 2 != 0) {
        puts("0");
    }

    return 0;
}

C++算法源码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<string> matrix(n);
    for (int i = 0; i < n; i++) {
        cin >> matrix[i];
    }

    // 二维数组前缀和
    // dp[i][j] 表示matrix矩阵中以 (i-1, j-1) 位置为右下角点的矩形中1的数量
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 此处公式请看图示说明
            dp[i][j] = (matrix[i - 1][j - 1] - '0') + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
        }
    }

    // i 表示正方形边长
    for (int i = 2; i <= n; i += 2) {
        // i 为奇数时, 则对应 i*i 正方形面积也为奇数, 不可能平分, 所以不存在01平衡的
        cout << 0 << endl;

        // i 为偶数时
        int count = 0; // 记录01平衡的i*i正方形数量
        for (int r = i; r <= n; r++) {
            for (int c = i; c <= n; c++) {
                // 正方形中1的数量
                int oneCount = dp[r][c] - dp[r][c - i] - dp[r - i][c] + dp[r - i][c - i];

                // 如果正方形中1的数量 == 正方形面积的一半，则形成01平衡
                if (oneCount * 2 == i * i) {
                    count++;
                }
            }
        }

        cout << count << endl;
    }

    // 如果 n 是奇数，则上面for循环会遗漏 n*n 正方形的01平衡判断
    if (n % 2 != 0) {
        cout << 0 << endl;
    }

    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/759293.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

C++操作系列(二)：VSCode安装和配置C++开发环境

C++操作系列(二)：VSCode安装和配置C++开发环境

1. VSCode下载 进入VSCode的官网网页&#xff1a;Download Visual Studio Code - Mac, Linux, Windows 下载相应的版本&#xff1a; 2. 安装VSCode 安装到指定位置&#xff1a; 一路下一步&#xff0c;直至安装完成&#xff1a; 3. 安装C插件 3.1. 安装C/C 点击扩展图标&…
阅读更多...
linux上git的使用

linux上git的使用

目录 1.测试是否安装有git 2.下载项目到本地 3.三板斧 1.将代码放在创建的目录中 2.提交改动到本地 3.提交代码到远端 4.注意点 以及补充内容 1.测试是否安装有git 如果输入git --help 会显示下面一大串那么就是已经安装&#xff0c;否则需要自行手动安装 yum install g…
阅读更多...
Elasticsearch开启认证|为ES设置账号密码|ES账号密码设置|ES单机开启认证|ES集群开启认证

Elasticsearch开启认证|为ES设置账号密码|ES账号密码设置|ES单机开启认证|ES集群开启认证

文章目录 前言单节点模式开启认证生成节点证书修改ES配置文件为内置账号添加密码Kibana修改配置验证 ES集群开启认证验证 前言 ES安装完成并运行&#xff0c;默认情况下是允许任何用户访问的&#xff0c;这样并不安全&#xff0c;可以为ES开启认证&#xff0c;设置账号密码。 …
阅读更多...
【Python从入门到进阶】59、Pandas库中Series对象的操作(二)

【Python从入门到进阶】59、Pandas库中Series对象的操作(二)

接上篇《58、Pandas库中Series对象的操作(一)》 上一篇我们讲解了Pandas库中Series对象的基本概念、对象创建和操作&#xff0c;本篇我们来继续学习Series对象的运算、函数应用、时间序列操作&#xff0c;以及Series的案例实践。 一、Series对象的运算 1. 数值型数据的算术运…
阅读更多...
ElasticSearch索引架构与存储

ElasticSearch索引架构与存储

关于ES官网的介绍: Elasticsearch provides near real-time search and analytics for all types of data. Whether you have structured or unstructured text, numerical data, or geospatial data, Elasticsearch can efficiently store and index it in a way that support…
阅读更多...
详细介绍MySQL的索引（下）

详细介绍MySQL的索引（下）

索引的使用 同一条数据在未创建索引的情况下耗时&#xff1a; nick字段是未创建索引的 select * from t_user WHERE nick 邹丽;SHOW PROFILES; 耗时为&#xff1a; user_account字段创建了唯一索引 select * from t_user WHERE user_account 13781945844;SHOW PROFILES;…
阅读更多...
基于Vue3 + Typescript 封装 Element-Plus 组件

基于Vue3 + Typescript 封装 Element-Plus 组件

1. 课程简介 项目地址 git clone https://gitee.com/childe-jia/my-message.git 背景: 该课程是基于Vue3 Typescript Vite构建, 教会大家封装Element-Plus组件 具备能力: 最新的 Vue3 及相关技术组件的设计思想大厂的开发模式/代码规范 技术: Vue3 首次渲染 / diff 算法 …
阅读更多...
5-linux文件路径与文件目录系统

5-linux文件路径与文件目录系统

目录 ①文件路径 目录跳转 绝对路径与相对路径 ②文件目录系统 目录系统组成 目录命名规则 命令补充 ls命令补充 file filename查看文件类型 less查看文本文件 ①文件路径 目录跳转 pwd:查看当前工作目录。 cd:改变目录。 ls:列出目录内容。 [root########## ~]# …
阅读更多...
取证工作：怎样解锁 LUKS2 加密磁盘？

取证工作：怎样解锁 LUKS2 加密磁盘？

对于 LUKS2 密码进行恢复&#xff0c;Elcomsoft Distributed Password Recovery &#xff08;简称 EDPR&#xff09; 软件可以构建高性能集群&#xff0c;以更快地破解密码。EDPR 软件提供零开销的可扩展性&#xff0c;并支持 GPU 加速&#xff0c;以加快恢复速度。EDPR 可帮助…
阅读更多...
下属无执行力，领导无能为力？用好这3大法则，打造一流行动力

下属无执行力，领导无能为力？用好这3大法则，打造一流行动力

下属无执行力&#xff0c;领导无能为力&#xff1f;用好这3大法则&#xff0c;打造一流行动力 第一个&#xff1a;漏斗法则 在沟通这个领域&#xff0c;有一个漏斗法则&#xff0c;意思就是指&#xff1a;如果你脑袋里面想表达的是100%&#xff0c;那你说出口的会只有80%&…
阅读更多...
开发板以电脑为跳板连接互联网

开发板以电脑为跳板连接互联网

标题 开发板以电脑为跳板连接互联网网络共享方式桥接方式 开发板以电脑为跳板连接互联网 分享下用网线直连电脑的开发板如何以电脑为跳板连接互联网的两个方法。 网络共享方式桥接方式 补充下&#xff0c;我的电脑连接的是无线网络&#xff0c;开发板和电脑是用网线进行连接的…
阅读更多...
AI奏响未来乐章：音乐界的革命性变革

AI奏响未来乐章：音乐界的革命性变革

AI在创造还是毁掉音乐 引言 随着科技的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;正在逐渐渗透到我们生活的每一个角落&#xff0c;音乐领域也不例外。AI技术的引入&#xff0c;不仅为音乐创作、教育、体验带来了革命性的变革&#xff0c;更为整个音乐产业注入了…
阅读更多...
昇思25天学习打卡营第7天|模型训练

昇思25天学习打卡营第7天|模型训练

模型训练 模型训练一般分为四个步骤&#xff1a; 构建数据集。定义神经网络模型。定义超参、损失函数及优化器。输入数据集进行训练与评估。 前面几天依次学习了前面几个步骤的操作&#xff0c;今天继续学习模型训练。 数据集和神经网络模型这个前面已经有详细的介绍。准确…
阅读更多...
生成式AI如何赋能教育？商汤发布《2024生成式AI赋能教育未来》白皮书

生成式AI如何赋能教育？商汤发布《2024生成式AI赋能教育未来》白皮书

生成式AI正在各个行业中展现出巨大的应用前景。在关系国计民生的教育行业&#xff0c;生成式AI能够催生哪些创新模式&#xff1f; 6月28日&#xff0c;商汤科技受邀参加2024中国AIGC应用与发展峰会&#xff0c;并在会上发布《2024生成式AI赋能教育未来》白皮书&#xff0c;提出…
阅读更多...
Qt：5.QWidget属性介绍(isEnabled和geometry)

Qt：5.QWidget属性介绍(isEnabled和geometry)

目录 一、 QWidget属性的介绍&#xff1a; 二、Enabled属性&#xff1a; 2.1Enabled属性的介绍&#xff1a; 2.2获取控件当前可用状态的api——isEnabled()&#xff1a; 2.3设置控件当前的可用状态的api—— setEnabled() &#xff1a; 2.4 实例&#xff1a;通过一个按钮&…
阅读更多...
【人工智能学习之图像操作（六）】

【人工智能学习之图像操作（六）】

【人工智能学习之图像操作&#xff08;六&#xff09;】 Hough变换直线检测圆检测 图像分割 Hough变换 在图像处理中&#xff0c;霍夫变换用来检测任意能够用数学公式表达的形状&#xff0c;即使这个形状被破坏或者有点扭曲 直线检测 import cv2 import numpy as np image …
阅读更多...
Python 基础：用 json 模块存储和读取数据

Python 基础：用 json 模块存储和读取数据

目录 一、用 json 存储数据二、用 json 读取数据 遇到看不明白的地方&#xff0c;欢迎在评论中留言呐&#xff0c;一起讨论&#xff0c;一起进步&#xff01; 本文参考&#xff1a;《Python编程&#xff1a;从入门到实践&#xff08;第2版&#xff09;》 用户关闭程序时&#…
阅读更多...
Redux实现Token持久化

Redux实现Token持久化

业务背景: Token数据具有一定的时效时间&#xff0c;通常在几个小时&#xff0c;有效时间内无需重新获取&#xff0c;而基于Redux的存储方式又是基于内存的&#xff0c;刷新就会丢失&#xff0c;为了保持持久化&#xff0c;我们需要单独做处理 解决方案&#xff1a; 使用redu…
阅读更多...
HTML图片链接缓存问题解决

HTML图片链接缓存问题解决

关于解决HTML使用图片链接出现的缓存问题处理 1、项目上明明替换了图片却没发现更新&#xff0c;得去浏览器设置清除浏览器缓存或者其它一些操作才能解决&#xff0c;这也太麻烦了&#xff01;加载过一次不会再加载第二次&#xff0c;其实这时候就存在浏览器图片缓存情况&…
阅读更多...
1-5题查询 - 高频 SQL 50 题基础版

1-5题查询 - 高频 SQL 50 题基础版

目录 1. 相关知识点2. 例题2.1.可回收且低脂的产品2.2.寻找用户推荐人2.3.大的国家2.4. 文章浏览 I2.5. 无效的推文 1. 相关知识点 sql判断&#xff0c;不包含null&#xff0c;判断不出来distinct是通过查询的结果来去除重复记录ASC升序计算字符长度 CHAR_LENGTH() 或 LENGTH(…
阅读更多...
最新文章

Copyright @ 2022~2023