力扣随机一题 6/28 数组/矩阵
创始人
2024-12-27 16:08:35
0
  • 📝个人主页🌹:誓则盟约
  • ⏩收录专栏⏪:IT 竞赛
  • 🤡往期回顾🤡:6/27 每日一题
  • 关注博主,后期持续更新系列文章
  • 如果有错误感谢请大家批评指出,及时修改
  • 感谢大家点赞👍收藏⭐评论✍ 

 

目录:

 

3195.包含所有1的最小矩形面积I【中等】

 题目描述:

题目分析:

代码实现:

总结:

“山外青山楼外楼,西湖歌舞几时休?”——《题临安邸》


3195.包含所有1的最小矩形面积I【中等】

 题目描述:

给你一个二维 二进制 数组 grid。请你找出一个边在水平方向和竖直方向上、面积 最小 的矩形,并且满足 grid 中所有的 1 都在矩形的内部。

返回这个矩形可能的 最小 面积。

示例 1:

输入: grid = [[0,1,0],[1,0,1]]

输出: 6

解释:

这个最小矩形的高度为 2,宽度为 3,因此面积为 2 * 3 = 6 

示例 2:

输入: grid = [[0,0],[1,0]]

输出: 1

解释:

 

这个最小矩形的高度和宽度都是 1,因此面积为 1 * 1 = 1

提示:

  • 1 <= grid.length, grid[i].length <= 1000
  • grid[i][j] 是 0 或 1。
  • 输入保证 grid 中至少有一个 1 。

 

题目分析:

        求矩形面积,也就是在找最左边的1的列号firstCol,最右边的1列号lastCol,最上面1的行号firstRow,最下面1的行号lastRow。

        那么面积就是  (lastRow-firstRow+1)*(lastCol-firstCol+1)

        遍历矩阵,分别找第一列,最后一列,第一行,最后一行出现1的数据,然后计算求结果。

代码实现:

class Solution:     def minimumArea(self, grid: List[List[int]]) -> int:         rowNums = len(grid)         colNums = len(grid[0])         firstRow = -1         firstCol = -1         lastRow = -1         lastCol = -1         for row in range(rowNums):             if firstRow==-1:                 for col in range(colNums):                     if grid[row][col]==1:                         if firstRow==-1:                             firstRow=row                             break          for col in range(colNums):             if firstCol==-1:                 for row in range(rowNums):                     if grid[row][col]==1:                         if firstCol==-1:                             firstCol=col                             break          for row in range(rowNums-1,-1,-1):             if lastRow==-1:                 for col in range(colNums-1,-1,-1):                     if grid[row][col]==1:                         if lastRow==-1:                             lastRow=row                             break          for col in range(colNums-1,-1,-1):             if lastCol==-1:                 for row in range(rowNums-1,-1,-1):                     if grid[row][col]==1:                         if lastCol==-1:                             lastCol=col                             break          value = (lastRow-firstRow+1)*(lastCol-firstCol+1)         return value


 

总结:

详解

  1. 首先,定义了网格的行数 rowNums 和列数 colNums 。
  2. 然后,通过四个循环分别找到值为 1 的单元格首次出现的行 firstRow 和列 firstCol ,以及最后出现的行 lastRow 和列 lastCol 。
    • 在第一个循环中,从第一行开始逐行查找,当找到第一个值为 1 的单元格时,记录其所在的行 firstRow ,并结束内层循环。
    • 第二个循环类似,从第一列开始逐列查找,记录第一个值为 1 的单元格所在的列 firstCol 。
    • 第三个循环从最后一行开始逐行向前查找,记录最后一个值为 1 的单元格所在的行 lastRow 。
    • 第四个循环从最后一列开始逐列向前查找,记录最后一个值为 1 的单元格所在的列 lastCol 。
  3. 最后,根据找到的边界计算最小矩形区域的面积 value ,公式为 (lastRow - firstRow + 1) * (lastCol - firstCol + 1) 。

考点

  1. 对二维数组的遍历和操作。
  2. 循环的使用和条件判断。
  3. 如何确定一个区域的边界。

收获

  1. 加深对二维数组操作的理解,包括如何遍历和根据特定条件获取相关信息。
  2. 学会通过多个循环和条件判断来确定一个区域的边界,并计算其相关属性(如面积)。
  3. 提高在解决实际问题时,对问题进行分析和转化为代码实现的能力。

“山外青山楼外楼,西湖歌舞几时休?”——《题临安邸》

相关内容

热门资讯

八分钟攻略!中至窝龙必赢攻略,... 八分钟攻略!中至窝龙必赢攻略,aaPOKER都是有挂,教你攻略(有挂详情);1)中至窝龙必赢攻略辅助...
四分钟攻略!中至吉安王炸输赢,... 四分钟攻略!中至吉安王炸输赢,鱼扑克app俱乐部真是真的有挂,规律教程(有挂详情)1、全新机制【中至...
2分钟了解!宁波竞技馆有挂吗,... 2分钟了解!宁波竞技馆有挂吗,wepOke总是存在有挂,揭秘教程(有挂ai代打);1、宁波竞技馆有挂...
八分钟辅助挂!喜扣打筒子辅助器... 八分钟辅助挂!喜扣打筒子辅助器,聚星扑克德州真是是有挂,辅助教程(有挂技巧);1、喜扣打筒子辅助器系...
八分钟发现!正版欢乐达人辅助工... 八分钟发现!正版欢乐达人辅助工具,鱼扑克app俱乐部都是是有挂,黑科技教程(有挂解说)1)正版欢乐达...
八分钟发现!山西大唐麻将输赢设... 八分钟发现!山西大唐麻将输赢设置,聚星扑克果然有挂,wepoke教程(有挂黑科技)1、上手简单,内置...
十分钟发现!哈灵辅助神器ios... 十分钟发现!哈灵辅助神器ios,wepokE都是真的是有挂,教你攻略(有挂解说)进入游戏-大厅左侧-...
4分钟辅助!皇豪互娱辅助器下载... 4分钟辅助!皇豪互娱辅助器下载,扑克世界原来真的是有挂,AA德州教程(有挂解说)1、超多福利:超高返...
8分钟普及!揭秘哈局十三张赢牌... 8分钟普及!揭秘哈局十三张赢牌秘诀,wEpOke真是是真的有挂,细节方法(有挂普及);1)揭秘哈局十...
3分钟辅助!微信上的广东雀神麻... 3分钟辅助!微信上的广东雀神麻将有挂吗,wepoKE真是是真的有挂,微扑克教程(有挂辅助);1、这是...