百度360必应搜狗淘宝本站头条
mqtt服务器xftp6mybatiscollectionkeyerrorc#var
当前位置：网站首页 > 热门文章 > 正文

LeetCode 力扣官方题解 | 2013. 检测正方形

bigegpt 2024-08-09 11:08 2 浏览


题目描述

给你一个在 x - y 平面上的点构成的数据流。设计一个满足下述要求的算法：

添加 一个在数据流中的新点到某个数据结构中。可以添加 重复 的点，并会视作不同的点进行处理。

给你一个查询点，请你从数据结构中选出三个点，使这三个点和查询点一同构成一个 面积为正 的 轴对齐正方形 ，统计 满足该要求的方案数目。

轴对齐正方形 是一个正方形，除四条边长度相同外，还满足每条边都与 x- 轴 或 y- 轴 平行或垂直。

实现 DetectSquares 类：

  • DetectSquares( ) 使用空数据结构初始化对象
  • void add (int [ ] point) 向数据结构添加一个新的点 point = [x, y]
  • int count (int [ ] point) 统计按上述方式与点 point = [x, y] 共同构造轴对齐正方形的方案数。


示例：



输入：
["DetectSquares", "add", "add", "add", "count", "count", "add", "count"]
[[], [[3, 10]], [[11, 2]], [[3, 2]], [[11, 10]], [[14, 8]], [[11, 2]], [[11, 10]]]
输出：
[null, null, null, null, 1, 0, null, 2]


解释：
DetectSquares detectSquares = new DetectSquares();
detectSquares.add([3, 10]);
detectSquares.add([11, 2]);
detectSquares.add([3, 2]);
detectSquares.count([11, 10]); // 返回 1 。你可以选择：
                               //   - 第一个，第二个，和第三个点
detectSquares.count([14, 8]);  // 返回 0 。查询点无法与数据结构中的这些点构成正方形。
detectSquares.add([11, 2]);    // 允许添加重复的点。
detectSquares.count([11, 10]); // 返回 2 。你可以选择：
                               //   - 第一个，第二个，和第三个点
                               //   - 第一个，第三个，和第四个点


提示：

  • point . length == 2
  • 0 <= x, y <= 1000
  • point . length 调用 add 和 count 的 总次数 最多为 5000


解决方案

方法一：哈希表

思路

先考虑如何实现 int count (int [ ] point)，记输入的 point 的横纵坐标分别为 x 和 y。则形成的正方形的上下两条边中，其中一条边的纵坐标为 y ，我们枚举另一条边的纵坐标为 col，则正方形的边长 d 为 ∣ y ? col ∣ 且大于 0。有了其中一个点的坐标（x ，y）和一条横边的纵坐标 col，我们可以得到正方形的四个点的坐标分别为（x，y），（x，col），（x + d，y），（x + d，col）或（x，y），（x，col），（x - d，y），（x - d，col）。


据此，我们可以用一个哈希表来存储 void add (int [ ] point) 函数中加入的点。先把点按照行来划分，键为行的纵坐标，值为另一个哈希表，其中键为该行中的点的横坐标，值为这样的点的个数。因为点会重复出现，所以计算正方形的个数时需要把另外三个坐标出现的次数相乘。


代码

Python3

class DetectSquares:


    def __init__(self):
        self.map = defaultdict(Counter)


    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]


        for col, colCnt in self.map.items():
            if col != y:
                # 根据对称性，这里可以不用取绝对值
                d = col - y
                res += colCnt[x] * yCnt[x + d] * colCnt[x + d]
                res += colCnt[x] * yCnt[x - d] * colCnt[x - d]
        
        return res


Java

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


    public DetectSquares() {
        cnt = new HashMap<Integer, Map<Integer, Integer>>();
    }


    public void add(int[] point) {
        int x = point[0], y = point[1];
        cnt.putIfAbsent(y, new HashMap<Integer, Integer>());
        Map<Integer, Integer> yCnt = cnt.get(y);
        yCnt.put(x, yCnt.getOrDefault(x, 0) + 1);
    }


    public int count(int[] point) {
        int res = 0;
        int x = point[0], y = point[1];
        if (!cnt.containsKey(y)) {
            return 0;
        }
        Map<Integer, Integer> yCnt = cnt.get(y);
        Set<Map.Entry<Integer, Map<Integer, Integer>>> entries = cnt.entrySet();
        for (Map.Entry<Integer, Map<Integer, Integer>> entry : entries) {
            int col = entry.getKey();
            Map<Integer, Integer> colCnt = entry.getValue();
            if (col != y) {
                // 根据对称性，这里可以不用取绝对值
                int d = col - y;
                res += colCnt.getOrDefault(x, 0) * yCnt.getOrDefault(x + d, 0) * colCnt.getOrDefault(x + d, 0);
                res += colCnt.getOrDefault(x, 0) * yCnt.getOrDefault(x - d, 0) * colCnt.getOrDefault(x - d, 0);
            }
        }
        return res;
    }
}


