T2 小美的平衡矩阵(25分) - 美团编程题 & 题解
考试平台: 牛客网
题目类型: 30道单选题(60分)+ 2 道编程题 (15分 + 25分)
考试时间: 2024-03-09 (两小时)
题目描述
小美拿到了一个n*n
的矩阵,其中每个元素是 0 或者 1。 小美认为一个矩形区域是完美的,当且仅当该区域内 0 的数量恰好等于 1 的数量。 现在,小美希望你回答有多少个i*i
的完美矩形区域。你需要回答的所有答案。
输入描述
第一行输入一个正整数n
,代表矩阵大小。 接下来的n
行,每行输入一个长度为n
的 01 串,用来表示矩阵。
输出描述
输出n
行,第i
行输出 i*i
的完美矩形区域的数量。
示例
输入:
4
1010
0101
1100
0011
输出:
0
7
0
1
题解
暴力枚举所有情况, 在暴力枚举的情况下使用前缀和优化检验 "是否是完美矩形区域" 的方法。
from collections import defaultdict
n = int(input())
grid = [input() for _ in range(n)]
# 前缀和 psum[r][i] 表示 grid[r][0:i] 中 “1” 的个数
psum = [[0] * (n+1) for _ in range(n)]
for r in ra
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
🔥笔试编程真题宝典💯 文章被收录于专栏
📕分享大厂机试真题深度剖析核心考点,助你速通面试。