LeetCode 2013. 检测正方形

2013. 检测正方形

Solution

思路:和我的思路大概一致,我想的是枚举同一行,题解是枚举同一列,因为确定一个点,长度有了,其他的点也就确定。因此枚举查询点同一列的点,然后距离有了,就在这两个高度的行中找对应的点是否存在。

class DetectSquares {
    Map<Integer, Map<Integer, Integer>> cnt;
    public DetectSquares() {
        cnt = new HashMap<Integer, Map<Integer, Integer>>();
    }
    
    public void add(int[] point) {
        int x = point[0], y = point[1];
        cnt.putIfAbsent(y, new HashMap<Integer, Integer>());
        Map<Integer, Integer> yCnt = cnt.get(y);
        yCnt.put(x, yCnt.getOrDefault(x, 0) + 1);
    }
    
    public int count(int[] point) {
        int res = 0;
        int x = point[0], y = point[1];
        if (!cnt.containsKey(y)) {
            return 0;
        }
        Map<Integer, Integer> yCnt = cnt.get(y);
        Set<Map.Entry<Integer, Map<Integer, Integer>>> entries = cnt.entrySet();
        for (Map.Entry<Integer, Map<Integer, Integer>> entry : entries) {
            int col = entry.getKey();
            Map<Integer, Integer> colCnt = cnt.get(col);
            if (col != y) {
                int d = y - col;
                res += colCnt.getOrDefault(x, 0) * yCnt.getOrDefault(x + d, 0) * colCnt.getOrDefault(x + d, 0);
                res += colCnt.getOrDefault(x, 0) * yCnt.getOrDefault(x - d, 0) * colCnt.getOrDefault(x - d, 0);
            }
        }
        return res;
    }
}

/**
 * Your DetectSquares object will be instantiated and called as such:
 * DetectSquares obj = new DetectSquares();
 * obj.add(point);
 * int param_2 = obj.count(point);
 */
上一篇:使用mybatis出现异常:invalid comparison: java.time.LocalDateTime and java.lang.String


下一篇:PTA(Advanced Level)1046.Shortest Distance