leetcode weekly-contest-290

发布于 2022-04-24  587 次阅读


T1 多个数组求交集

给你一个二维整数数组 nums ,其中 nums[i] 是由 不同 正整数组成的一个非空数组,按 升序排列 返回一个数组,数组中的每个元素在 nums 所有数组 中都出现过。

输入:nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
输出:[3,4]
解释:
nums[0] = [3,1,2,4,5],nums[1] = [1,2,3,4],nums[2] = [3,4,5,6],在 nums 中每个数组中都出现的数字是 3 和 4 ,所以返回 [3,4] 。

分析:

由于这个题中,数据流不是很大,所以可以用哈希表来枚举每个数出现的次数

然后判断最终数字出现次数正好等于nums.size()的个数即可

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> intersection(vector<vector<int>>& nums) {
        map<int,int> mp;
        for(auto n:nums){
            for(auto num:n){
                mp[num]++;
            }
        }
        vector<int> ans;
        for(auto i :mp){
            if(i.second==nums.size()){
                ans.push_back(i.first);
            }
        }
        return ans;
    }
};

int main(){
    Solution s;
    vector<vector<int>> mp={{3,1,2,4,5},{1,2,3,4},{3,4,5,6}};
    vector<int> ans=s.intersection(mp);
    for(auto i : ans){
        cout<<i<<endl;
    }
}

T26042. 统计圆内格点数目

给你一个二维整数数组 circles ,其中 circles[i] = [xi, yi, ri] 表示网格上圆心为 (xi, yi) 且半径为 ri 的第 i 个圆,返回出现在 至少一个 圆内的 格点数目 。

注意:

格点 是指整数坐标对应的点。
圆周上的点 也被视为出现在圆内的点。

示例 1:

img

输入:circles = [[2,2,1]]
输出:5
解释:
给定的圆如上图所示。
出现在圆内的格点为 (1, 2)、(2, 1)、(2, 2)、(2, 3) 和 (3, 2),在图中用绿色标识。
像 (1, 1) 和 (1, 3) 这样用红色标识的点,并未出现在圆内。
因此,出现在至少一个圆内的格点数目是 5 。

分析:

这个题呢,就找到每个圆的左右,上下的边界,分别为x-r,x+r;y-r;y-r,然后去扫描每个点。

把每个点用set去重,返回set的长度

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    int countLatticePoints(vector<vector<int>>& circles) {
        set<pair<int,int>> ans;
        for(auto circle:circles){
            int x=circle[0];
            int y=circle[1];
            int r=circle[2];
            for(int nx=x-r;nx<=x+r;nx++){
                for(int ny=y-r;ny<=y+r;ny++){
                    if((nx-x)*(nx-x)+(ny-y)*(ny-y)<=r*r){
                        ans.insert({nx,ny});
                    }
                }
            }
        }
        return ans.size();
    }
};

int main(){
    Solution s;
    vector<vector<int>> mp={{2,1,1}};
    cout<<s.countLatticePoints(mp);
}

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

给你一个二维整数数组 rectangles ,其中 rectangles[i] = [li, hi] 表示第 i 个矩形长为 li 高为 hi 。给你一个二维整数数组 points ,其中 points[j] = [xj, yj] 是坐标为 (xj, yj) 的一个点。

第 i 个矩形的 左下角 在 (0, 0) 处,右上角 在 (li, hi) 。

请你返回一个整数数组 count ,长度为 points.length,其中 count[j]是 包含 第 j 个点的矩形数目。

如果 0 <= xj <= li 且 0 <= yj <= hi ,那么我们说第 i 个矩形包含第 j 个点。如果一个点刚好在矩形的 边上 ,这个点也被视为被矩形包含。

img

输入:rectangles = [[1,2],[2,3],[2,5]], points = [[2,1],[1,4]]
输出:[2,1]
解释:
第一个矩形不包含任何点。
第二个矩形只包含一个点 (2, 1) 。
第三个矩形包含点 (2, 1) 和 (1, 4) 。
包含点 (2, 1) 的矩形数目为 2 。
包含点 (1, 4) 的矩形数目为 1 。
所以,我们返回 [2, 1] 。

这道题很有意思的是发现了1 <= $$h^i$$, $$y^j$$ <= 100这个条件,所以我们可以把纵坐标相同的点放到一起,然后去扫描每个点的有效值,去求和即可

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> countRectangles(vector<vector<int>>& rectangles, vector<vector<int>>& points) {
        vector<vector<int>> mp(101);
        for(auto i:rectangles){
            mp[i[1]].push_back(i[0]);
        }
        for(auto &i :mp){
            sort(i.begin(),i.end());
        }
        vector<int> ans;
        for(auto i : points){
            int x=i[0],y=i[1];
            int cnt=0;
            for(int q =100;q>=y;q--){
                if(mp[q].size()==0){
                    continue;
                }
                cnt+=mp[q].end()-lower_bound(mp[q].begin(),mp[q].end(),x);
            }
            ans.push_back(cnt);
        }
        return ans;
    }
};

int main(){
    Solution s;
    vector<vector<int>> rectangles={{1,2},{2,3},{2,5}};
    vector<vector<int>> points={{2,1},{1,4}};
    vector<int>ans=s.countRectangles(rectangles,points);
    for(auto i: ans){
        cout<<i<<" ";
    }
}

T4花期内花的数目

给你一个下标从 0 开始的二维整数数组 flowers ,其中 flowers[i] = [starti, endi] 表示第 i 朵花的 花期 从 starti 到 endi (都 包含)。同时给你一个下标从 0 开始大小为 n 的整数数组 persons ,persons[i] 是第 i 个人来看花的时间。

请你返回一个大小为 n 的整数数组 answer ,其中 answer[i]是第 i 个人到达时在花期内花的 数目 。

img

输入:flowers = [[1,6],[3,7],[9,12],[4,13]], persons = [2,3,7,11]
输出:[1,2,2,2]
解释:上图展示了每朵花的花期时间,和每个人的到达时间。
对每个人,我们返回他们到达时在花期内花的数目。

分析:

本题就是找每个时间点上的重叠,这个和前面出现的存储量,存货人数等题很相似,但是需要做一下哈希表补全才可以。

#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& persons) {
        map<int,int> mp;
        for(auto line : flowers){
            mp[line[0]]++;
            mp[line[1]+1]--;
        }
        vector<int> idx(persons.size());
        for(int i = 0 ;i<persons.size();i++){
            idx[i]=i;
        }
        sort(idx.begin(),idx.end(),[&](int a,int b){
            return persons[a]<persons[b];
        });
        vector<int> ans(persons.size());
        auto it=mp.begin();
        int now=0;
        for(int i =0 ; i<persons.size();i++){
            while(it->first<=persons[idx[i]]&&it!=mp.end()){
                now+=it->second;
                it++;
            }
            ans[idx[i]]=now;
        }
        return ans;
    }
};
int main(){
    Solution s;
    vector<vector<int>> flowers={{1,6},{3,7},{9,12},{4,13}};
    vector<int> persons={2,3,7,11};
    vector<int>ans=s.fullBloomFlowers(flowers,persons);
    for(auto i: ans){
        cout<<i<<" ";
    }

}

绝对不是恋爱脑!