This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together

preface

Hi, I’m the Rookie Nuggets blogger: “Nuggets of Gold” is updating LeetCode with one problem of the day every day, and some of the problem solutions published will refer to other leaders’ ideas (the link to reference materials will be placed at the bottom). Welcome to follow me ~ ~ ~ Meanwhile, we are also doing other special types of problem brushing and problem solving activities. Today is the 30th day of writing solutions (haha, started on Christmas 21). Cheer up!

  • LeetCode: 2013
    • Time: 2022-01-26
    • Strength button difficulty: Medium
    • Personal difficulty: Medium-
    • Algorithms: simulation, mathematics, recursion

2022-01-26: LeetCode: 2013. Check the square

1. Topic description

  • Title: Original title link

    • I give you a data stream of points in the X-y plane. Design an algorithm that meets the following requirements:
      • Adds a new point in the data flow to a data structure. Duplicate points can be added and treated as separate points.
      • Give you a query point, please select three points from the data structure, make these three points and query points together form a positive area of the axis alignment square, count the number of schemes that meet the requirements.
    • An axis aligned square is a square where, in addition to having four sides of the same length, each side is parallel or perpendicular to the X-axis or Y-axis.
    • To implement the DetectSquares class:
      • DetectSquares()Initialize an object with an empty data structure
      • void add(int[] point)Add a new point to the data structure point = [x, y]
      • int count(int[] point)Count the number of schemes for constructing an axially aligned square with point = [x, y] in the above way.
    • point.length == 2
    • 0 <= x, y <= 1000
    • calladd 和 count 的 The total number ofFor the most5000

2. Method one: hash table & counting

  • Train of thought

    • The number of axisymmetric squares that can be formed by a given point and an existing point
    • First of all, you can use a hash table to store each point. Since the question clearly states that points can be repeated, the hash table can store the coordinates of the key points and the number of values
    • Secondly, because the sides of an axisymmetric square can only be parallel or perpendicular to the coordinate axis, we can determine the position of the square by the horizontal and vertical coordinates of the input points
    • Then traverse hash table directly, whether the current element and the input point equals the horizontal or vertical, if equal, point to the square of the second point, and the equivalent of a square side length determined, namely the location of the other two points are also identified, go directly to the hash table to find the number of points, finally to find the sum
    • Furthermore, since the points can be repeated, the resulting number of points per square should be the product of the other three points
    • An array ofSince we compare addresses when we hash, the keys of a hash table can be used in the following ways, rather than as arrays of points
      • Key = List, store the horizontal and vertical coordinates of the point, value count
      • Customize a structure to count keys and values
      • Key sets the abscissa, value sets a Map or other set to store the ordinate and count
      • If you look at the size of the data in this case, the horizontal and vertical coordinates are between 0 and 1000, and you can use a two-dimensional array to represent the horizontal and vertical coordinates, and the value is the count

  • Answer key

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

    public DetectSquares(a) {
        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); }}returncount; }}Copy the code

  • Query the number of squares method complexity analysis: n is the number of points

    • Time complexity: O(n)O(n)O(n)
    • Space complexity: O(1)O(1)O(1)

The last

If this article is helpful, you are welcome to give three even “thumbs up” & “favorites” & “attention” ~ ~ ~ also hope that you have time to visit my other platform, which will update the Java face classics, eight-part essay, brush problem records and so on, welcome to visit and exchange, thank you!

  • “Personal Blog”
  • “LeetCode”
  • “Jane”