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：
输入：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 个点。如果一个点刚好在矩形的 边上 ，这个点也被视为被矩形包含。
输入：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 个人到达时在花期内花的 数目 。
输入：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<<" ";
}
}
Comments | NOTHING