第55天(简单题中等题 数据结构)

打卡第五十五天
2道简单题+1道中等题

题目：

思路：差分

代码：

class Solution {
public:int numberOfPoints(vector<vector<int>>& nums) {int max_end = 0;for (const auto& s : nums) {max_end = max(max_end, s[1]);  // 找到所有区间中最大的终点值}vector<int> diff(max_end + 2);  // 初始值全为0，diff[i] 表示坐标 i 处的覆盖数相对于 i-1 处的变化量for (const auto& s : nums) {int start = s[0];  int end = s[1];    diff[start]++;// 从这个点开始，多了一个区间覆盖diff[end + 1]--;// 从这个点之后，少了一个区间覆盖。区间包含终点，所以减1操作在 end+1 处}int ans = 0;    // 最终结果int count = 0;  // 当前坐标点被覆盖的次数for (int i = 0; i <= max_end; ++i) {count += diff[i];// diff[0] 到 diff[i] 的累加和if (count > 0) {// 如果当前点被至少一个区间覆盖ans++;  }}return ans;}
};

耗时≈1小时 明天继续