C#

public class DetectSquares {
    Dictionary<int, Dictionary<int, int>> cnt;


    public DetectSquares() {
        cnt = new Dictionary<int, Dictionary<int, int>>();
    }


    public void Add(int[] point) {
        int x = point[0], y = point[1];
        if (!cnt.ContainsKey(y)) {
            cnt.Add(y, new Dictionary<int, int>());
        }
        Dictionary<int, int> yCnt = cnt[y];
        if (!yCnt.ContainsKey(x)) {
            yCnt.Add(x, 0);
        }
        yCnt[x]++;
    }


    public int Count(int[] point) {
        int res = 0;
        int x = point[0], y = point[1];
        if (!cnt.ContainsKey(y)) {
            return 0;
        }
        Dictionary<int, int> yCnt = cnt[y];
        foreach(KeyValuePair<int, Dictionary<int, int>> pair in cnt) {
            int col = pair.Key;
            Dictionary<int, int> colCnt = pair.Value;
            if (col != y) {
                // 根据对称性，这里可以不用取绝对值
                int d = col - y;
                int cnt1 = colCnt.ContainsKey(x) ? colCnt[x] : 0;
                int cnt2 = colCnt.ContainsKey(x + d) ? colCnt[x + d] : 0;
                int cnt3 = colCnt.ContainsKey(x - d) ? colCnt[x - d] : 0;
                res += (colCnt.ContainsKey(x) ? colCnt[x] : 0) * (yCnt.ContainsKey(x + d) ? yCnt[x + d] : 0) * (colCnt.ContainsKey(x + d) ? colCnt[x + d] : 0);
                res += (colCnt.ContainsKey(x) ? colCnt[x] : 0) * (yCnt.ContainsKey(x - d) ? yCnt[x - d] : 0) * (colCnt.ContainsKey(x - d) ? colCnt[x - d] : 0);
            }
        }
        return res;
    }
}


C++

class DetectSquares {
public:
    unordered_map<int, unordered_map<int, int>> cnt;
    DetectSquares() {


    }
    
    void add(vector<int> point) {
        int x = point[0], y = point[1];
        cnt[y][x]++;
    }
    
    int count(vector<int> point) {
        int res = 0;
        int x = point[0], y = point[1];
        if (!cnt.count(y)) {
            return 0;
        }
        unordered_map<int, int> & yCnt = cnt[y];
        for (auto & [col, colCnt] : cnt) {
            if (col != y) {
                // 根据对称性，这里可以不用取绝对值
                int d = col - y;
                res += (colCnt.count(x) ? colCnt[x] : 0) * (yCnt.count(x + d) ? yCnt[x + d] : 0) * 
                       (colCnt.count(x + d)? colCnt[x + d] : 0);
                res += (colCnt.count(x) ? colCnt[x] : 0) * (yCnt.count(x - d) ? yCnt[x - d] : 0) * 
                       (colCnt.count(x - d) ? colCnt[x - d] : 0);
            }
        }
        return res;
    }
};


C

typedef struct {
    int key; 
    int val;
    UT_hash_handle hh;         
} HashMapEntry;


typedef struct {
    int key;
    HashMapEntry * obj;
    UT_hash_handle hh;     
} HashMapDictEntry;


int hashMapGetVal(const HashMapEntry ** obj, int key) {
    HashMapEntry * pEntry = NULL;
    HASH_FIND(hh, *obj, &key, sizeof(int), pEntry);
    if (NULL == pEntry) {
        return 0;
    }
    return pEntry->val;
}


void hashMapFree(HashMapEntry ** obj) {
    HashMapEntry *curr = NULL, *next = NULL;
    HASH_ITER(hh, *obj, curr, next)
    {
        HASH_DEL(*obj, curr);  
        free(curr);      
    }
}


typedef struct {
    HashMapDictEntry * dict;
} DetectSquares;


DetectSquares* detectSquaresCreate() {
    DetectSquares * obj = (DetectSquares *)malloc(sizeof(DetectSquares));
    obj->dict = NULL;
    return obj;
}


