LeetCode题解(1001):网格照明(Python)
发布日期:2021-06-29 20:09:41
浏览次数:2
分类:技术文章
本文共 1645 字,大约阅读时间需要 5 分钟。
题目:(困难)
标签:哈希表、几何
解法 | 时间复杂度 | 空间复杂度 | 执行用时 |
---|---|---|---|
Ans 1 (Python) | O ( L + Q ) O(L+Q) O(L+Q) | O ( L ) O(L) O(L) | 496ms (25.45%) |
Ans 2 (Python) | |||
Ans 3 (Python) |
解法一:
class Solution: def gridIllumination(self, N: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]: def is_valid(x, y): return 0 <= x < N and 0 <= y < N def near(x, y): maybe = [(x, y), (x - 1, y - 1), (x - 1, y), (x - 1, y + 1), (x, y + 1), (x + 1, y + 1), (x + 1, y), (x + 1, y - 1), (x, y - 1)] return [(x, y) for x, y in maybe if is_valid(x, y)] size1, size2 = len(lamps), len(queries) count1 = collections.Counter() count2 = collections.Counter() count3 = collections.Counter() count4 = collections.Counter() count_lamp = { (x, y) for x, y in lamps} for i in range(size1): x1, y1 = lamps[i] count1[x1] += 1 count2[y1] += 1 count3[x1 - y1] += 1 count4[x1 + y1] += 1 ans = [] for i in range(size2): # 查询 x2, y2 = queries[i] if count1[x2] > 0 or count2[y2] > 0 or count3[x2 - y2] > 0 or count4[x2 + y2] > 0: ans.append(1) else: ans.append(0) # 关灯 for x1, y1 in near(x2, y2): if (x1, y1) in count_lamp: count1[x1] -= 1 count2[y1] -= 1 count3[x1 - y1] -= 1 count4[x1 + y1] -= 1 count_lamp.remove((x1, y1)) # print(count1, count2, count3, count4, count_lamp) return ans
转载地址:https://dataartist.blog.csdn.net/article/details/109843286 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月20日 20时10分55秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
windows环境下,在node学习时使用nodemon 报错
2019-04-30
VScode自动生成项目目录文件结构的方法
2019-04-30
如何避免CSS :before、:after 中文乱码
2019-04-30
观察者模式
2019-04-30
1024. 视频拼接
2019-04-30
北漂码农的现状
2019-04-30
前端技巧必备:重置样式表reset.css
2019-04-30
css技巧--给选中的tab加下划线
2019-04-30
css技巧---位置中间的竖线|垂直居中
2019-04-30
css技巧---电子表体字体引入
2019-04-30
随笔---如何启动Redis
2019-04-30
css技巧---menu菜单加new
2019-04-30
uni-app 开发技巧:复选框list选择后value传多值问题
2019-04-30
ES6数组中删除指定元素
2019-04-30
freemarker模板当标签内的元素为空报错解决方案
2019-04-30
序列化对象
2019-04-30
理解对象意思
2019-04-30