网站首页 > java教程 正文
题目描述
给你一个在 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 /
本文作者：力扣
声明：本文归“力扣”版权所有，如需转载请联系。
猜你喜欢
- 2024-10-28 如何从100亿数据快速找到目标?--红黑树
- 2024-10-28 《Java语言程序设计》测试题及参考答案(第4部分)
- 2024-10-28 全网把Map中的hash()分析的最透彻的文章，别无二家
- 2024-10-28 对一致性Hash算法，Java代码实现的深入研究
- 2024-10-28 我去，脸皮厚啊，你竟然使用==比较浮点数?
- 2024-10-28 Java中::这个符号是干嘛的（java /符号）
- 2024-10-28 Java封神之路-拿下Byte（java游戏封神榜）
欢迎 你 发表评论:
- 07-15采用Oracle OSB总线进行服务注册和接入
- 07-15javaEE 新闻管理系统 oracle11+tomcat6
- 07-15从Oracle演进看数据库技术的发展（oracle数据库发展史）
- 07-15如何升级oracle数据库安全补丁（oraclepsu补丁升级）
- 07-15【权威发布】关于Oracle WebLogic Server未授权远程代码执行高危漏洞的预警通报
- 07-15【mykit-data】 数据库同步工具（数据库表同步工具）
- 07-15[Java速成] 数据库基础，Connector/J、JDBC、JPA的关系(day 7)
- 07-15Google前工程主管“入住”Oracle（google浏览器找不到以前的书签）
- 最近发表
-
- 采用Oracle OSB总线进行服务注册和接入
- javaEE 新闻管理系统 oracle11+tomcat6
- 从Oracle演进看数据库技术的发展（oracle数据库发展史）
- 如何升级oracle数据库安全补丁（oraclepsu补丁升级）
- 【权威发布】关于Oracle WebLogic Server未授权远程代码执行高危漏洞的预警通报
- 【mykit-data】 数据库同步工具（数据库表同步工具）
- [Java速成] 数据库基础，Connector/J、JDBC、JPA的关系(day 7)
- Google前工程主管“入住”Oracle（google浏览器找不到以前的书签）
- Oracle数据库云服务系列新增前所未有的企业级功能
- 直播预告丨如何实现Oracle存储过程到java的一键转化
- 标签列表
-
- java反编译工具 (77)
- java反射 (57)
- java接口 (61)
- java随机数 (63)
- java7下载 (59)
- java数据结构 (61)
- java 三目运算符 (65)
- java对象转map (63)
- Java继承 (69)
- java字符串替换 (60)
- 快速排序java (59)
- java并发编程 (58)
- java api文档 (60)
- centos安装java (57)
- java调用webservice接口 (61)
- java深拷贝 (61)
- 工厂模式java (59)
- java代理模式 (59)
- java.lang (57)
- java连接mysql数据库 (67)
- java重载 (68)
- java 循环语句 (66)
- java反序列化 (58)
- java时间函数 (60)
- java是值传递还是引用传递 (62)
本文暂时没有评论，来添加一个吧(●'◡'●)