网格照明
网格照明
class Solution {
public int[] gridIllumination(int n,int[][] lamps,int[][] queries){
Map<Integer,Integer> row=new HashMap<Integer,Integer>();
Map<Integer,Integer> col=new HashMap<Integer,Integer>();
Map<Integer,Integer> dia=new HashMap<Integer,Integer>();
Map<Integer,Integer> re_dia=new HashMap<Integer,Integer>();
Set<Long> points=new HashSet<Long>();
for (int[] lamp : lamps) {
int a=lamp[0];int b=lamp[1];
if(!points.add(hash(a,b))){//如果已经统计过,不需要重复统计
continue;
}
row.put(a,row.getOrDefault(a,0)+1);
col.put(b,col.getOrDefault(b,0)+1);
dia.put(a+b,dia.getOrDefault(a+b,0)+1);
re_dia.put(a-b,re_dia.getOrDefault(a-b,0)+1);
}
int m=queries.length;
int[] res=new int[m];
for (int i=0;i<queries.length;i++) {
//判断是否行列
int r=queries[i][0];int c=queries[i][1];
if(row.getOrDefault(r,0)>0){
res[i]=1;
}else if(col.getOrDefault(c,0)>0){
res[i]=1;
}else if(dia.getOrDefault(r+c,0)>0){
res[i]=1;
}else if(re_dia.getOrDefault(r-c,0)>0){
res[i]=1;
}
//将8个位置灯关闭
for(int x=r-1;x<=r+1;x++){
for(int y=c-1;y<=c+1;y++){
if(x<0||x>=n||y<0||y>=n){
continue;
}
if(points.remove(hash(x,y))){
//有灯关闭
row.put(x,row.get(x)-1);
if(row.get(x)==0){
row.remove(x);
}
col.put(y,col.get(y)-1);
if(col.get(y)==0){
col.remove(y);
}
dia.put(x+y,dia.get(x+y)-1);
if(dia.get(x+y)==0){
dia.remove(x+y);
}
re_dia.put(x-y,re_dia.get(x-y)-1);
if(re_dia.get(x-y)==0){
re_dia.remove(x-y);
}
}
}
}
}
return res;
}
public long hash(int a,int b){
return (long)a+((long)b<<32);
}
}
统计点对的数目
统计点对的数目
class Solution {
int n;
public int[] countPairs(int n,int[][] edges,int[] queries){
this.n=n;
int[] deg=new int[n+1];
Map<Integer,Integer> cnt=new HashMap<Integer,Integer>();//对每一条边进行计数
List<int[]> e=new ArrayList<int[]>();
for (int[] edge : edges) {
int a=edge[0];int b=edge[1];
deg[a]++;deg[b]++;
//将相同的边进行编码
int encode_id=encode(a,b);
//保存去重之后的边
if(!cnt.containsKey(encode_id)){
e.add(new int[]{a,b});
}
cnt.put(encode_id,cnt.getOrDefault(encode_id,0)+1);
}
//将所有的点按照度排序
int[] sortedDeg = Arrays.copyOfRange(deg, 1,n + 1);
Arrays.sort(sortedDeg);
int[] res=new int[queries.length];
for(int i=0;i<queries.length;i++){
int l=0,r=n-1;
int count=0;
while(l<n){//对于每一个左端点
while(r>l&&sortedDeg[l]+sortedDeg[r]>queries[i]){
r--;
}
count+=(n-Math.max(l,r)-1);//排序之后满足条件的点对
l++;
}
//可能重复计数的边
for(int j=0;j<e.size();j++){
int p=e.get(j)[0];int q=e.get(j)[1];
int idx=encode(p,q);
if(deg[p]+deg[q]>queries[i]&°[p]+deg[q]-cnt.get(idx)<=queries[i]){
count--;
}
}
res[i]=count;
}
return res;
}
public int encode(int a,int b){
return Math.max(a,b)*(n+1)+Math.min(a,b);
}
}