leetcode 403周赛 包含所有1的最小矩形面积||「暴力」
3197. 包含所有 1 的最小矩形面积 II
题目描述:
给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形,并且满足 grid 中所有的 1 都在这些矩形的内部。
返回这些矩形面积之和的 最小 可能值。
注意,这些矩形可以相接。
1 < = g r i d . l e n g t h , g r i d [ i ] . l e n g t h < = 30 1 <= grid.length, grid[i].length <= 30 1<=grid.length,grid[i].length<=30
思路:
观察数据范围,n只有30,估计是 O ( n 4 ) O(n^4) O(n4)甚至是 O ( n 5 ) O(n^5) O(n5),所以要想办法暴力
我们只能做到 O ( n 2 ) O(n^2) O(n2)的方法去计算一个区域中用一个矩形覆盖的情况
所以要想办法只枚举两次就能把图形分割成三份,情况如下

写代码的时候要仔细,注意下标
class Solution {
public:int n, m, tr[35][35];int cal(int x1, int y1, int x2, int y2){bool fuck = 0;int x_max = 0, x_min = 1e9, y_max = 0, y_min = 1e9;for(int i = x1; i <= x2; ++i){for(int j = y1; j <= y2; ++j){if(tr[i][j]){fuck = 1;x_max = max(x_max, i);x_min = min(x_min, i);y_max = max(y_max, j);y_min = min(y_min, j);}}}if(fuck == 0)return 0;return (x_max - x_min + 1) * (y_max - y_min + 1);}int minimumSum(vector<vector<int>>& num) {n = num.size();m = num[0].size();for(int i = 1; i <= n; ++i){for(int j = 1; j <= m; ++j){tr[i][j] = num[i - 1][j - 1];}}int ans = 1e9;for(int i = 1; i <= n; ++i){for(int j = i + 1; j <= n; ++j){ans = min(ans, cal(1,1, i, m) + cal(i + 1, 1, j, m) + cal(j + 1, 1, n, m));}for(int j = 1; j <= m; ++j){ans = min(ans, cal(1, 1, i, j) + cal(i + 1, 1, n, j) + cal(1, j + 1, n, m));ans = min(ans, cal(1, 1, n, j) + cal(1, j + 1, i, m) + cal(i + 1, j + 1, n, m));ans = min(ans, cal(1, 1, i, j) + cal(1, j + 1, i, m) + cal(i + 1, 1, n, m));ans = min(ans, cal(1, 1, i, m) + cal(i + 1, 1, n, j) + cal(i + 1, j + 1, n, m));}}for(int i = 1; i <= m; ++i){for(int j = i + 1; j <= m; ++j){ans = min(ans, cal(1, 1, n, i) + cal(1, i + 1, n, j) + cal(1, j + 1, n, m));}}return ans;}
};
相关文章:
leetcode 403周赛 包含所有1的最小矩形面积||「暴力」
3197. 包含所有 1 的最小矩形面积 II 题目描述: 给你一个二维 二进制 数组 grid。你需要找到 3 个 不重叠、面积 非零 、边在水平方向和竖直方向上的矩形,并且满足 grid 中所有的 1 都在这些矩形的内部。 返回这些矩形面积之和的 最小 可能值。 注意…...
Stable Diffusion web UI 插件
2024.7.3更新,持续更新中 如果需要在linux上自己安装sd,参考:stable diffusion linux安装 插件复制到 /stable-diffusion-webui/extensions 目录下,然后重新启动sd即可 一、插件安装方法 每种插件的安装方法可能略有不同…...
深度学习中的反向传播算法的原理
深度学习中的反向传播算法的原理,以及如何计算梯度 反向传播算法(Backpropagation)是深度学习中最核心的优化技术之一,用于训练神经网络。它基于链式法则,通过从输出层逆向计算误差并逐层传递到输入层来更新模型参数&…...
身处奇瑞看三星:既“开卷“又“起火“,却更难受了
三星"起火" 这几天奇瑞的事情,让大家破防了,纷纷表示国内的就业市场环境普遍恶劣。 那我们转个眼,看看海外企业的情况。 最近一周,三星频频登上新闻,颇有"起火"之势。 在刚步入下半年的 7 月 1 日…...
系统架构设计师教程(清华第2版)<第1章 绪论>解读
系统架构设计师教程 第一章 绪论 1.1 系统架构概述1.1.1 系统架构的定义及发展历程1.1.2 软件架构的常用分类及建模方法1.1.3 软件架构的应用场景1.1.4 软件架构的发展未来1.2 系统架构设计师概述1.2.1 架构设计师的定义、职责和任务1.2.2 架构设计师应具备的专业素质1.3 如何成…...
Vue + Element UI + JSEncrypt实现简单登录页面
安装依赖 npm install jsencrypt --save局部引入 import JSEncrypt from jsencrypt/bin/jsencrypt;登录页面index.vue <template><div class"loginbody"><div class"logindata"><div class"logintext"><h2>Wel…...
从“关注流”到“时间线”,搜狐给内容加信任价值
文 | 螳螂观察 作者 | 易不二 在近日第十六季搜狐新闻马拉松活动中,搜狐新闻APP的“时间线”功能备受瞩目。不仅开幕式现场竖了一块“左手时间线,右手关注流”的路牌,张朝阳也着重强调了“时间线”产品的互动方式:“关注是基础&…...
vscode的一些使用问题
vscode使用技巧 1、快捷键(1)打开命令面板(2)注释(3)删除行(4)上下移动光标(5)光标回退(6)复制行(7)插入空白行…...
爬虫-网页基础
HTML 基本语法 HTML:Hyper Text Markup Language, 超文本标记语言,是计算机语言的一种,由元素构成。 p元素 <p>Web 真好玩!</p> 由三大部分组成 开始标签:一对尖括号中间包裹这元素名称元素内容&#x…...
保存huggingface缓存中AI模型(从本地加载AI模型数据)
在github下拉项目后,首次运行时会下拉一堆模型数据,默认是保存在缓存的,如果你的系统盘空间快满的时候就会被系统清理掉,每次运行又重新下拉一次,特别麻烦。 默认下载的缓存路径如下:C:\Users\用户名\.cache\huggingf…...
wps的xlsm和xltm和xlam格式的文件各有什么区别
文章目录 一、前言二、WPS表格文件格式介绍1. .xlsm 文件格式2. .xltm 文件格式3. .xlam 文件格式 三、总结 一、前言 本文将详细介绍WPS表格中三种常见的文件格式:.xlsm、.xltm、和.xlam,并提供通俗易懂的解释和示例,帮助用户理解它们的区别…...
软件性能测试有哪几种测试方法?专业性能测试报告出具
软件性能测试是指对软件系统在特定负载条件下的性能进行评估和验证的过程,目的是确保软件在正常使用的情况下能够满足用户的要求,并在稳定的性能水平下运行,在软件开发过程中起到了至关重要的作用,可以确保软件产品的质量和可靠性…...
JavaScript语言简介与实战应用:从零开始的编程之旅
JavaScript,一种轻量级的、解释型的、面向对象的脚本语言,自1995年由Netscape公司的Brendan Eich设计以来,迅速成为了Web开发中不可或缺的一部分。它不仅能够为静态网页添加动态效果,还能实现客户端与服务器的交互,如今…...
如何理解synchronized锁升级
在Java中,synchronized 关键字是实现线程同步的一种方式,它涉及到锁的升级和释放的过程。理解synchronized 锁的升级可以分为三个阶段:无锁状态、偏向锁状态和轻量级锁状态。 无锁状态: 当对象被创建时,默认处于无锁状…...
js【最佳实践】遍历数组的八种方法(含数组遍历 API 的对比)for,forEach,for of,map,filter,reduce,every,some
遍历方法返回值使用场景备注副作用for 循环——遍历数组通用可以改变原数组forEach 循环——遍历数组ES5 新增,不支持中断和异步可以改变原数组for of 循环——遍历数组ES6 新增可以改变原数组map格式化后的数组格式化数组的API不会改变原数组filter过滤后的数组过滤…...
Node.js开发实战 视频教程 下载
ode.js开发实战 视频教程 下载 下载地址 https://download.csdn.net/download/m0_67912929/89487510 01-课程介绍.mp4 02-内容综述.mp4 03-Node.js是什么? .mp4 04-Node.js可以用来做什么?.mp4 05-课程实战项目介绍.mp4 06-什么是技术预研? .mp4 07-Node.js开发环境…...
VS2022(Visual Studio 2022)最新安装教程
1、下载 1、下载地址 - 官网地址:下载 Visual Studio Tools - 免费安装 Windows、Mac、Linux - 根据自己的电脑的 【操作系统】 灵活选择。 2、安装包 【此处为Windows系统安装包】 2、安装 1、打开软件 - 右击【以管理员身份打开】, 2、准备配置 …...
从华为和特斯拉之争,看智能驾驶的未来
“一旦特斯拉完全解决自动驾驶问题并量产Optimus,任何空头都将被消灭,即使是比尔-盖茨也不例外。”7月2日,马斯克再次在社交媒体X上画下了这样的“大饼”。 与此同时,特斯拉的股价在最近的三个交易日也迎来了24%的涨幅,…...
20240705 每日AI必读资讯
📚Retool 刚刚发布了最新2024上半年《人工智能现状报告》 - 收集了约750名技术人员的意见 - 包括开发者、数据团队和各行业的领导者,了解如何利用人工智能产生真正的影响。 🔗 2024上半年《人工智能现状报告》Retool刚刚发布了最新-CSDN b…...
C++ 设计模式之访问者模式
C 设计模式之访问者模式 简介 1、访问者模式 (Visitor)是一种行为型设计模式,它表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。 使用该模式可以在不修改已有程序结构的前提…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
Robots.txt 文件
什么是robots.txt? robots.txt 是一个位于网站根目录下的文本文件(如:https://example.com/robots.txt),它用于指导网络爬虫(如搜索引擎的蜘蛛程序)如何抓取该网站的内容。这个文件遵循 Robots…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...
