前言

• 大家好，我是新人简书博主：「 个人主页」主要分享程序员生活、编程技术、* * 以及每日的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 == 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 是点的个数

  • 时间复杂度：
  • 空间复杂度：

最后

如果本文有所帮助的话，欢迎大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的其他平台，上面会更新Java面经、八股文、刷题记录等等，欢迎大家光临交流，谢谢！

• 「个人博客」
• 「掘金」
• 「LeetCode」