Skip to content

Latest commit

 

History

History
141 lines (80 loc) · 3.87 KB

1001._Grid_Illumination.md

File metadata and controls

141 lines (80 loc) · 3.87 KB

1001. Grid Illumination

难度: Hard

刷题内容

原题连接

内容描述

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

解题方案

思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******

对于一个格子,只要它的横坐标上一条线,纵坐标上一条线,主对角线上一条线,副对角线上一条线,这4条线上任意一条线有一个lamp, 或者它自身就是lamp, 这个格子都是illuminated的

所以我们可以记录下来每一个横坐标上一条线,纵坐标上一条线,主对角线上一条线,副对角线上一条线各有多少个lamp

然后对于每一个query来说,根据前面的分析我们可以很轻易的知道这个cell是否是illuminated的, 然后我们要把包含这个cell自身的九宫格里面的 lamp 全都 turn off, 即对应横坐标上一条线,纵坐标上一条线,主对角线上一条线,副对角线上一条线的lamp数量减去1

注意:

  1. 主对角线可以用 i-j 来唯一表示,即代码里面的d1[l[0]-l[1]]
  2. 副对角线可以用 i+j 来唯一表示,即代码里面的d1[l[0]+l[1]]
from collections import defaultdict

class Solution:
    def gridIllumination(self, N, lamps, queries):
        # x, y, d1, d2 分别代表横坐标上一条线,纵坐标上一条线,主对角线上一条线,副对角线上一条线
        x, y, d1, d2 = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int)
        ll = set()
        for l in lamps:
            ll.add((l[0], l[1]))
            x[l[0]] += 1
            y[l[1]] += 1
            d1[l[0]-l[1]] += 1
            d2[l[0]+l[1]] += 1
            
        nxts = [[0,1],[0,-1],[1,0],[-1,0],[-1,-1],[-1,1],[1,-1],[1,1],[0,0]]
        res = []
        for q in queries:
            if x[q[0]] or y[q[1]] or d1[q[0]-q[1]] or d2[q[0] + q[1]]:
                res.append(1)
            else:
                res.append(0)
            # 把包含自身的九宫格里面的 lamp 全都 turn off
            for xx, yy in nxts:
                if 0 <= xx < N and 0 <= yy < N:
                    if (xx, yy) in ll:
                        x[xx] -= 1
                        y[yy] -= 1
                        d1[xx-yy] -= 1
                        d2[xx+yy] -= 1
                        ll.remove((xx,yy))
        return res