【算法实战】每日一题:设计一个算法,用最少数量的矩形覆盖一系列宽度为d、高度为w的矩形,且使用矩形不能超出边界
题目
设计一个算法,用最少数量的矩形覆盖一系列宽度为d、高度为w的矩形建筑物侧墙,且矩形不能超出边界。
核心思路
考虑这种结构

前面递增后面一个与前面的某个高度一致,这时候考虑最下面的覆盖(即都是从最下面向上覆盖)

考虑到使用栈,这里我们用列表代替
当栈不为空并且新元素比栈顶小,这时候存在这种可能结构成立,
对每个墙循环,如果新元素比栈顶元素大,就进栈;
反之,如果新元素比栈顶元素小,就使得栈顶元素出栈,继续比较新栈顶元素与当前使用新元素的大小,一直到比较到当前使用新元素和之前的某个元素的大小相同,此时计数器+1,表示找到这种结构+1
另外向上因为与数量一致,所以这里不考虑

伪代码
定义一个函数 main:定义一个变量 n,用于存储输入的整数。定义一个变量 ans,初始化为 0,用于存储最终答案。定义一个空列表 st,用于模拟栈结构。对于从 1 到 n 的每个整数 i:读取两个整数 d 和 w,并将它们分别存储到变量 d 和 w 中。当列表 st 不为空且 w 小于等于 st 中最后一个元素时:如果 st 中最后一个元素等于 w:将 ans 的值增加 1。从 st 中移除最后一个元素,因为当前 w 值破坏了递增结构。将 w 添加到 st 的末尾。打印 n 减去 ans 的结果。如果这个脚本是主程序:调用 main 函数。
CODE
def main():n = int(input())# 这种结构有多少种ans = 0st = []for i in range(1, n + 1):d, w = map(int, input().split())# 列表类似栈的结构while st and w <= st[-1]:# 找到该种结构种类数+1if st[-1] == w:ans += 1# pop掉,因为该种结构要求前面都是递增,而这里当前使用新元素已经是破坏了# 递增结构,所以直接丢掉,准备下一次的# 最后栈是空的,上面循环直接刷到最前面了st.pop()st.append(w)print(n - ans)if __name__ == "__main__":main()
END
相关文章:
【算法实战】每日一题:设计一个算法,用最少数量的矩形覆盖一系列宽度为d、高度为w的矩形,且使用矩形不能超出边界
题目 设计一个算法,用最少数量的矩形覆盖一系列宽度为d、高度为w的矩形建筑物侧墙,且矩形不能超出边界。 核心思路 考虑这种结构 前面递增后面一个与前面的某个高度一致,这时候考虑最下面的覆盖(即都是从最下面向上覆盖&#…...
外贸仓库管理软件:海外仓效率大幅度提升、避免劳动力积压
随着外贸业务的不断发展,如何高效管理外贸仓库,确保货物顺利流转,订单顺利处理,就变得非常重要。 现在通常的解决方案都是通过引入外贸仓库管理软件,也就是我们常说的海外仓WMS系统来解决。 今天我们就系统的探讨一下…...
6.8 LIBBPF API(七,bpf_core_read.h 函数,定义,枚举)
一,函数 void * bpf_rdonly_cast (const void *obj, __u32 btf_id) __ksym __weak 二,定义 __CORE_RELO(src, field, info) __builtin_preserve_field_info((src)->field,BPF_FIELD_##info) __CORE_BITFIELD_PROBE_READ(dst, src, fld) bpf_probe_read_kernel( \ (v…...
电脑卸载linux安装windows后每次开机都出现grub
原因分析 这是因为电脑硬盘中还存在linux系统的引导程序,并且启动顺序还在windows之前,有时候通过bios根本找不到它的存在,以至于每次windows开机出现grub之后都要输入exit退出linux的引导之后才能使得电脑进入windows,这个有时会…...
总结 HTTPS 的加密流程
一、前言 http是为了解决http存在的问题而在http基础上加入了SSL/TSL,在HTTP/2中TCP三次握手后会进入SSL/TSL握手,当SSL/TSL建立链接后,才会进行报文的传输。 二、HTTPS的混合加密 我们先来认识密钥: 密钥是用于加密和解密数据…...
Spring的FactoryBean多例问题
关于spring bean,我们了解的最多的还是单例,而多例bean,除了平时我们自己new的那些多实例外(但不属于IOC管理了),几乎很少能用到,而在spring 层面,FactoryBean刚好是多例的一个体现,…...
[nextjs]推荐几个很好看的模板网站
最近在做网站,折腾了 vue 框架,然后发现了 nextjs 框架,感觉这个做出来的网站配色很好看,然后又开始研究这个 网站配色好看是因为用的 tailwindcss,找网站过程中,发现了几个很好看的模板网站,在这里推荐下,或许你也能用得上 推荐第一个网站是: https://tailspark.co/ 有组件,也…...
《当微服务遇上Ribbon:一场负载均衡的华丽舞会》
在微服务的厨房里,如何确保每一道服务都恰到好处?揭秘Spring Cloud Ribbon如何像大厨一样精心调配资源,让负载均衡变得像烹饪艺术一样简单! 文章目录 Spring Cloud Ribbon 详解1. 引言微服务架构中的负载均衡需求Spring Cloud Rib…...
简单随机数据算法
文章目录 一,需求概述二,实现代码三、测试代码四、测试结果五、源码传送六、效果演示 一,需求概述 系统启动时,读取一组图片数据,通过接口返回给前台,要求: 图片随机相邻图片不重复 二&#…...
js画思维导图代码2
这段代码是一个使用Vue.js和D3.js构建的树形图组件。它是一个Vue组件,用于创建和显示一个交互式的树形结构图。下面是对这段代码的简要分析: 模板部分 (<template>): 定义了组件的HTML结构,包括一个隐藏的提示框(#tooltip)和一个用于显…...
使用 Flask 实现异步请求处理
文章目录 为什么需要异步请求处理?在 Flask 中实现异步请求处理使用 Flask-Cors 扩展 总结 在开发 Web 应用程序时,异步请求处理是提高性能和并发能力的重要方法之一。Flask 是一个轻量级的 Web 框架,它提供了易于使用的工具来实现异步请求处…...
关于c++的通过cin.get()维持黑框的思考
1.前言 由于本科没有学过c语言,研究生阶段接触c上手有点困难,今天遇到关于通过cin.get()来让黑框维持的原因。 2.思考 cin.get()维持黑框不消失的原因一言蔽之就是等待输入。等待键盘的输入内容并回车(一般是回车)后cin.get()才…...
fastadmin接口输出图片 自动拼接网站URL
先自定义常量 1.文件接口路径 修改核心文件 application\common\controller\Api.php/*** 构造方法* access public* param Request $request Request 对象*/public function __construct(Request $request null){$this->request is_null($request) ? Request::instance…...
VMware Workstation 不可恢复错误:(vmui) 错误代码0xc0000094
软件版本 vmware 17 错误情况 VMware Workstation 不可恢复错误:(vmui) Exception 0xc0000094 has occurred. 问题原因 VMware升级到17.0后,将虚拟机环境的【硬件兼容性】升级至Workstation 17.X后,无法修改设备参数。 解决办法 打开需…...
DockerNetwork
Docker Network Docker Network 是 Docker 引擎提供的一种功能,用于管理 Docker 容器之间以及容器与外部网络之间的网络通信。它允许用户定义和配置容器的网络环境,以便容器之间可以相互通信,并与外部网络进行连接。 Docker Network 提供了以…...
QT学习(20):QStyle类
Qt包含一组QStyle子类,这些子类(QWindowsStyle,QMacStyle等)模拟Qt支持的不同平台的样式,默认情况下,这些样式内置在Qt GUI模块中,样式也可以作为插件提供。 Qt的内置widgets使用QStyle来执行几…...
hadoop学习之MapReduce案例:输出每个班级中的成绩前三名的学生
hadoop学习之MapReduce案例:输出每个班级中的成绩前三名的学生 所要处理的数据案例: 1500100001 施笑槐,22,女,文科六班,406 1500100002 吕金鹏,24,男,文科六班,440 1500100003 单乐蕊,22,女,理科六班,359 1500100004 葛德曜,24,男,理科三班,421 15001…...
【亲测,安卓版】快速将网页网址打包成安卓app,一键将网页打包成app,免安装纯绿色版本,快速将网页网址打包成安卓apk
背景:部分客户需求将自己网站打包成app,供用户在浏览器安装使用、 网页网址快速生成app 准备材料操作流程第一步:打开HBuilder X新建项目第二步创建Wap2App项目第三步修改App图标第四步发布app第五步查看apk 准备材料 1.需要打包的网页 2.ap…...
学习thinkphp的循环标签
1.FOREACH标签 foreach标签的用法和PHP语法非常接近,用于循环输出数组或者对象的属性,用法如下: $list User::all(); View::assign(list,$list); 模板文件中可以这样输出 {foreach $list as $key>$vo } {$vo.id}:{$vo.name} {/foreac…...
根据标签名递归读取xml字符串中element
工具类: /*** 根据标签名递归读取xml字符串中element* 例:* String xml * "<req>\n" * "<tag1></tag1>\n" * "<tag2>\n" * " <tag4></tag4>\n" * "</tag2>\n&…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
YSYX学习记录(八)
C语言,练习0: 先创建一个文件夹,我用的是物理机: 安装build-essential 练习1: 我注释掉了 #include <stdio.h> 出现下面错误 在你的文本编辑器中打开ex1文件,随机修改或删除一部分,之后…...
IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...
Java编程之桥接模式
定义 桥接模式(Bridge Pattern)属于结构型设计模式,它的核心意图是将抽象部分与实现部分分离,使它们可以独立地变化。这种模式通过组合关系来替代继承关系,从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...
OD 算法题 B卷【正整数到Excel编号之间的转换】
文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的:a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...
