前言
- 大家好，我是新人简书博主：「 个人主页」主要分享程序员生活、编程技术、* * 以及每日的LeetCode刷题记录，欢迎大家关注我，一起学习交流，谢谢！
- 正在坚持每日更新LeetCode每日一题，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
- 同时也在进行其他专项类型题目的刷题与题解活动，相关资料也会同步到「GitHub」上面 ~
- 今天是坚持写题解的30天(haha，从21年圣诞节开始的)，大家一起加油
- 每日一题：LeetCode：2013.检测正方形
- 时间：2022-01-26
- 力扣难度：Medium
- 个人难度：Medium-
- 算法：模拟、数学、递归
LeetCode每日一题.jpg
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 == 20 <= x, y <= 1000- 调用
add和count的 总次数 最多为5000
- 给你一个在 X-Y 平面上的点构成的数据流。设计一个满足下述要求的算法：
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 是点的个数
- 时间复杂度：
- 空间复杂度：
- 时间复杂度：
最后
如果本文有所帮助的话，欢迎大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的其他平台，上面会更新Java面经、八股文、刷题记录等等，欢迎大家光临交流，谢谢！
