Daily question 2013 Detect square

topic ： stay x-y The number of schemes that plane detection can form an axis aligned square .

The main points of ：1. Shaft alignment, ： The side of the square is parallel to the coordinate axis .2. There can be multiple points at the same position on the plane .

Explain ：（ Refer to the official explanation ）

Use dictionary nesting to store points .{y:{x: Number }}

When calculating the square scheme, you can enumerate y2 Determine the side length of the square abs(y2-y), So as to determine the four points of the square .

class DetectSquares:

    def __init__(self):
       self.map = defaultdict(Counter)
       # {y:{x: Number }}


    def add(self, point: List[int]) -> None:
        x,y = point
        self.map[y][x] += 1


    def count(self, point: List[int]) -> int:
        # Number of axis aligned squares 
        res = 0
        x,y = point
        if not y in self.map:
            return 0
        yCnt = self.map[y]  #y Corresponding x  Dictionaries 
        # Enumerate another y Axis 
        for y2,y2Cnt in self.map.items():
            if y2 != y:
                d = y2 - y
                res += y2Cnt[x]  * y2Cnt[x+d] * yCnt[x+d]
                res += y2Cnt[x]  * y2Cnt[x-d] * yCnt[x-d]
        return res



# Your DetectSquares object will be instantiated and called as such:
# obj = DetectSquares()
# obj.add(point)
# param_2 = obj.count(point)

  Add ：defaultdict() and Counter

collections --- Container data type — Python 3.10.2 file

defaultdict() Returns an object similar to a dictionary . yes dict Subclasses of .

This object contains a named  default_factory  Properties of , When constructing , The first parameter is used to provide the initial value for the attribute , The default is  None. All other parameters （ Including keyword parameters ） Are equivalent to passing on to  dict  Constructor for .

When the key value cannot be found ,defaultdict Would call default_factory Method provides default values . in other words , Equivalent to

Dictionary d.setdefault(k, default_factory())

defaultdict Example ：

Use  list  As  default_factory, Easily （ key - A pair of values ） The sequence is converted to （ key - A list of ） Dictionaries ：

>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
...     d[k].append(v)
...
>>> sorted(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

When each key first meets , It's not in the dictionary yet , So automatically create this entry , That is to call  default_factory  Method , Returns an empty  list. list.append()  Add values to this new list . When the key is accessed again , Just operate normally ,list.append()  Add another value to the list . This is better than its equivalent method  dict.setdefault()  Be fast and simple ：

>>>

>>> d = {}
>>> for k, v in s:
...     d.setdefault(k, []).append(v)
...
>>> sorted(d.items())
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

Set up  default_factory  by  int, send  defaultdict  Used to count （ Similar to... In other languages bag or multiset）：

>>>

>>> s = 'mississippi'
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
...
>>> sorted(d.items())
[('i', 4), ('m', 1), ('p', 2), ('s', 4)]

When a letter is first encountered , It will fail the query , be  default_factory  Would call  int()  To provide an integer 0 As default . The subsequent auto increment operation establishes the count of each letter .

Counter

collections --- Container data type — Python 3.10.2 file

 Counter  yes  dict  Subclasses of , Used to count hashable objects . It's a collection , Elements are like dictionary keys (key) Same storage , Their counts are stored as values .

>>> # Tally occurrences of words in a list
>>> cnt = Counter()
>>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
...     cnt[word] += 1
>>> cnt
Counter({'blue': 3, 'red': 2, 'green': 1})

If the referenced key has no record , Just go back to one 0, Instead of popping up a  KeyError :

>>> c = Counter(['eggs', 'ham'])
>>> c['bacon']                              # count of a missing element is zero
0