5877. 检测正方形 力扣周赛(中等 ) 题意读错,写复杂

5877. 检测正方形

给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法:

添加 一个在数据流中的新点到某个数据结构中。可以添加 重复 的点,并会视作不同的点进行处理。
给你一个查询点,请你从数据结构中选出三个点,使这三个点和查询点一同构成一个 面积为正 的 轴对齐正方形 ,统计 满足该要求的方案数目。
轴对齐正方形 是一个正方形,除四条边长度相同外,还满足每条边都与 x-轴 或 y-轴 平行或垂直。

实现 DetectSquares 类:

DetectSquares() 使用空数据结构初始化对象
void add(int[] point) 向数据结构添加一个新的点 point = [x, y]
int count(int[] point) 统计按上述方式与点 point = [x, y] 共同构造 轴对齐正方形 的方案数。

示例:

5877. 检测正方形   力扣周赛(中等 )   题意读错,写复杂

 

 

 

代码:

开始题目理解错了,以为是矩形,其实是正方形,

自己写的代码有点复杂,枚举对角点。。

其实:map<pair<int,int>,int>  mp;  效果等价  map<int, map<int, int>> mp; 

class DetectSquares {
public:
   
    map<pair<int,int>,int> mp;
    
    DetectSquares() {

    }
    
    void add(vector<int> point) {

      mp[make_pair(point[0],point[1])]++;
      return;
    }
    
    int count(vector<int> point) {
     int cnt=0;
     for(auto i:mp)
     {
         pair<int,int> p=i.first;
         if(p.first==point[0] || p.second==point[1]) continue;
         if(abs(p.first-point[0])!=abs(p.second-point[1])) continue;
         cnt+=mp[p]*mp[make_pair(p.first,point[1])]*mp[make_pair(point[0],p.second)];
     }
        return cnt;
    }
};

/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares* obj = new DetectSquares();
 * obj->add(point);
 * int param_2 = obj->count(point);
 */

简单写法:

class DetectSquares {
public:
    map<int, map<int, int>> mp;
    DetectSquares() {
    }
    
    void add(vector<int> point) {
        mp[point[0]][point[1]] += 1;
    }
    
    int get(int x, int y) {
        if (not mp.count(x)) return 0;
        if (not mp[x].count(y)) return 0;
        return mp[x][y];
    }
    
    int count(vector<int> point) {
        int x = point[0], y = point[1];
        int ans = 0;
        for (auto [y1, c] : mp[x]) {
            if (y1 != y) {
                ans += c * get(x + abs(y1 - y), y1) * get(x + abs(y1 - y), y);
                ans += c * get(x - abs(y1 - y), y1) * get(x - abs(y1 - y), y);
            }
        }
        return ans;
    }
};

/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares* obj = new DetectSquares();
 * obj->add(point);
 * int param_2 = obj->count(point);
 */

 

上一篇:“FPGA+CPU” 并行处理大行其道


下一篇:FPGA器件选型