void detectSquaresAdd(DetectSquares* obj, int* point, int pointSize) {
    int x = point[0], y = point[1];
    HashMapDictEntry * pEntry = NULL;
    HashMapEntry * pItemEntry = NULL;
    
    HASH_FIND(hh, obj->dict, &y, sizeof(int), pEntry);
    if (NULL == pEntry) {
        pItemEntry = (HashMapEntry *)malloc(sizeof(HashMapEntry));
        pItemEntry->key = x;
        pItemEntry->val = 1;
        pEntry = (HashMapDictEntry *)malloc(sizeof(HashMapDictEntry));
        pEntry->key = y;
        pEntry->obj = NULL;
        HASH_ADD(hh, pEntry->obj, key, sizeof(int), pItemEntry);
        HASH_ADD(hh, obj->dict, key, sizeof(int), pEntry);
    } else {
        HASH_FIND(hh, pEntry->obj, &x, sizeof(int), pItemEntry);
        if (NULL == pItemEntry) {
            pItemEntry = (HashMapEntry *)malloc(sizeof(HashMapEntry));
            pItemEntry->key = x;
            pItemEntry->val = 1;
            HASH_ADD(hh, pEntry->obj, key, sizeof(int), pItemEntry);
        } else {
            pItemEntry->val++;
        }
    }
}


int detectSquaresCount(DetectSquares* obj, int* point, int pointSize) {
    int res = 0;
    int x = point[0], y = point[1];
    HashMapDictEntry * pEntry = NULL;
    HashMapEntry * yCnt = NULL;
    HASH_FIND(hh, obj->dict, &y, sizeof(int), pEntry);
    if (NULL == pEntry) {
        return 0;
    }
    yCnt = pEntry->obj;
    HashMapDictEntry *curr = NULL, *next = NULL;
    HASH_ITER(hh, obj->dict, curr, next) {
        int col = curr->key;
        HashMapEntry * colCnt = curr->obj;
        if (col != y) {
            // 根据对称性，这里可以不用取绝对值
            int d = col - y;
            res += hashMapGetVal(&colCnt, x) * hashMapGetVal(&yCnt, x + d) * hashMapGetVal(&colCnt, x + d);
            res += hashMapGetVal(&colCnt, x) * hashMapGetVal(&yCnt, x - d) * hashMapGetVal(&colCnt, x - d);
        }   
    }
    return res;
}


void detectSquaresFree(DetectSquares* obj) {
    HashMapDictEntry *curr = NULL, *next = NULL;
    HASH_ITER(hh, obj->dict, curr, next)
    {
        hashMapFree(&(curr->obj));
        HASH_DEL(obj->dict, curr); 
        free(curr);      
    }
}


JavaScript

var DetectSquares = function() {
    this.cnt = new Map();
};


DetectSquares.prototype.add = function(point) {
    const x = point[0], y = point[1];
    if (!this.cnt.has(y)) {
        this.cnt.set(y, new Map());
    }
    const yCnt = this.cnt.get(y);
    yCnt.set(x, (yCnt.get(x) || 0) + 1);
};


DetectSquares.prototype.count = function(point) {
    let res = 0;
    let x = point[0], y = point[1];
    if (!this.cnt.has(y)) {
        return 0;
    }
    const yCnt = this.cnt.get(y);
    const entries = this.cnt.entries();
    for (const [col, colCnt] of entries) {
        if (col !== y) {
            // 根据对称性，这里可以不用取绝对值
            let d = col - y;
            res += (colCnt.get(x) || 0) * (yCnt.get(x + d) || 0) * (colCnt.get(x + d) || 0);
            res += (colCnt.get(x) || 0) * (yCnt.get(x - d) || 0) * (colCnt.get(x - d) || 0);
        }
    }
    return res;
};


Golang

type DetectSquares map[int]map[int]int


func Constructor() DetectSquares {
    return DetectSquares{}
}


func (s DetectSquares) Add(point []int) {
    x, y := point[0], point[1]
    if s[y] == nil {
        s[y] = map[int]int{}
    }
    s[y][x]++
}


func (s DetectSquares) Count(point []int) (ans int) {
    x, y := point[0], point[1]
    if s[y] == nil {
        return
    }
    yCnt := s[y]
    for col, colCnt := range s {
        if col != y {
            // 根据对称性，这里可以不用取绝对值
            d := col - y
            ans += colCnt[x] * yCnt[x+d] * colCnt[x+d]
            ans += colCnt[x] * yCnt[x-d] * colCnt[x-d]
        }
    }
    return
}


