首页 > 其他分享 >2848.与车相交的点-362

2848.与车相交的点-362

时间:2023-09-11 11:12:38浏览次数:35  
标签:end 2848 nums int 相交 start ans diff 362

2848. 与车相交的点

给你一个下标从 0 开始的二维整数数组 nums 表示汽车停放在数轴上的坐标。对于任意下标 i,nums[i] = [starti, endi] ,其中 starti 是第 i 辆车的起点,endi 是第 i 辆车的终点。

返回数轴上被车 任意部分 覆盖的整数点的数目。

示例 1:

输入:nums = [[3,6],[1,5],[4,7]]
输出:7
解释:从 1 到 7 的所有点都至少与一辆车相交,因此答案为 7 。
示例 2:

输入:nums = [[1,3],[5,8]]
输出:7
解释:1、2、3、5、6、7、8 共计 7 个点满足至少与一辆车相交,因此答案为 7 。

提示:

1 <= nums.length <= 100
nums[i].length == 2
1 <= starti <= endi <= 100

解题思路

见代码注释。

code

class Solution {
public:

    //记录该点是否有汽车
    //区间更新[start,end]
    //区间更新:差分数组
    //diff[0] = a[0]
    //diff[i] = a[i] - a[i-1]

    //关键实现:update(start,end)
    //diff[start] += x
    //diff[end + 1] -= x

    void update(int start,int end,int x,vector<int> & diff)
    {
        diff[start] += x;
        diff[end + 1] -= x;
    } 

    int numberOfPoints(vector<vector<int>>& nums) {

        vector<int> diff(110,0);

        for(auto item : nums)
            update(item[0],item[1],1,diff);

        int ans = 0;
        for(int i = 1;i < 110;i ++)
        {
            diff[i] = diff[i] + diff[i-1];
            if(diff[i] > 0) ans ++;
        }

        return ans; 
    }
};
class Solution:

    def update(selt,diff : List[int],start : int,end : int,x : int) -> int:
        diff[start] += x
        diff[end + 1] -= x

    def numberOfPoints(self, nums: List[List[int]]) -> int:
        
        diff = [0] * 110
        #print(diff)
        for start,end in nums:
            self.update(diff,start,end,1)

        ans = 0

        for i in range(1,110):
            diff[i] = diff[i] + diff[i-1]
            if(diff[i] > 0):
                ans += 1

        return ans

标签:end,2848,nums,int,相交,start,ans,diff,362
From: https://www.cnblogs.com/huangxk23/p/17692978.html

相关文章

  • 2849. 判断能否在给定时间到达单元格-362
    2849.判断能否在给定时间到达单元格给你四个整数sx、sy、fx、fy以及一个非负整数t。在一个无限的二维网格中,你从单元格(sx,sy)开始出发。每一秒,你必须移动到任一与之前所处单元格相邻的单元格中。如果你能在恰好t秒后到达单元格(fx,fy),返回true;否则,返回......
  • 代码随想录算法训练营第四天| 24. 两两交换链表中的节点, 19.删除链表的倒数第N个结点
    24.两两交换链表中的节点mydemo(超时)/***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListNode(intx):val(x),next(nullptr){}*ListNode(intx,Lis......
  • Revit API创建几何实体Solid并找到与之相交的元素
    几何实体的创建方法之一:构成封闭底面,指定拉伸方向与拉伸高度。GeometryCreationUtilities//自创几何实体相交法[TransactionAttribute(Autodesk.Revit.Attributes.TransactionMode.Manual)]publicclassFindIntersectWallsByGeometry:IExternalCommand{publicResult......
  • Java中使用JTS对空间几何计算(读取WKT、距离、点在面内、长度、面积、相交等)
    场景基于GIS相关的集成系统,需要对空间数据做一些判断处理。比如读取WKT数据、点到点、点到线、点到面的距离,线的长度、面的面积、点是否在面内等处理。JTS(JavaTopologySuite)Java拓扑套件,是Java的处理地理数据的API。github地址:https://github.com/locationtech/jtsAPI......
  • loj3362
    因为某hhz曾经往XJOI模拟赛搬了这题,然后现在我要给模拟赛讲题,所以滚回来补题了。观察\(1\):对于一个形如WWBB的子图,如果当前匹配是\((1,4)(2,3)\),我们换成\((1,3)(2,4)\)总更优。观察\(2\):满足观察\(1\)的情况,可以被描述为,假设某个B和W相连,那么当前B的后一个......
  • Leetcode 160. 链表相交(Intersection of two linked lists lcci)
    题目链接给定两个单链表的头节点headA和headB,请找出并返回两个单链表相交的起始节点.如果两个链表没有交点,返回null.图示两个链表在节点c1开始相交,题目数据保证整个链式结构中不存在环.示例1:输入:intersectVal=8,listA=[4,1,8,4,5],listB=[5,0,1,8,4,5],sk......
  • ID为12848的进程未运行,解决方法
    1.win+R输入eventvwr,打开事件查看器打开windows事件查看器查看报错具体信息,跟具文件位置判断,认证服务没有启动。2.查看具体报错信息,发现由于项目框架为asp.net3.1,本地并未安装该框架,点击下载安装包。3.不报错,运行成功,......
  • LeetCode 1035.不相交的线
    1.题目:在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足: nums1[i]==nums2[j]且绘制的直线不与任何其他连线(非水平线)相交。请注意,连线即使在端点也不能相交:每个数字只......
  • P3629 巡逻 LCA题解
    原题:洛谷P3629问题转化首先,给定的图是一个有\(n\)个点,\(n-1\)条边的无向连通图,这个图就等价于一棵树。不建立新的道路时,从\(1\)号节点出发,把整棵树上的每条边遍历至少一次,再回到\(1\)号节点,会恰好经过每条边两次,路线总长度为\(2(n-1)\),如下图最左边的部分所示。根据树......
  • 线段相交Ⅲ
    描述 线段相交有两种情形:一种是“规范相交”,另一种是“非规范相交”。规范相交是指两条线段恰有唯一一个不是端点的公共点。即如果一条线段的端点在另一条线段上则不视为相交。如果两条线段有部分重合,也不视为相交。而非规范相交则把以上两种情况都视为相交。如下图所示:规范......