跳到主要内容

1001.网格照明

· 阅读需 6 分钟

1、题干​

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态。

给你一个由灯的位置组成的二维数组 lamps ，其中 lamps[i] = [rowi, coli] 表示 打开 位于 grid[rowi][coli] 的灯。即便同一盏灯可能在 lamps 中多次列出，不会影响这盏灯处于 打开 状态。

当一盏灯处于打开状态，它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。

另给你一个二维数组 queries ，其中 queries[j] = [rowj, colj] 。对于第 j 个查询，如果单元格 [rowj, colj] 是被照亮的，则查询结果为 1 ，否则为 0 。在第 j 次查询之后 [按照查询的顺序] ，关闭 位于单元格 grid[rowj][colj] 上及相邻 8 个方向上（与单元格 grid[rowi][coli] 共享角或边）的任何灯。

返回一个整数数组 ans 作为答案， ans[j] 应等于第 j 次查询 queries[j] 的结果，1 表示照亮，0 表示未照亮。

 

示例 1：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
输出：[1,0]
解释：最初所有灯都是关闭的。在执行查询之前，打开位于 [0, 0] 和 [4, 4] 的灯。第 0 次查询检查 grid[1][1] 是否被照亮（蓝色方框）。该单元格被照亮，所以 ans[0] = 1 。然后，关闭红色方框中的所有灯。

第 1 次查询检查 grid[1][0] 是否被照亮（蓝色方框）。该单元格没有被照亮，所以 ans[1] = 0 。然后，关闭红色矩形中的所有灯。

示例 2：

输入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,1]]
输出：[1,1]

示例 3：

输入：n = 5, lamps = [[0,0],[0,4]], queries = [[0,4],[0,1],[1,4]]
输出：[1,1,0]

 

提示：

  • 1 <= n <= 109
  • 0 <= lamps.length <= 20000
  • 0 <= queries.length <= 20000
  • lamps[i].length == 2
  • 0 <= rowi, coli < n
  • queries[j].length == 2
  • 0 <= rowj, colj < n

今天题目挺简单的，感觉会写CRUD就能AC，只需要按照题目意思存储、查询以及修改亮灯状态就行

5b4f2239f899f748dd1fd07a8d78a201.gif


2、解题思路​

  • 由于网格行列的最大值是 10910^9，要遍历网格进行状态查改是不太可能了
  • 本题关键点是使用多个哈希表存储亮灯状态，另外要注意灯的状态实际有3种：关闭、打开、被照亮
    • 使用哈希集合存储打开的灯，记为 lightSet，其中键为行列号拼接成的字符串，形如 i-j
    • 使用哈希映射存储被照亮的行和列，分别记为 rowMap 和 colMap，其中键为行号或列号，值为亮灯数量
    • 使用哈希映射存储被照亮的两条对角线 y−x=dy-x=d 和 y+x=dy+x=d，分别记为 dglMap1 和 dglMap2，其中键为行列号的差或和，值为亮灯数量
  • 接着根据题意模拟即可
    • 将初始亮灯状态 lamps 存入各哈希表中
    • 遍历查询数组 queries ，查询亮灯状态并记录到结果数组 ans，查询时注意：只要行列或对角线上亮灯数量大于0，亮灯状态就是 1
    • 每次查询后关闭九宫格内的灯，关灯时注意：打开的灯才需要关闭，被照亮的灯无法关闭

3、代码​

var gridIllumination = function (n, lamps, queries) {
    // 亮灯哈希集合
    const lightSet = new Set();
    // 亮灯行、亮灯列
    const rowMap = new Map(), colMap = new Map();
    // 亮灯对角线1：y-x=d、亮灯对角线2：y+x=d
    const dglMap1 = new Map(), dglMap2 = new Map();
    
    // 将初始亮灯状态存入各哈希表中
    for (const [i, j] of lamps) {
        if (lightSet.has(`${i}-${j}`)) continue;
        lightSet.add(`${i}-${j}`);
        rowMap.set(i, (rowMap.get(i) || 0) + 1);
        colMap.set(j, (colMap.get(j) || 0) + 1);
        const d1 = j - i, d2 = j + i;
        dglMap1.set(d1, (dglMap1.get(d1) || 0) + 1);
        dglMap2.set(d2, (dglMap2.get(d2) || 0) + 1);
    }

    // 关灯函数：关闭九宫格内的灯
    function turnOff(fi, fj) {
        for (let di = -1; di < 2; di++) {
            for (let dj = -1; dj < 2; dj++) {
                const i = fi + di, j = fj + dj;
                if (!lightSet.has(`${i}-${j}`)) continue;
                lightSet.delete(`${i}-${j}`);
                rowMap.set(i, (rowMap.get(i) || 0) - 1);
                colMap.set(j, (colMap.get(j) || 0) - 1);
                const d1 = j - i, d2 = j + i;
                dglMap1.set(d1, (dglMap1.get(d1) || 0) - 1);
                dglMap2.set(d2, (dglMap2.get(d2) || 0) - 1);
            }
        }
    }

    // 遍历查询数组，计算亮灯状态后进行关灯操作
    const ans = queries.map(() => 0);
    for (let qi = 0; qi < queries.length; qi++) {
        const [i, j] = queries[qi];
        const d1 = j - i, d2 = j + i;
        if (lightSet.has(`${i}-${j}`) || rowMap.get(i) || colMap.get(j) || dglMap1.get(d1) || dglMap2.get(d2)) ans[qi] = 1;
        turnOff(i, j);
    }

    return ans;
};

4、复杂度​

  • 时间复杂度：O(n)O(n)
  • 空间复杂度：O(n)O(n)

5、执行结果​

image.png