資料結構
網路
關係資料庫管理系統 (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 次瀏覽
