每日一题 2013. 检测正方形

题：在x-y平面检测可以构成轴对齐正方形的方案数。

要点：1.轴对齐：正方形的边和坐标轴平行。2.平面上同一位置的点可有多个。

解：（参考官方题解）

使用字典嵌套来存储点。{y:{x:数量}}

计算正方形方案时可以枚举y2确定正方形边长abs(y2-y)，从而确定正方形的四个点。

class DetectSquares:
 
    def __init__(self):
       self.map = defaultdict(Counter)
       # {y:{x:数量}}
 
 
    def add(self, point: List[int]) -> None:
        x,y = point
        self.map[y][x] += 1
 
 
    def count(self, point: List[int]) -> int:
        #轴对齐正方形数
        res = 0
        x,y = point
        if not y in self.map:
            return 0
        yCnt = self.map[y]  #y对应的x 字典
        #枚举另一个y轴
        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)

补充：defaultdict() 和Counter

collections --- 容器数据类型 — Python 3.10.2 文档

defaultdict()返回一个类似字典的对象。是dict的子类。

本对象包含一个名为 default_factory 的属性，构造时，第一个参数用于为该属性提供初始值，默认为 None。所有其他参数（包括关键字参数）都相当于传递给 dict 的构造函数。

当无法找到键值时，defaultdict会调用default_factory方法提供默认值。也就是说，等价于

字典的d.setdefault(k, default_factory())

defaultdict例子：

使用 list 作为 default_factory，很轻松地将（键-值对组成的）序列转换为（键-列表组成的）字典：

>>> 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])]

当每个键第一次遇见时，它还没有在字典里面，所以自动创建该条目，即调用 default_factory 方法，返回一个空的 list。 list.append() 操作添加值到这个新的列表里。当再次存取该键时，就正常操作，list.append() 添加另一个值到列表中。这比它的等价方法 dict.setdefault() 要快速和简单：

>>>

>>> d = {}

>>> for k, v in s:

...     d.setdefault(k, []).append(v)

...

>>> sorted(d.items())

[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

设置 default_factory 为 int，使 defaultdict 用于计数（类似其他语言中的 bag 或 multiset）：

>>>

>>> s = 'mississippi'

>>> d = defaultdict(int)

>>> for k in s:

...     d[k] += 1

...

>>> sorted(d.items())

[('i', 4), ('m', 1), ('p', 2), ('s', 4)]

当一个字母首次遇到时，它会查询失败，则 default_factory 会调用 int() 来提供一个整数 0 作为默认值。后续的自增操作建立起对每个字母的计数。

Counter

collections --- 容器数据类型 — Python 3.10.2 文档

Counter 是 dict 的子类，用于计数可哈希对象。它是一个集合，元素像字典键(key)一样存储，它们的计数存储为值。

>>> # 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})

如果引用的键没有任何记录，就返回一个0，而不是弹出一个 KeyError :

>>> c = Counter(['eggs', 'ham'])

>>> c['bacon']                              # count of a missing element is zero

0