复杂度分析

  • 时间复杂度：DetectSquares( )，消耗 O(1) 时间复杂度，void add (int [ ] point) 消耗 O(1) 时间复杂度，int count (int [ ] point) 消耗 O(n) 时间复杂度 ，其中 n 为 void add (int [ ] point) 已经调用的次数。
  • 空间复杂度：DetectSquares( )消耗 O(1) 空间复杂度 void add (int [ ] point) 消耗 O(1) 空间复杂度，int count (int [ ] point) 消耗 O(1) 空间复杂度。


BY /

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。

相关推荐

【Docker 新手入门指南】第十章:Dockerfile

Dockerfile是Docker镜像构建的核心配置文件，通过预定义的指令集实现镜像的自动化构建。以下从核心概念、指令详解、最佳实践三方面展开说明，帮助你系统掌握Dockerfile的使用逻...

Windows下最简单的ESP8266_ROTS_ESP-IDF环境搭建与腾讯云SDK编译

前言其实也没啥可说的,只是我感觉ESP-IDF对新手来说很不友好,很容易踩坑,尤其是对业余DIY爱好者搭建环境非常困难,即使有官方文档,或者网上的其他文档,但是还是很容易踩坑,多研究,记住两点就行了,...

python虚拟环境迁移（python虚拟环境conda）

主机A的虚拟环境向主机B迁移。前提条件：主机A和主机B已经安装了virtualenv1.主机A操作如下虚拟环境目录：venv进入虚拟环境：sourcevenv/bin/active(1)记录虚拟环...

Python爬虫进阶教程(二):线程、协程

简介线程线程也叫轻量级进程，它是一个基本的CPU执行单元，也是程序执行过程中的最小单元，由线程ID、程序计数器、寄存器集合和堆栈共同组成。线程的引入减小了程序并发执行时的开销，提高了操作系统的并发性能...

基于网络安全的Docker逃逸（docker）

如何判断当前机器是否为Docker容器环境Metasploit中的checkcontainer模块、（判断是否为虚拟机，checkvm模块）搭配学习教程1.检查根目录下是否存在.dockerenv文...

Python编程语言被纳入浙江高考，小学生都开始学了

今年9月份开始的新学期，浙江省三到九年级信息技术课将同步替换新教材。其中，新初二将新增Python编程课程内容。新高一信息技术编程语言由VB替换为Python，大数据、人工智能、程序设计与算法按照教材...

CentOS 7下安装Python 3.10的完整过程

1.安装相应的编译工具yum-ygroupinstall"Developmenttools"yum-yinstallzlib-develbzip2-develope...

如何在Ubuntu 20.04上部署Odoo 14

Odoo是世界上最受欢迎的多合一商务软件。它提供了一系列业务应用程序，包括CRM，网站，电子商务，计费，会计，制造，仓库，项目管理，库存等等，所有这些都无缝集成在一起。Odoo可以通过几种不同的方式进...

Ubuntu 系统安装 PyTorch 全流程指南

当前环境：Ubuntu22.04，显卡为GeForceRTX3080Ti1、下载显卡驱动驱动网站：https://www.nvidia.com/en-us/drivers/根据自己的显卡型号和...

spark+python环境搭建（python 环境搭建）

最近项目需要用到spark大数据相关技术，周末有空spark环境搭起来...目标spark，python运行环境部署在linux服务器个人通过vscode开发通过远程python解释器执行代码准备...

centos7.9安装最新python-3.11.1（centos安装python环境）

centos7.9安装最新python-3.11.1centos7.9默认安装的是python-2.7.5版本，安全扫描时会有很多漏洞，比如：Python命令注入漏洞(CVE-2015-2010...

Linux系统下，五大步骤安装Python

一、下载Python包网上教程大多是通过官方地址进行下载Python的，但由于国内网络环境问题，会导致下载很慢，所以这里建议通过国内镜像进行下载例如：淘宝镜像http://npm.taobao.or...

centos7上安装python3（centos7安装python3.7.2一键脚本）

centos7上默认安装的是python2，要使用python3则需要自行下载源码编译安装。1.安装依赖yum-ygroupinstall"Developmenttools"...

利用本地数据通过微调方式训练 本地DeepSeek-R1 蒸馏模型

网络上相应的教程基本都基于LLaMA-Factory进行，本文章主要顺着相应的教程一步步实现大模型的微调和训练。训练环境：可自行定义，mac、linux或者window之类的均可以，本文以ma...

【法器篇】天啦噜，库崩了没备份（天啦噜是什么意思?）

背景数据库没有做备份，一天突然由于断电或其他原因导致无法启动了，且设置了innodb_force_recovery=6都无法启动，里面的数据怎么才能恢复出来？本例采用解析建表语句+表空间传输的方式进行...

一周热门
最近发表
标签列表