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)是一种行为型设计模式,它表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。 使用该模式可以在不修改已有程序结构的前提…...
FFmpeg 低延迟同屏方案
引言 在实时互动需求激增的当下,无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作,还是游戏直播的画面实时传输,低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架,凭借其灵活的编解码、数据…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
生成 Git SSH 证书
🔑 1. 生成 SSH 密钥对 在终端(Windows 使用 Git Bash,Mac/Linux 使用 Terminal)执行命令: ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" 参数说明: -t rsa&#x…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
Fabric V2.5 通用溯源系统——增加图片上传与下载功能
fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...
