首页 > 其他分享 >Leetcode每日一题 20240731 3111.覆盖所有点的最少矩阵数目

Leetcode每日一题 20240731 3111.覆盖所有点的最少矩阵数目

时间:2024-07-31 23:24:49浏览次数:15  
标签:20240731 int beg 3111 右上角 points 左下角 矩形 Leetcode

题目描述

给你一个二维整数数组 point ,其中 points[i] = [xi, yi] 表示二维平面内的一个点。同时给你一个整数 w 。你需要用矩形 覆盖所有 点。
每个矩形的左下角在某个点 (x1, 0) 处,且右上角在某个点 (x2, y2) 处,其中 x1 <= x2 且 y2 >= 0 ,同时对于每个矩形都 必须 满足 x2 - x1 <= w 。
如果一个点在矩形内或者在边上,我们说这个点被矩形覆盖了。
请你在确保每个点都 至少 被一个矩形覆盖的前提下,最少 需要多少个矩形。

注意:一个点可以被多个矩形覆盖。
3111.覆盖所有点的最少矩阵数目

测试案例及提示

示例1:
png输入:points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1
输出:2
解释:
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (1, 0) ,右上角在 (2, 8) 。
一个矩形的左下角在 (3, 0) ,右上角在 (4, 8) 。

示例2:
png
输入:points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2
输出:3
解释:
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (0, 0) ,右上角在 (2, 2) 。
一个矩形的左下角在 (3, 0) ,右上角在 (5, 5) 。
一个矩形的左下角在 (6, 0) ,右上角在 (6, 6) 。

示例 3:
png
输入:points = [[2,3],[1,2]], w = 0
输出:2
解释
上图展示了一种可行的矩形放置方案:
一个矩形的左下角在 (1, 0) ,右上角在 (1, 2) 。
一个矩形的左下角在 (2, 0) ,右上角在 (2, 3) 。

提示:
1 <= points.length <= 105
points[i].length == 2
0 <= xi == points[i][0] <= 109
0 <= yi == points[i][1] <= 109
0 <= w <= 109
所有点坐标 (xi, yi) 互不相同。

解题思路

理解题意
题目需要我们用最少的矩形来覆盖所有点,同时不要考虑矩形的高(y轴方向的长度)
我们只需要考虑x方向上的点。
构建思路
首先对points进行排序,然后从最小的x开始规划,然后对于每个矩形都使用最大的宽度(宽度视为x边的值,最大值是w),依次判断points[i][0]是否满足条件,不满足就更新矩形左下角坐标为当前的points[i][0].
C语言排序的模板可查看我的一篇文章
python

class Solution:
    def minRectanglesToCoverPoints(self, points: List[List[int]], w: int) -> int:
        points = sorted(points)
        ans = 1
        beg = points[0][0]     
        for p in points:
            if p[0] > (beg + w):
                ans += 1
                beg = p[0]
        return ans

C

int compare(const void **a, const void **b) {
    return ((*(int **)a)[0] - (*(int **)b)[0]);
}

int minRectanglesToCoverPoints(int** points, int pointsSize, int* pointsColSize, int w) {
    qsort(points, pointsSize, sizeof(int*), compare);
    int ans = 1;
    int beg = points[0][0];
    for (int i = 1; i < pointsSize; i++) {
        if (points[i][0] > beg + w) {
            ans++;
            beg = points[i][0];
        }
    }
    return ans;
}

标签:20240731,int,beg,3111,右上角,points,左下角,矩形,Leetcode
From: https://blog.csdn.net/2301_76443687/article/details/140834422

相关文章

  • leetcode20.有效的括号、华为OD机试-(C卷,100分)- 表达式括号匹配
    leetcode20.有效的括号题目描述给定一个只包括‘(’,‘)’,‘{’,‘}’,‘[’,‘]’的字符串s,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。示例1:输入:s=“()......
  • LeetCode | 27 RemoveElement
    https://github.com/dolphinmind/datastructure/tree/datastructure-array主类packagecom.github.dolphinmind.array.binarysearch;/***@authordolphinmind*@ClassNameRemoveElement*@description27移除元素*移除元素分析*快......
  • LeetCode | 977 SquaresOfASortedArray
    https://github.com/dolphinmind/datastructure/tree/datastructure-array主类packagecom.github.dolphinmind.array.binarysearch;/***@authordolphinmind*@ClassNameSquaresOfASortedArray*@description977.有序数组的平方*分析:有移除元素{......
  • LeetCode | 704 BinarySearch
    https://github.com/dolphinmind/datastructure/tree/datastructure-array主类packagecom.github.dolphinmind.array.binarysearch;/***@authordolphinmind*@ClassNameBinarySearch*@description704二分法搜索*前提条件:有序数组,且无重复元素......
  • *算法训练(leetcode)第三十五天 | 121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 I
    刷题记录*121.买卖股票的最佳时机贪心*动态规划122.买卖股票的最佳时机II贪心*动态规划*123.买卖股票的最佳时机III*121.买卖股票的最佳时机leetcode题目地址贪心找左侧最小值、右侧最大值(与最小值求差最大),求差即为最大利润。时间复杂度:......
  • 坐牢二十天 20240731(IO)
    一.作业1>使用父子进程完成两个文件的拷贝父进程拷贝前一半内容,子进程拷贝后一半内容子进程结束后退出,父进程回收子进程的资源#include<myhead.h>//定义求源文件长度的函数intlenmain(constchar*src,constchar*dst){intfd1=0;//源文件intfd2=0;//目......
  • 代码随想录训练第三十天|01背包理论基础、01背包、LeetCode416.分割等和子集
    文章目录01背包理论基础01背包二维dp数组01背包一维dp数组(滚动数组)416.分割等和子集思路01背包理论基础背包问题的理论基础重中之重是01背包,一定要理解透!leetcode上没有纯01背包的问题,都是01背包应用方面的题目,也就是需要转化为01背包问题。所以我先通过纯01背......
  • 代码随想录训练第三十一天|LeetCode1049.最后一块石头的重量II、LeetCode494.目标和、
    文章目录1049.最后一块石头的重量II思路一维数组二维数组494.目标和思路一维数组解法二维数组解法474.一和零思路1049.最后一块石头的重量II有一堆石头,用整数数组stones表示。其中stones[i]表示第i块石头的重量。每一回合,从中选出任意两块石头,然后将它们一......
  • 代码随想录训练第三十二天|完全背包理论基础、LeetCode518.零钱兑换II、LeetCode377.
    文章目录完全背包理论基础完全背包总结518.零钱兑换II思路一维数组二维数组377.组合总和Ⅳ思路卡码网70.爬楼梯(进阶版)思路完全背包理论基础完全背包有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i],得到的价值是value[i]。每件物品都有无......
  • 代码随想录训练第三十三天|LeetCode322. 零钱兑换、LeetCode279.完全平方数、LeetCode
    文章目录322.零钱兑换思路279.完全平方数思路139.单词拆分思路多重背包背包总结遍历顺序01背包完全背包总结322.零钱兑换给你一个整数数组coins,表示不同面额的硬币;以及一个整数amount,表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果......