当前位置: 首页 > 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.jsqmd.com/news/22505/

相关文章:

  • 实用指南:【Android之路】 Kotlin 的 data class、enum class、sealed interface
  • 精通-Pandas-探索性分析-全-
  • 【图像处理-基础知识】SFIT特征解析 - 教程
  • 深入解析:【FPGA+DSP系列】——(2)DSP最小核心板进行ADC采样实验(采集电位器输出电压)
  • ABC429F Shortest Path Query 题解
  • 苏维埃日报08.高三生福音?大屏课表软件ClassIsland助你度过高三
  • 创建平面设计网站-全-
  • 2025年优质的造纸橡胶辊,天然橡胶辊品牌厂家排行榜
  • 软件神器 --- x64db插件 之 SharpOD
  • 2025年耐用的移动搅拌车,搅拌车优质厂家推荐榜单
  • 2025年靠谱的方形冷却塔,横流式冷却塔用户口碑最好的厂家榜
  • 2025年口碑好的硅胶制品,密封硅胶制品厂家最新实力排行
  • 2025年耐用的北美款三防灯,单双管三防灯厂家推荐及选择指南
  • 2025年优质的高速电吹风开关,电吹风开关厂家最新用户好评榜
  • 2025年比较好的冷拔无缝钢管,大口径无缝钢管热门厂家推荐榜单
  • 2025年靠谱的广场音乐喷泉,水秀音乐喷泉行业内口碑厂家排行榜
  • 2025年知名的薄型液压缸,多级液压缸实力厂家TOP推荐榜
  • 2025年有实力贴体机,手压式真空贴体机用户好评厂家排行
  • 2025年优质的定量包装机,自动吨袋包装机厂家最新用户好评榜
  • 2025年靠谱的汽车改装,别克gl8汽车改装厂家实力及用户口碑排行榜
  • 2025年知名的厚薄门通用缓冲铰链,任意扣缓冲铰链厂家实力及用户口碑排行榜
  • 完整教程:构建融合扩散模块的知识引导式联邦图注意力学习网络用于阿尔茨海默病诊断|文献速递-文献分享
  • 2025年优质的移动盘式过滤机,真空过滤机最新TOP品牌厂家排行
  • 2025年诚信的涂料色浆,浙江环保水性色浆厂家推荐及采购指南
  • 2025年知名的变频器控制柜,ACU控制柜行业内知名厂家排行榜
  • 2025年优质的涤纶单层网布,鞋材单层网布厂家最新推荐权威榜
  • 2025年热门的卧式明装风机盘管,立式暗装风机盘管厂家最新权威推荐排行榜
  • 2025年质量好的安全保护电器开关,感应电器开关厂家选购指南与推荐
  • 2025年比较好的防氧化铝合金线槽,耐腐蚀铝合金线槽厂家最新TOP排行榜
  • 2025年优秀的肌电图针电极,术中针电极厂家推荐及选购参考榜