当前位置: 首页 > news >正文

记力扣2271.毯子覆盖的最多白色砖块数 练习理解 - 详解

给你一个二维整数数组 tiles ,其中 tiles[i] = [li, ri] ,表示所有在 li <= j <= ri 之间的每个瓷砖位置 j 都被涂成了白色。

同时给你一个整数 carpetLen ,表示可以放在 任何位置 的一块毯子的长度。

通过请你返回使用这块毯子,最多 能够盖住多少块瓷砖。

思路:

先将列表按元素第一个数字大小顺序排序(tiles.sort(key:lambda x:x[0]),接着开始遍历,算出每一个列表的长度,然后通过carpet_left=该列表右端点长减去毯子长 +1 算 出毯子左端点的位置,然后去判断第一个列表的右端点是否小于毯子左端点假设成立则得剔除该列表的长度,达到合适的管用毯子覆盖,然后算出不被覆盖的最大长度,之后结果就是max(ans,cover-uncover),前面算的是完全不在范围内的列表长度,末了还需把部分重叠的减去才是最终的结果

from typing import List
class Solution:def maximumWhiteTiles(self,tiles:List[int],carpeten:int)->int:ans,cover,left=0,0,0tiles.sort(key=lambda x:x[0])for tl,tr in tiles:cover +=tr-tl+1carpet_left=tr-carpeten+1while tiles[left][1]

难点:

  1. 区间覆盖的边界处理

    • 难点在于计算uncover部分:max(carpet_left - tiles[left][0], 0)
    • 当地毯左边界落在某个瓷砖区间中间时就是这部分需要准确判断当前左边界瓷砖有多少部分不在被地毯覆盖,尤其
  2. 滑动窗口的调整策略

    • 如何确定窗口左边界的移动时机:while tiles[left][1] < carpet_left
    • 需要精准判断哪些瓷砖完全不在被当前地毯覆盖,从而从窗口中移除
  3. 地毯长度与瓷砖区间的匹配

    • 当地毯长度大于多个瓷砖区间总和时的处理
    • 当地毯长度小于单个瓷砖区间时的部分覆盖计算
  4. 最优解的更新时机

    • 每次调整窗口后都需要计算当前有效覆盖长度,并与历史最优解比较
    • 这里的有效覆盖长度是cover - uncover,而不是简单的cover

http://www.rkmt.cn/news/30636.html

相关文章:

  • 精通-Pandas-探索性分析-全-
  • 精通-HTML5-表单-全-
  • ABC429F Shortest Path Query 题解
  • 苏维埃日报08.高三生福音?大屏课表软件ClassIsland助你度过高三
  • 创建平面设计网站-全-
  • 2025年靠谱的方形冷却塔,横流式冷却塔用户口碑最好的厂家榜
  • 2025年知名的薄型液压缸,多级液压缸实力厂家TOP推荐榜
  • 2025年优质的定量包装机,自动吨袋包装机厂家最新用户好评榜
  • 2025年优质的移动盘式过滤机,真空过滤机最新TOP品牌厂家排行
  • 2025年优质的涤纶单层网布,鞋材单层网布厂家最新推荐权威榜
  • 2025年靠谱的粉末冶金,粉末冶金齿轮厂家推荐及采购参考
  • 2025年热门的吸塑PET片,食品级PET片品牌厂家排行榜
  • 2025年热门的发电机组,柴油发电机组厂家最新推荐排行榜
  • quicker目录
  • [SHELL] 个人BASH配置与美化
  • [AI应用开发平台] Coze:AI应用开发平台
  • [网络] [TOOL] 为什么要使用ss工具替代netstat?
  • [网络] [TCP] Linux UDP Socket 学习指南
  • 品牌故事不会写?这个AI指令可能帮你解决大问题
  • 电梯调度编程结对项目总结
  • 第二次作业--田佳吉
  • 启动分布式mapreduce的过程以及prompt
  • 20232310 2025-2026-1 《网络与系统攻防技术》实验三实验报告
  • [SWPUCTF 2024 秋季新生赛]http标头 WP
  • 20251025 之所思 - 人生如梦
  • 为什么Java/Python程序无需关心内存释放?揭秘垃圾回收(GC)的核心概念
  • 从图像到文本:详解藏文OCR的实现过程与核心技术
  • Jerrum–Sinclair 全有或全无定理
  • 初步学习计算机相关知识有感 - fang
  • RuoYi-Cloud 认证实现