昨天的天梯赛打的稀烂,我感觉自己的阅读理解水平好差,全程都没怎么写到算法题,都在和模拟题阅读理解题做斗争,题目都看不懂(甚至读了假题),模拟都模拟不出来,该加训了!!!
这场周赛感觉是离散化+差分场??(感觉后两题都可以差分做)
1.多个数组求交集
考点:模拟,STL
class Solution {
public:
set<int>sb;
int cnt[1100];
vector<int> intersection(vector<vector<int>>& nums) {
for(int i=0;i<nums.size();i++){
vector<int>t=nums[i];
for(auto x:t)cnt[x]++,sb.insert(x);
}
int len=nums.size();
vector<int>ans;
for(auto x:sb){
if(cnt[x]==len)ans.push_back(x);
}
return ans;
}
};
2.统计圆内格点数目
考点:枚举,模拟, STL (枚举半径,从蓝桥杯的扫雷学到的)
class Solution {
public:
map<pair<int,int>,bool>ma;
int countLatticePoints(vector<vector<int>>& a) {
int ans=0;
for(int i=0;i<a.size();i++){
vector<int>t=a[i];
int x=t[0],y=t[1],r=t[2];
for(int i=-r;i<=r;i++){
for(int j=-r;j<=r;j++){
int ux=x+i,uy=y+j;
if((ux-x)*(ux-x)+(uy-y)*(uy-y)<=r*r){
if(!ma[{ux,uy}])ans++,ma[{ux,uy}]=true;
}
}
}
}
return ans;
}
};
3.统计包含每个点的矩形数目
离散化,二维差分
class Solution {
public:
int b[100020][120]; //二维差分
unordered_map<int,int>hasi;
int idx=0;
vector<int> countRectangles(vector<vector<int>>& a, vector<vector<int>>& sb) {
//二维差分?
//搞离散化
vector<int>alls;
for(int i=0;i<a.size();i++){
int l=a[i][0],h=a[i][1];
alls.push_back(l);
alls.push_back(h);
}
for(int i=0;i<sb.size();i++){
int x=sb[i][0],y=sb[i][1];
alls.push_back(x);
alls.push_back(y);
}
alls.push_back(0);
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto x:alls)hasi[x]=++idx;
for(int i=0;i<a.size();i++){
int l=a[i][0],h=a[i][1];
int x1=hasi[0],y1=hasi[0],x2=hasi[l],y2=hasi[h];
//做差分
b[x1][y1]++;
b[x2+1][y1]--;
b[x1][y2+1]--;
b[x2+1][y2+1]++;
}
//求前缀和
for(int i=1;i<=idx;i++){
for(int j=1;j<=110;j++){
b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];
}
}
vector<int>ans;
for(int i=0;i<sb.size();i++){
int x=sb[i][0],y=sb[i][1];
ans.push_back(b[hasi[x]][hasi[y]]);
}
return ans;
}
};
4.花期内花的数目
考点:离散化,一维差分
class Solution {
public:
unordered_map<int,int>hasi;
int g[200010];
int idx=0;
vector<int> fullBloomFlowers(vector<vector<int>>& a, vector<int>& persons) {
//又是离散化差分?
vector<int>alls;
for(int i=0;i<a.size();i++){
int x=a[i][0],y=a[i][1];
alls.push_back(x);
alls.push_back(y);
}
for(int i=0;i<persons.size();i++){
int x=persons[i];
alls.push_back(x);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto x:alls)hasi[x]=++idx;
for(int i=0;i<a.size();i++){
int x=a[i][0],y=a[i][1];
x=hasi[x],y=hasi[y];
g[x]++;
g[y+1]--;
}
for(int i=1;i<=idx;i++)g[i]=g[i-1]+g[i];
vector<int>ans;
for(auto x:persons){
ans.push_back(g[hasi[x]]);
}
return ans;
}
};