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