Leetcode第290场周赛解题报告

本次题目难度增加了，虽然大家都表示猝不及防，但是我更希望以后能够出一些这样难度的题目

6041. 多个数组求交集

知识点：哈希表
直接使用哈希表维护出现次数，加入出现次数与给定数组个数nums.size()相等，那么说明该数字在每个数组中均出现了一次。

class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        unordered_map<int,int> mp;
        for(auto i:nums) {
            for(auto j :i) {
                mp[j]++;
            }
        }
        auto s = nums.size();
        vector<int> ans;
        for(auto &[k,v]:mp) {
            if(v==s) ans.push_back(k);
        }
        sort(ans.begin(),ans.end());
        return ans;
    }
};

6042. 统计圆内格点数目

知识点：模拟/扫描线、差分数组

模拟：大暴力

把正方形区域内的每一个点暴力了一遍，然后判断与圆心关系。该方法会卡时限，只能说恰好可以通过，而且并非最优解

class Solution {
public:
    int countLatticePoints(vector<vector<int>>& circles) {
        set<pair<int,int>> s;
        for(auto i : circles) {
            for(int x = i[0]-i[2];x <= i[0]+i[2];x++) {
                for(int y = i[1]-i[2];y <= i[1]+i[2];y++) {
                    if(pow(fabs(x-i[0]),2)+pow(fabs(y-i[1]),2)<=i[2]*i[2]) s.insert({x,y});
                }
            }
        }
        return s.size();
    }
};

6043. 统计包含每个点的矩形数目

知识点：二分/树状数组/二维线段树

二分：暴力

这里是根据题目中1 <= hi, yj <= 100的取值范围而确定的方法，当然 我在比赛中没有遇见。
开100个数组，对每个数组进行排序。
在查找时，遍历100次，对每个数组进行二分查找，查找到其下标，根据下标确定目标个数即可。

class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        vector<vector<int>> yrt(101);
        for(auto i : rectangles) {
            yrt[i[1]].push_back(i[0]);
        }
        for(int i = 0;i <= 100;i++) {
            sort(yrt[i].begin(),yrt[i].end());
        }
        vector<int> ans;
        for(auto i : points){
            int r = 0;
            for(int j = i[1];j <= 100;j++){
                auto low = lower_bound(yrt[j].begin(),yrt[j].end(),i[0])-yrt[j].begin();
                if(low < yrt[j].size()) r += yrt[j].size()-low;
            }
            ans.push_back(r);
        }
        return ans;
    }
};

6044. 花期内花的数目

知识点：扫描线算法、二分/树状数组/线段树
如果不取巧的做的话，难度还是挺高的。

暴力：扫描线算法

首先第一步，对数据进行离散化，即不存储中间条件，只存储首尾信息，将开始归纳为{pos,+1}，结束归纳为{pos,-1}，每个关键节点记录变化之前的值和变化之后的值。
然后对于每个问询：使用二分查找对map查找到最近的节点，如果该节点的key与问询相等，那么使用该节点变化之后的值，如果该节点的key大于问询，那么使用变化之前的值。

#include <vector>
#include <map>
#include <iostream>
#include <algorithm>
using namespace std;
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        vector<pair<int,int>> pers;
        for(int i = 0;i < persons.size();i++) pers.push_back({persons[i],i});
        sort(pers.begin(),pers.end());
        vector<int> ans(persons.size(),0);
        
        vector<pair<int,int>> f(flowers.size()*2);
        for(int i = 0;i < flowers.size();i++) {
            f[i*2] = {flowers[i][0],+1};
            f[i*2 + 1] = {flowers[i][1]+1,-1};
        }
        sort(f.begin(),f.end());
        
        map<int,pair<int,int>> mp;
        
        int now = 0;
        for(auto i:f) {
            auto x = now;
            if(mp.find(i.first)!=mp.end()) {
                x = mp[i.first].first;
            }
            now += i.second;
            mp[i.first] = {x,now};
        }
        
        
        for(auto i : pers) {
            int an = 0;
            int q = i.first;
            
            auto res = mp.lower_bound(q);
            if(res==mp.end()) an = 0;
            else{
                if(res->first==q) an = res->second.second;
                else an = res->second.first;
            }
            ans[i.second] = an;
        }
        
        
        return ans;
    }
};