题解 # 二维矩阵最大矩形问题#
题目:
小明有一张N*M的方格纸,且部分小方格中涂了颜色,部分小方格还是空白。
给出N (2<Ns30)和M(2sMs30)的值,及每个小方格的状态((被涂了颜色小方格用数字1表示,空白小方格用数字0表示);
请帮助小明找出最大的矩形空白区域,并输出该矩形空白区域由多少个小方格组成。
例如:N=4, M=5,4*5的方格纸中每个小方格的状态如下图:
最大的空日区域由6个小方格组成(红色框区域)。
思路:
暴力穷举法:
1、将每一个方格的下边0的个数、右边0的个数进行统计
2、在由下边0的个数和右边0的个数以及该方格围城的矩形中,筛选出值是1的方格,进行0个数的回退。
3、将每一个方格的下标、下边0的个数,右边0的个数进行保存,最后再求最大的面积
4、如果这个方格里面是1则,从该方格出发是不能构成数据全部为0的矩形的,行刺可以直接将该方格的下边0和右边0的个数设置为0,排除即可。
5、最后查找 下边0的个数 >= 1 同时 右边0的个数也 >= 1的找到面积最大的矩形。
代码:
#include<stdio.h>
#define N 4
#define M 5
#define NUM (N*M)int main()
{int arr[N][M] = {{1,1,0,0,0},{1,0,1,0,0},{0,0,0,1,1},{0,0,0,1,0},};// 本例采用数组存储,因为有多个数组因此采用 二维数组方式int posArr[NUM][4]={0};// 先获取每一个数据// arr数据的行下标 int i;// arr数据的列下标 int j;printf("原始数组信息:\n");for(i=0;i<N;i++){for(j=0;j<M;j++){printf("%d ",arr[i][j]); }printf("\n");}// 查找下边0的临时下标 int k;// 查找右边0的临时下标 int t;// 下边0的个数 int bottom = 0;// 右边0的个数 int right = 0;// 存放最大矩形信息的下标。int maxI;// 最大矩形的面积 int maxArea;for(i=0;i<N;i++){for(j=0;j<M;j++){ // 如果该数据是1,不能构成以这个点为定点的矩形,则不需要向下和向右统计0的个数了 if(arr[i][j] != 0){posArr[i*M+j][0] = i; posArr[i*M+j][1] = j; posArr[i*M+j][2] = 0; posArr[i*M+j][3] = 0; continue;}// 如果该数据是0,可能构成 以这个点为定点的矩形bottom = 0;right = 0;// 查找下边0的个数;for(k=j+1;k<M;k++){if(arr[i][k] == 0){right++;}else{break;}} // 向右查找0的个数for(t=i+1;t<N;t++){if(arr[t][j] == 0){bottom++;}else{break;}} // 以行为准查找1,将不和要求的矩形排除掉,当前位置为i 和 j for(k=i+1;k<=i + bottom;k++){for(t=j;t<=j + right;t++){if(arr[k][t] == 1){if(k > t){bottom -= 1;}else if(k < t){right -= 1;}else{bottom -= 1;right -= 1;}}}} posArr[i*M+j][0] = i; posArr[i*M+j][1] = j; posArr[i*M+j][2] = bottom; posArr[i*M+j][3] = right; } } // 访问数据maxI = 0;maxArea=0; int tempArea = 0;for(i=0;i<NUM;i++){if(posArr[i][2] == 0 && posArr[i][3] != 0){tempArea = 1 * posArr[i][3];}if(posArr[i][2] != 0 && posArr[i][3] == 0){tempArea = 1 * posArr[i][2];}if(posArr[i][2] == 0 && posArr[i][3] == 0){tempArea = 1;}if(posArr[i][2] != 0 && posArr[i][3] != 0){tempArea = (posArr[i][2]+1) * (posArr[i][3]+1);}if(maxArea < tempArea){maxI = i;maxArea = tempArea;} } printf("最大矩形的信息:\n");printf("左上角的坐标点为:第%d行第%d列\n",posArr[maxI][0],posArr[maxI][1]);printf("宽:%d,高%d\n",posArr[maxI][3]+1,posArr[maxI][2]+1);printf("面积为:%d\n",(posArr[maxI][3]+1)*(posArr[maxI][2]+1));return 0;
}
效果演示:


拓展:
求正方形该代码也使用,查找 下方0个数和右边0个数一样的组合即可。
相关文章:
题解 # 二维矩阵最大矩形问题#
题目: 小明有一张N*M的方格纸,且部分小方格中涂了颜色,部分小方格还是空白。 给出N (2<Ns30)和M(2sMs30)的值,及每个小方格的状态((被涂了颜色小方格用数字1表示,空白小方格用数字0表示); 请…...
奔四的路上,依旧倔强的相信未来
本文首发于2022年12月31日 原标题: 奔四的路上,依旧倔强的相信未来!–我的2022年终总结 读大学那几年,一直保持着写日记和做计划的习惯,还记得大学毕业刚开始打工的时候,我的床头的墙上一定会画一张表,写上一个月的计划和一周的计划 计划也会有完不成的时候,但加深了…...
61 k8s + rancher + karmada容器化部署
文章目录 一、什么是rancher二、为什么使用rancher三、rancher安装1、细部介绍四、图形化操作1、执行2、补充五、 karmada1、官网2、细部介绍一、什么是rancher 1、Rancher 是一个 全栈式 的 Kubernetes 容器管理平台,为你提供在任何地方都能成功运行 Kubernetes 的工具。 二…...
Vue3的新特性变化,上手指南!
文章目录一、Vue3相比Vue2,更新了什么变化?二、Proxy 代理响应式原理三、组合式 API (Composition API)setup()函数:ref()函数reactive()函数组合式 setup 中使用 Props 父向子传递参数计算属性watch(数据监视)watchEffect&#x…...
OllyDbg
本文通过吾爱破解论坛上提供的OllyDbg版本为例,讲解该软件的使用方法 F2对鼠标所处的位置打下断点,一般表现为鼠标所属地址位置背景变红F3加载一个可执行程序,进行调试分析,表现为弹出打开文件框F4执行程序到光标处F5缩小还原当前…...
记一次键盘维修,最终修复
我的笔记本是华硕的K45VD,是我亲人在高二那年买的,之后就一直给我用,距今2023年已经差不多13年,它承载了太多记忆。在大学期间也给它升级,重要的零部件基本没问题。只在大学时加了8G内存和一个240G固态,换了…...
LeetCode 155.最小栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。实现 MinStack 类:MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int getMin(…...
C++学习笔记-重载运算符和重载函数
重载的运算符是带有特殊名称的函数,函数名是由关键字 operator 和其后要重载的运算符符号构成的。与其他函数一样,重载运算符有一个返回类型和一个参数列表。 C 允许在同一作用域中的某个函数和运算符指定多个定义,分别称为函数重载和运算符重…...
Java —— JDBC
引入mysql链接 创建表格 Navicat查看建表代码双击要打开的表,右侧顶端点击ddl小方框 CREATE TABLE s (id int(6) NOT NULL,name varchar(20) COLLATE utf8_bin DEFAULT NULL,age int(11) DEFAULT NULL,gender varchar(2) COLLATE utf8_bin DEFAULT NULL,dept var…...
备战金三银四,熬夜半个月汇集大厂 Java 岗 1600 页面试真题
如果你不停地加班。却很少冒险,也很少学习,那你极大可能会陷入到内卷中。 为什么这么说呢?我们先来捋清楚「内卷」的概念: 「内卷化」简而言之就是:日复一日,越混越掉坑里。 所谓内卷化,指一种…...
9、面向对象、泛型与反射
目录一、构造函数二、继承与重写三、泛型四、反射1 - 反射的基本概念2 - 反射的基础数据类型3 - 反射APIa - 获取Type类型b - 获取struct成员变量的信息c - 获取struct成员方法的信息d - 获取函数的信息e - 判断类型是否实现了某接口五、reflect.Valuea - 空value判断b - 获取V…...
Python使用百度通用API进行翻译
想汉化StarUML这个软件,感觉工作量太大,想要用Python自动翻译。 结果网上找的一个个用不了,或者用一会儿就断。 于是自己手写了一个简单的,只有两个类:APIConfig和Translater 使用 demo my_api_config APIConfig(…...
JavaScript 弹窗
文章目录JavaScript 弹窗警告框确认框提示框换行JavaScript 弹窗 可以在 JavaScript 中创建三种消息框:警告框、确认框、提示框。 警告框 警告框经常用于确保用户可以得到某些信息。 当警告框出现后,用户需要点击确定按钮才能继续进行操作。 语法 wi…...
408复试day1
文章目录数据结构计算机组成原理操作系统计算机网络数据结构 深度优先遍历DFS: 首先访问图中起始顶点v,然后由v出发,访问与v邻接且未被访问的顶点v1,再访问与v1相邻的且未被访问的顶点v2……重复上述过程。当不能再继续向下访问时…...
gdb openocd jlink arm-a9调试
连接关系是这样的:gdb —> openocd —>(这里需要两个xx.cfg配置文件) jlink —> arm-a9板子 具体流程是这样的: 给jlink(硬件调试器)安装驱动,用USB Driver Tool这个软件,…...
Leetcode Solutions - Part 2
1. Two Sum 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按…...
外盘国际期货:围观那些奇葩的国际节日?
围观那些奇葩的国际节日? 2月24日:世界讨厌香菜日,号召全世界所以讨厌香菜的人一起抵制香菜,2016年世界反香菜联盟 3月21日:世界睡眠日,唤起全民对睡眠重要性的认识,2001年国际精神卫生组织 …...
Kubernetes之服务的基本管理
svc是kubernetes最核心的概念,通过创建Service,可以为一组具有相同功能的容器应用提供一个统一的入口地址,并将请求进行负载分发到后端的各个容器应用上。pod生命周期短不稳定,pod异常后新生成的pod的IP会发生变化,通过…...
TimeWheel时间轮算法原理及实现(附源码)
时间轮算法原理及实现前言1.时间轮核心2.简单定时器3.任务队列4.优化任务队列5.简单时间轮6.多层时间轮前言 在各种业务场景中,我们总是会需要一些定时进行一些操作,这些操作可能是需要在指定的某个时间点操作,也可能是每过一个固定的时间间隔后进行操作,这就要求我们需要有一个…...
【蓝牙mesh】Upper协议层介绍
【蓝牙mesh】Upper协议层介绍 Upper层简介 Upper协议层用于处理网络层以上的功能,包括设备的应用层数据、安全、群组等信息,是实现蓝牙mesh应用功能的关键协议之一。Upper层接收来自Access层的数据或者是Upper层自己生成的Control数据,并且将…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
API网关Kong的鉴权与限流:高并发场景下的核心实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...
软件工程 期末复习
瀑布模型:计划 螺旋模型:风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合:模块内部功能紧密 模块之间依赖程度小 高内聚:指的是一个模块内部的功能应该紧密相关。换句话说,一个模块应当只实现单一的功能…...
【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统
Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...
ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...
图解JavaScript原型:原型链及其分析 | JavaScript图解
忽略该图的细节(如内存地址值没有用二进制) 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么:保存在堆中一块区域,同时在栈中有一块区域保存其在堆中的地址(也就是我们通常说的该变量指向谁&…...
算法—栈系列
一:删除字符串中的所有相邻重复项 class Solution { public:string removeDuplicates(string s) {stack<char> st;for(int i 0; i < s.size(); i){char target s[i];if(!st.empty() && target st.top())st.pop();elsest.push(s[i]);}string ret…...
【1】跨越技术栈鸿沟:字节跳动开源TRAE AI编程IDE的实战体验
2024年初,人工智能编程工具领域发生了一次静默的变革。当字节跳动宣布退出其TRAE项目(一款融合大型语言模型能力的云端AI编程IDE)时,技术社区曾短暂叹息。然而这一退场并非终点——通过开源社区的接力,TRAE在WayToAGI等…...
标注工具核心架构分析——主窗口的图像显示
🏗️ 标注工具核心架构分析 📋 系统概述 主要有两个核心类,采用经典的 Scene-View 架构模式: 🎯 核心类结构 1. AnnotationScene (QGraphicsScene子类) 主要负责标注场景的管理和交互 🔧 关键函数&…...
