題目如下：

On a?N x N?grid of cells, each cell?(x, y)?with?0 <= x < N?and?0 <= y < N?has a lamp.

Initially, some number of lamps are on.??lamps[i]?tells us the location of the?i-th lamp that is on.? Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).

For the i-th query?queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.

After each query?(x, y)?[in the order given by?queries], we turn off any?lamps that are at cell?(x, y)?or are adjacent 8-directionally (ie., share a corner or edge with cell?(x, y).)

Return an array of answers.? Each?value?answer[i]should be equal to the answer of the?i-th query?queries[i].

?

Example 1:

Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]] Output: [1,0] Explanation: Before performing the first query we have both lamps [0,0] and [4,4] on. The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner: 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 1 1 1 Then the query at [1, 1] returns 1 because the cell is lit. After this query, the lamp at [0, 0] turns off, and the grid now looks like this: 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 0 1 1 1 1 1 1 1 Before performing the second query we have only the lamp [4,4] on. Now the query at [1,0] returns 0, because the cell is no longer lit.

?

Note:

1 <= N <= 10^9

0 <= lamps.length <= 20000

0 <= queries.length <= 20000

lamps[i].length == queries[i].length == 2

解題思路：每一盞燈可以照亮所在位置的水平方向、垂直方向和兩個(gè)對(duì)角線方向?，假設(shè)這盞燈的坐標(biāo)是(i,j)，那么用一次函數(shù)來表示這水平和垂直方向就是x=i,y=j。兩個(gè)對(duì)角線方向很顯然斜率分別是1和-1，把(i,j)分別帶入方程 y=x+b和y=-x+b即可求出b的值，而(斜率,b)這兩個(gè)參數(shù)即可確定一條直線。這里可以用三個(gè)字典分別保存這四個(gè)方程，例如dic_x[i] ，dic_y[j], dic[(-1,b)],dic[(1,b)]，每亮一盞燈，算出key值并對(duì)字典中相應(yīng)的key所對(duì)應(yīng)的值+1，而滅燈就是對(duì)key所對(duì)應(yīng)的值減去1。判斷一盞燈是否是亮的狀態(tài)，算出四個(gè)方向的key值并判斷這四個(gè)key中至少有一個(gè)存在于字典中即可。

代碼如下：

class Solution(object):dic = {}dic_x = {}dic_y = {}dic_lamp = {}def turn_on(self,x,y):b = y - xself.dic[(1, b)] = self.dic.setdefault((1, b), 0) + 1b = x + yself.dic[(-1, b)] = self.dic.setdefault((-1, b), 0) + 1self.dic_x[x] = self.dic_x.setdefault(x, 0) + 1self.dic_y[y] = self.dic_y.setdefault(y, 0) + 1def turn_off(self,x,y):b = y - xif (1,b) in self.dic:self.dic[(1, b)] -= 1self.dic[(1, b)] = max(0,self.dic[(1, b)])b = x + yif (-1,b) in self.dic:self.dic[(-1, b)] -= 1if self.dic[(-1, b)] == 0:del self.dic[(-1, b)]if x in self.dic_x:self.dic_x[x] -= 1if self.dic_x[x] == 0:del self.dic_x[x]if y in self.dic_y:self.dic_y[y] -= 1if self.dic_y[y] == 0:del self.dic_y[y]def is_on(self,x,y):return x in self.dic_x or y in self.dic_y or (1,y-x) in self.dic or (-1,y+x) in self.dicdef gridIllumination(self, N, lamps, queries):""":type N: int:type lamps: List[List[int]]:type queries: List[List[int]]:rtype: List[int]"""self.dic = {}self.dic_x = {}self.dic_y = {}self.dic_lamp = {}for (x,y) in lamps:self.turn_on(x,y)self.dic_lamp[(x,y)] = 1res = []direction = [(-1,0),(1,0),(0,1),(0,-1),(1,1),(1,-1),(-1,1),(-1,-1)]for (x,y) in queries:if self.is_on(x,y):res.append(1)if (x,y) in self.dic_lamp:self.turn_off(x, y)for (i,j) in direction:if (i+x,j+y) in self.dic_lamp:self.turn_off(i+x,j+y)else:res.append(0)if (x,y) in self.dic_lamp:self.turn_off(x, y)for (i, j) in direction:if (i + x, j + y) in self.dic_lamp:self.turn_off(i + x, j + y)return res

?

轉(zhuǎn)載于:https://www.cnblogs.com/seyjs/p/10474841.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎(jiǎng)勵(lì)來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎(jiǎng)

總結(jié)

以上是生活随笔為你收集整理的【leetcode】1001. Grid Illumination的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。