Leetcode 第290场周赛

Leetclass="superseo">code 第290场周赛

这周是个菜狗

6041 多个数组求交集

class Solution:
    def intersection(self, nums: List[List[int]]) -> List[int]:
        dicts = defaultdict(int)
        n = len(nums)
        for num in nums:
            for items in num:
                dicts[items]+=1
        ans = []
        for item in dicts:
            if dicts[item]==n:
                ans.append(item)
        ans.sort()
        return ans

6042 统计圆内格点数目

判断那里没加while循环，一直没想到 掐点没交上 我菜哭了

class Solution {
public:
    int ans = 0;
    vector<vector<bool>> mp;
    void dfs(vector<int> v) {
        vector<int> row(2);
        int hight = v[1];
        row[0] = v[0]-v[2];
        row[1] = v[0]+v[2];
        while(hight<=v[1]+v[2]){
            while((hight-v[1]) * (hight-v[1]) + (row[1]-v[0])*(row[1]-v[0]) > v[2]*v[2]){
                row[0]+=1; row[1]-=1;
            }
            for(int i=row[0]; i<=row[1]; i++){
                if(!mp[i][hight]){
                    mp[i][hight] = true; ans+=1;
                }
            }
            hight +=1;
            
                
        }
        row[0] = v[0]-v[2]+1;
        row[1] = v[0]+v[2]-1;
        hight  = v[1] - 1;
        while(hight>=v[1]-v[2]){
            while((hight-v[1]) * (hight-v[1]) +(row[1]-v[0])*(row[1]-v[0]) > v[2]*v[2]){
                row[0]+=1; row[1]-=1;
            }
            for(int i=row[0]; i<=row[1]; i++){
                if(!mp[i][hight]){
                    mp[i][hight] = true; ans+=1;
                }
            }
            hight -=1;
        }

    }
    int countLatticePoints(vector<vector<int>>& circles) {
        int n = circles.size();
        mp.resize(1000,vector<bool>(1000,false));
        for(int i=0;i<n;i++)    dfs(circles[i]);
        return ans;
    }
};

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

参考思路1：y最大100，rectangles的x放到0-100容器中，然后二分遍历找在points y>=y-100中找比point x大的加起来。
参考思路2：将rectangle 的x从大到小排序，然后points 记录id 从大到小排序，用个有序的set维护和记录对y排序，47 / 47 个通过测试用例 状态：超出时间限制

//思路1 打败100%
vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
    int n = points.size(), m = rectangles.size();
    vector<vector<int>> buttom(100+1);
    vector<int> ans(n,0);
    for(int i=0;i<m;i++) 
        buttom[rectangles[i][1]].push_back(rectangles[i][0]);
    for(int i=0;i<=100;i++) 
        sort(buttom[i].begin(),buttom[i].end());//从大到小
    for(int i=0;i<n;i++) {
        for(int j=points[i][1];j<=100;j++){
            if(buttom[j].size()==0) continue;
            int ix = lower_bound(buttom[j].begin(),buttom[j].end(),points[i][0])-buttom[j].begin();
            ans[i] += buttom[j].size()-ix;
        }
    } 
    return ans;
}

class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        int n = points.size(), m = rectangles.size();
        vector<vector<int>> nPoint(n,vector<int>(3));
        for(int i=0;i<n;i++) {
            nPoint[i][0]=points[i][0];
            nPoint[i][1]=points[i][1];
            nPoint[i][2]=i;
        }
        // 横的排序 从大到小
        sort(rectangles.begin(),rectangles.end(),[](vector<int> a,vector<int> b){return a[0]>b[0];});
        sort(nPoint.begin(),nPoint.end(),[](vector<int> a,vector<int> b){return a[0]>b[0];});
        vector<int> ans(n,0);
        vector<int> count(100+1,0);
        set<int> s;
        int ix = 0, id;
        for(int i=0;i<n;i++) {
            while(ix<m && rectangles[ix][0]>=nPoint[i][0]){ //放入满足>x的条件的 y 
                s.insert(rectangles[ix][1]);
                count[rectangles[ix][1]]+=1;
                ix++;
            }
            auto it = s.lower_bound(nPoint[i][1]);
            while(it!=s.end()){
                ans[nPoint[i][2]]+= count[*it]; it++;
            }
        }
        return ans;
    }
};

6044 花期内花的数目