每日一题(2022-01-26):检测正方形

每日一题(2022-01-26):检测正方形

来源:力扣
难度:中等
题目:2013. 检测正方形

题目详情

原题截图1.png
原题截图2.png
原题截图3.png

题解思路

官方题解方法一就很精简巧妙,直接参考,不做赘述:
官方题解.png
题外话,总结两点:

  1. 多重哈希确实能解决不少问题,尤其是对于需要多个变量才能定位的元素,使用哈希表嵌套可以快速检索;
  2. 结构化绑定作为C++17的新特性,搭配auto写起来十分舒服。

代码结果

class DetectSquares {
public:
    DetectSquares() {

    }
    
    void add(vector<int> point) {
        __m_mapCount[point[1]][point[0]]++;
    }
    
    int count(vector<int> point) {
        int iTotalCount  = 0;
        int x = point[0], y = point[1];
        if (!__m_mapCount.count(y)) return 0;
        unordered_map<int, int>& mapYCount = __m_mapCount[y];
        for (auto& [iY, iYCount] : __m_mapCount)
        {
            if (iY != y)
            {
                int iLenSide = iY - y;
                iTotalCount += (iYCount.count(x) ? iYCount[x] : 0) 
                    * (mapYCount.count(x + iLenSide) ? mapYCount[x + iLenSide] : 0) 
                    * (iYCount.count(x + iLenSide) ? iYCount[x + iLenSide] : 0);
                iTotalCount += (iYCount.count(x) ? iYCount[x] : 0) 
                    * (mapYCount.count(x - iLenSide) ? mapYCount[x - iLenSide] : 0) 
                    * (iYCount.count(x - iLenSide) ? iYCount[x - iLenSide] : 0);
            }
        }
        return iTotalCount;
    }

private:
    unordered_map<int, unordered_map<int, int>> __m_mapCount;
};

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

运行结果.png