-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
1001.py
111 lines (108 loc) · 3.72 KB
/
1001.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
__________________________________________________________________________________________________
sample 916 ms submission
class Solution:
def gridIllumination(self, N: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
s = set()
lx = {}
ly = {}
lp = {}
lq = {}
for lamp in lamps:
x = lamp[0]
y = lamp[1]
s.add((x,y))
if x in lx:
lx[x]+=1
else:
lx[x]=1
if y in ly:
ly[y]+=1
else:
ly[y]=1
if x+y in lp:
lp[x+y]+=1
else:
lp[x+y]=1
if x-y in lq:
lq[x-y]+=1
else:
lq[x-y]=1
ans = []
for query in queries:
x = query[0]
y = query[1]
if x in lx or y in ly or x + y in lp or x - y in lq:
ans.append(1)
for tx in range(x-1,x+2):
for ty in range(y-1, y+2):
if tx<0 or tx>=N or ty<0 or ty>=N:
continue
if (tx,ty) in s:
s.remove((tx,ty))
lx[tx]-=1
if lx[tx] == 0:
lx.pop(tx)
ly[ty]-=1
if ly[ty] == 0:
ly.pop(ty)
lp[tx+ty]-=1
if lp[tx+ty] ==0:
lp.pop(tx+ty)
lq[tx-ty]-=1
if lq[tx-ty] == 0:
lq.pop(tx-ty)
else:
ans.append(0)
return ans
__________________________________________________________________________________________________
sample 27208 kb submission
from collections import defaultdict
class Solution:
@staticmethod
def get_neighbors(x: int,y: int, N: int):
res = [(x, y)]
if x-1 >= 0:
res.append((x-1, y))
if y-1 >= 0:
res.append((x, y-1))
if x+1 < N:
res.append((x+1, y))
if y+1 < N:
res.append((x, y+1))
if x-1 >= 0 and y-1 >= 0:
res.append((x-1, y-1))
if x-1 >= 0 and y+1 < N:
res.append((x-1, y+1))
if x+1 < N and y-1 >= 0:
res.append((x+1, y-1))
if x+1 < N and y+1 < N:
res.append((x+1, y+1))
return res
def gridIllumination(self, N: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
row, col = defaultdict(int), defaultdict(int)
diag1, diag2 = defaultdict(int), defaultdict(int)
lamp_cell = set()
for lamp in lamps:
x, y = lamp
row[x] += 1
col[y] += 1
diag1[x + y] += 1
diag2[x - y] += 1
lamp_cell.add((x, y))
res = []
for q in queries:
x, y = q
if (x in row and row[x] > 0) or (y in col and col[y] > 0) or (x+y in diag1 and diag1[x+y] > 0) or (x-y in diag2 and diag2[x-y] > 0):
res.append(1)
else:
res.append(0)
cells = self.get_neighbors(x, y, N)
for cell in cells:
if cell in lamp_cell:
lamp_cell.remove(cell)
row[cell[0]] -= 1
col[cell[1]] -= 1
diag1[cell[0] + cell[1]] -= 1
diag2[cell[0] - cell[1]] -= 1
return res
__________________________________________________________________________________________________