算法leetcode

用哈希表维护次小值信息

字数统计: 1.1k字   |   阅读时长: 4分
, ,

摘要: 哈希表维护的信息怎样设计

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

各位好，今天我们来看一个哈希表的灵活应用问题，主要难点在于哈希表的键和值维护什么信息，怎样设计。

题目

给你一个二维数组 points 和一个字符串 s ，其中 points[i] 表示第 i 个点的坐标，s[i] 表示第 i 个点的 标签 。

如果一个正方形的中心在 (0, 0) ，所有边都平行于坐标轴，且正方形内 不 存在标签相同的两个点，那么我们称这个正方形是 合法 的。

请你返回 合法 正方形中可以包含的 最多 点数。

注意：

  • 如果一个点位于正方形的边上或者在边以内，则认为该点位于正方形内。
  • 正方形的边长可以为零。

提示：

1
2
3
4
5
6
1 <= s.length, points.length <= 1e5
points[i].length == 2
-1e9 <= points[i][0], points[i][1] <= 1e9
s.length == points.length
points 中的点坐标互不相同。
s 只包含小写英文字母。

示例 1：

输入：points = [[2,2],[-1,-2],[-4,4],[-3,1],[3,-3]], s = “abdca”
输出：2
解释：
边长为 4 的正方形包含两个点 points[0] 和 points[1] 。

示例 2：

输入：points = [[1,1],[-2,-2],[-2,2]], s = “abb”
输出：1
解释：
边长为 2 的正方形包含 1 个点 points[0] 。

示例 3：

输入：points = [[1,1],[-1,-1],[2,-2]], s = “ccd”
输出：0
解释：
任何正方形都无法只包含 points[0] 和 points[1] 中的一个点，所以合法正方形中都不包含任何点。

题解

算法: 哈希表

假设共有 $m$ 个标签，那么一个正方形想要合法，需要该正方形在每个标签 t 上都合法才行，也就是该正方形要么没有围到 t，要么只围到一个 t。

对于一个标签 t，考虑中心在原点的正方形边长从 0 开始逐渐变大的过程。一开始没有围到 t，随着边长继续变大，将围到第 1 个 t，边长继续变大，可能会在某个边界位置上围到第二个 t。记围到第 2 个 t 的正方形的边长的一半为 $r_{t}$。那么最终的合法正方形边长的一半就必须小于 $r_{t}$，否则在标签 t 上就不合法。

对于一个位置 $(x, y)$，能够围住该位置的中心在原点的正方形，其边长的一半至少为 $\max(|x|, |y|)$，这个值越小，说明围住该位置所需的正方形边长越小，我们称这个值 $\max(|x|, |y|)$ 为位置 $(x,y)$ 到原点的切比雪夫距离。

综上，我们的算法流程如下：

首先枚举所有的点及其对应标签，进行预处理。对每个标签 $t = 1, 2, …, m$，维护距离远点第二小的切比雪夫距离，记为 $r_{t}$。

然后遍历所有标签 $R = \min\limits_{1\leq t\leq m}(r_{t} - 1)$ 记为合法正方形的最大半径。

接下来再一次遍历所有标签，若其距原点的切比雪夫距离最小的点不大于 $R$ 则计数加 1。

上述过程我们要维护的是标签，及其对应的到原点的最小、次小切比雪夫距离。由于不关心标签的顺序，这个需求用哈希映射是最合适的。

代码 (Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
INF = int(2e9)

class Solution:
    def maxPointsInsideSquare(self, points: List[List[int]], s: str) -> int:
        n = len(points)
        # mapping[t] 表示种类 t 的最小、次小半径
        mapping = {}
        for i in range(n):
            x, y = points[i]
            r = max(abs(x), abs(y))
            if s[i] not in mapping:
                mapping[s[i]] = [r, INF]
            else:
                if r < mapping[s[i]][0]:
                    mapping[s[i]][1] = mapping[s[i]][0]
                    mapping[s[i]][0] = r
                elif r < mapping[s[i]][1]:
                    mapping[s[i]][1] = r
        max_r = INF
        minx_list = []
        for key in mapping:
            minx, sub_minx = mapping[key]
            minx_list.append(minx)
            max_r = min(max_r, sub_minx - 1)
        ans = len(list(filter(lambda minx: minx <= max_r, minx_list)))
        return ans
Share