数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python中的网格照明
假设我们有一个 N x N 的单元格网格，每个单元格 (x, y) 都有一盏灯。最初，一些灯是亮的。lamps[i] 是第 i 盏亮着的灯的位置。每盏亮着的灯都会照亮其 x 轴、y 轴和两个对角线上的每个方格。现在对于第 i 个查询，即 queries[i] = (x, y)，如果单元格 (x, y) 被照亮，则查询的答案为 1，否则为 0。在每个查询 (x, y) 之后，我们将关闭位于单元格 (x, y) 或在其 8 个方向上相邻的任何灯。返回答案数组。每个值 answer[i] 应该等于第 i 个查询 queries[i] 的答案。
因此，如果输入类似于 N = 5，lamps 为 [[0,0],[4,4]]，query 为 [[1,1],[1,0]]，则输出将为 [1,0]
为了解决这个问题，我们将遵循以下步骤：
lamps := 从给定数组 lamps 中获取的成对集合
创建映射 x、y、diag1、diag2
对于 lamps 中的每个对 (i, j)
x[i] := x[i] + 1, y[j] := y[j] + 1
diag1[i + j] := diag1[i + j] + 1, diag2[i - j] = diag2[i - j] + 1
ans := []
对于 C 中的每个值 i
a := i[0], b := i[1]
将 (如果 x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 则为 1，否则为 0) 插入 ans
对于行范围从 a - 1 到 a + 1
对于列范围从 b - 1 到 b + 1
如果行、列对在 lamps 中，则：
x[row] := x[row] - 1
y[col] := y[col] - 1
diag1[row + col] = diag1[row + col] - 1
diag2[row - col] = diag2[row - col] - 1
从 lamps 中移除 (row, col)
返回 ans
让我们看看下面的实现，以便更好地理解：
示例
from collections import defaultdict
class Solution(object):
def gridIllumination(self, N, b, C):
lamps = {(i[0], i[1]) for i in b}
x, y, diag1, diag2 = defaultdict(int), defaultdict(int),
defaultdict(int), defaultdict(int)
for i, j in lamps:
x[i] += 1
y[j] += 1
diag1[i + j] += 1
diag2[i - j] += 1
ans = []
for i in C:
a = i[0]
b = i[1]
ans.append(1 if x[a] + y[b] + diag1[a + b] + diag2[a - b] > 0 else 0)
for row in range( a - 1, a + 2):
for col in range(b - 1, b + 2):
if (row, col) in lamps:
x[row] -= 1
y[col] -= 1
diag1[row + col] -= 1
diag2[row - col] -= 1
lamps.remove((row, col))
return ans
ob = Solution()
N = 5
lamps = [[0,0],[4,4]]
query = [[1,1],[1,0]]
print(ob.gridIllumination(N, lamps, query))输入
5, [[0,0],[4,4]], [[1,1],[1,0]]
输出
[1, 0]
367 次浏览
