每日一题:LeetCode:2013.检测正方形

浏览次数 : 次 2022-01-26

博文字数统计 : 944字 | 阅读所需时长 : 3分

× 文章目录

1. 2022-01-26：LeetCode：2013.检测正方形
1. 1.1. 1. 题目描述
2. 1.2. 2. 方法一：哈希表 & 计数

每日一题：LeetCode：2013.检测正方形
- 时间：2022-01-26
- 力扣难度：Medium
- 个人难度：Medium-
- 算法：模拟、数学、递归

2022-01-26：LeetCode：2013.检测正方形

1. 题目描述

题目：原题链接
- 给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法：
  - 添加一个在数据流中的新点到某个数据结构中。可以添加重复的点，并会视作不同的点进行处理。
  - 给你一个查询点，请你从数据结构中选出三个点，使这三个点和查询点一同构成一个面积为正的轴对齐正方形 ，统计满足该要求的方案数目。
- 轴对齐正方形是一个正方形，除四条边长度相同外，还满足每条边都与 x-轴或 y-轴平行或垂直。
- 实现 DetectSquares 类：
  - DetectSquares() 使用空数据结构初始化对象
  - void add(int[] point) 向数据结构添加一个新的点 point = [x, y]
  - int count(int[] point) 统计按上述方式与点 point = [x, y] 共同构造轴对齐正方形的方案数。
- point.length == 2
- 0 <= x, y <= 1000
- 调用 add 和 count 的 总次数 最多为 5000

2. 方法一：哈希表 & 计数

思路
- 本题要求出给定一个点和已有的点可以组成的轴对称正方形的个数(明明不是轴对称，翻译整段垮掉)
- 首先，可以使用哈希表来储存每个点，由于题目中明确说明点可以重复，所以哈希表的key存点的坐标，value存个数即可
- 其次，因为轴对称正方形的边只能平行或垂直于坐标轴，所以我们可以通过输入的点的横纵坐标，确定正方形的位置
- 然后，直接遍历哈希表，判断当前元素是否和输入点的横坐标或者纵坐标相等，如果相等，该点为正方形的第二个点，且相当于正方形的边长确定了，即其他两个点的位置也确定了，直接去哈希表里查找点的个数，最后求出总和即可
- 此外，由于点可以重复，所以结果每个正方形的个数应该是其他三个点个数的乘积
- 数组因为在哈希的时候是比较地址，所以哈希表的Key不能直接用数组形式的点，而是可以用以下几种方式
  - key为List，存点的横纵坐标，value计数
  - 自定义一个结构作为key，value计数
  - key放横坐标，value嵌套一个Map或者其他集合，存放纵坐标和计数
  - 观察本题的数据规模，横纵坐标都在0到1000之间，直接可以使用二维数组表示横纵坐标，值表示计数

题解


class DetectSquares {
    Map<Integer, Map<Integer, Integer>> pointMap;

    public DetectSquares() {
        pointMap = new HashMap<Integer, Map<Integer, Integer>>();
    }

    public void add(int[] point) {
        int x = point[0], y = point[1];
        Map<Integer, Integer> map = pointMap.getOrDefault(y, new HashMap<>());
        map.put(x, map.getOrDefault(x, 0) + 1);
        pointMap.put(y, map);
    }

    public int count(int[] point) {
        int count = 0;
        int edge = 0;
        int x = point[0], y = point[1];
        if (!pointMap.containsKey(y)) return 0;
        Map<Integer, Integer> yMap = pointMap.get(y);
        Set<Map.Entry<Integer, Map<Integer, Integer>>> entries = pointMap.entrySet();
        for (Map.Entry<Integer, Map<Integer, Integer>> entry : entries) {
            int col = entry.getKey();
            Map<Integer, Integer> map = entry.getValue();
            if (col != y) {
                edge = col - y;
                count += map.getOrDefault(x, 0) * yMap.getOrDefault(x + edge, 0) * map.getOrDefault(x + edge, 0);
                count += map.getOrDefault(x, 0) * yMap.getOrDefault(x - edge, 0) * map.getOrDefault(x - edge, 0);
            }
        }
        return count;
    }
}

查询正方形个数方法的复杂度分析：n 是点的个数
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$

本文作者： Chthollists
发布时间： 2022-01-26 19:16:29
最后更新： 2022-02-20 13:34:08
本文标题： 每日一题:LeetCode:2013.检测正方形
本文链接： https://chthollists.github.io/post/32c2ed53.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可。转载请注明作者和出处！