列表

详情

1001. 网格照明

在大小为 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]

 

提示：

相似题目

N 皇后

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) { } };

golang 解法, 执行用时: 160 ms, 内存消耗: 18.3 MB, 提交时间: 2023-05-14 19:46:09 

func gridIllumination(n int, lamps [][]int, queries [][]int) []int {
    rowCnts, colCnts, lrCnts, rlCnts, points := map[int]int{}, map[int]int{}, map[int]int{}, map[int]int{}, map[int]bool{}
    for _, lamp := range lamps {
        x, y := lamp[0], lamp[1]
        p := x * n + y
        if(!points[p]) {
            points[p] = true
            rowCnts[x] += 1
            colCnts[y] += 1
            lrCnts[x + y] += 1
            rlCnts[x - y] += 1
        }
    }

    ans := make([]int, len(queries))
    for i := 0; i < len(queries); i++ {
        x, y := queries[i][0], queries[i][1]
        if(rowCnts[x] > 0 || colCnts[y] > 0 || lrCnts[x + y] > 0 || rlCnts[x - y] > 0) {
            ans[i] = 1
            for _, dir := range [][]int{{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}} {
                nx, ny := x + dir[0], y + dir[1]
                if nx >= 0 && ny >= 0 && nx < n && ny < n {
                    p := nx * n + ny
                    if(points[p]) {
                        points[p] = false
                        rowCnts[nx] -= 1
                        colCnts[ny] -= 1
                        lrCnts[nx + ny] -= 1
                        rlCnts[nx - ny] -= 1
                    }
                }
            }
        }
    }
    return ans
}

javascript 解法, 执行用时: 228 ms, 内存消耗: 83.4 MB, 提交时间: 2023-05-14 19:45:55 

/**
 * @param {number} n
 * @param {number[][]} lamps
 * @param {number[][]} queries
 * @return {number[]}
 */
const DIRS = [[0, 0], [0, 1], [1, 0], [0, -1], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]
var gridIllumination = function(n, lamps, queries) {
    const rowCnts = new Map(), colCnts = new Map(), lrCnts = new Map(), rlCnts = new Map(), points = new Set()

    update = function(map, key, val) {
        if(map.has(key)){
            let v = map.get(key)
            v += val
            if(v == 0)
                map.delete(key)
            else
                map.set(key, v)
        } else {
            map.set(key, val)
        }
    }

    operate = function(x, y, diff) {
        update(rowCnts, x, diff)
        update(colCnts, y, diff)
        update(lrCnts, x + y, diff)
        update(rlCnts, x - y, diff)
    }

    for(const lamp of lamps) {
        const x = lamp[0], y = lamp[1]
        const p = BigInt(x * n + y)
        if(!points.has(p)) {
            points.add(p)
            operate(x, y, 1)
        }
    }

    const ans = new Array(queries.length).fill(0)
    for(let i = 0; i < queries.length; i++) {
        const x = queries[i][0], y = queries[i][1]
        if(rowCnts.has(x) || colCnts.has(y) || lrCnts.has(x + y) || rlCnts.has(x - y)) {
            ans[i] = 1
            for(const dir of DIRS) {
                const nx = x + dir[0], ny = y + dir[1]
                if(nx >= 0 && ny >= 0 && nx < n && ny < n) {
                    const p = BigInt(nx * n + ny)
                    if(points.has(p)) {
                        points.delete(p)
                        operate(nx, ny, -1)
                    }
                }
            }
        }        
    }
    return ans
};

java 解法, 执行用时: 53 ms, 内存消耗: 57.8 MB, 提交时间: 2023-05-14 19:45:40 

class Solution {
    private static final int[][] DIRS = new int[][]{{0, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
    private Map<Integer, Integer> rowCnts, colCnts, lrCnts, rlCnts;
    public int[] gridIllumination(int n, int[][] lamps, int[][] queries) {
        long ln = (long)n;
        rowCnts = new HashMap<>();
        colCnts = new HashMap<>();
        lrCnts = new HashMap<>();
        rlCnts = new HashMap<>();
        Set<Long> points = new HashSet<>();
        for(int[] lamp: lamps) {
            int x = lamp[0], y = lamp[1];
            long p = ln * x + y;
            if(!points.contains(p)) {
                points.add(p);
                operate(x, y, 1);
            }
        }
        int[] ans = new int[queries.length];
        for(int i = 0; i < queries.length; i++) {
            int x = queries[i][0], y = queries[i][1];
            if(rowCnts.getOrDefault(x, 0) > 0 || colCnts.getOrDefault(y, 0) > 0 || lrCnts.getOrDefault(x + y, 0) > 0 || rlCnts.getOrDefault(x - y, 0) > 0){
                ans[i] = 1;
                for(int[] dir: DIRS){
                    int nx = x + dir[0], ny = y + dir[1];
                    if(nx >= 0 && ny >= 0 && nx < n && ny < n){
                        long p = ln * nx + ny;
                        if(points.contains(p)){
                            points.remove(p);
                            operate(nx, ny, -1);
                        }
                    }
                }
            }
        }
        return ans;
    }

    private void operate(Integer x, Integer y, int diff) {
        add(rowCnts, x, diff);
        add(colCnts, y, diff);
        add(lrCnts, x + y, diff);
        add(rlCnts, x - y, diff);
    }

    private void add(Map<Integer,Integer> map, Integer key, int val) {
        int cur = map.getOrDefault(key, 0);
        map.put(key, cur + val);
    }
}

python3 解法, 执行用时: 184 ms, 内存消耗: 37.3 MB, 提交时间: 2023-05-14 19:45:27 

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        row_cnts, col_cnts, lr_cnts, rl_cnts, points = defaultdict(int), defaultdict(int), defaultdict(int), defaultdict(int), set()
        for r, c in lamps:
            if (r, c) not in points:
                points.add((r, c))
                row_cnts[r] += 1
                col_cnts[c] += 1
                # r * (-1) + b = c
                lr_cnts[r + c] += 1
                # r + b = c
                rl_cnts[r - c] += 1
        ans = [0] * len(queries)
        for i in range(len(queries)):
            r, c = queries[i]
            if row_cnts[r] or col_cnts[c] or lr_cnts[r + c] or rl_cnts[r - c]:
                ans[i] = 1
                for dx, dy in (0, 1), (1, 0), (0, -1), (-1, 0), (0, 0), (1, 1), (-1, 1), (1, -1), (-1, -1):
                    if ((nx := r + dx),(ny := c + dy)) in points:
                        points.remove((nx, ny))
                        row_cnts[nx] -= 1
                        col_cnts[ny] -= 1
                        lr_cnts[nx + ny] -= 1
                        rl_cnts[nx - ny] -= 1
        return ans

golang 解法, 执行用时: 248 ms, 内存消耗: 15.1 MB, 提交时间: 2023-05-14 19:45:09 

func gridIllumination(n int, lamps, queries [][]int) []int {
    type pair struct{ x, y int }
    points := map[pair]bool{}
    row := map[int]int{}
    col := map[int]int{}
    diagonal := map[int]int{}
    antiDiagonal := map[int]int{}
    for _, lamp := range lamps {
        r, c := lamp[0], lamp[1]
        p := pair{r, c}
        if points[p] {
            continue
        }
        points[p] = true
        row[r]++
        col[c]++
        diagonal[r-c]++
        antiDiagonal[r+c]++
    }

    ans := make([]int, len(queries))
    for i, query := range queries {
        r, c := query[0], query[1]
        if row[r] > 0 || col[c] > 0 || diagonal[r-c] > 0 || antiDiagonal[r+c] > 0 {
            ans[i] = 1
        }
        for x := r - 1; x <= r+1; x++ {
            for y := c - 1; y <= c+1; y++ {
                if x < 0 || y < 0 || x >= n || y >= n || !points[pair{x, y}] {
                    continue
                }
                delete(points, pair{x, y})
                row[x]--
                col[y]--
                diagonal[x-y]--
                antiDiagonal[x+y]--
            }
        }
    }
    return ans
}

python3 解法, 执行用时: 320 ms, 内存消耗: 33.1 MB, 提交时间: 2023-05-14 19:44:50 

class Solution:
    def gridIllumination(self, n: int, lamps: List[List[int]], queries: List[List[int]]) -> List[int]:
        points = set()
        row, col, diagonal, antiDiagonal = Counter(), Counter(), Counter(), Counter()
        for r, c in lamps:
            if (r, c) in points:
                continue
            points.add((r, c))
            row[r] += 1
            col[c] += 1
            diagonal[r - c] += 1
            antiDiagonal[r + c] += 1

        ans = [0] * len(queries)
        for i, (r, c) in enumerate(queries):
            if row[r] or col[c] or diagonal[r - c] or antiDiagonal[r + c]:
                ans[i] = 1
            for x in range(r - 1, r + 2):
                for y in range(c - 1, c + 2):
                    if x < 0 or y < 0 or x >= n or y >= n or (x, y) not in points:
                        continue
                    points.remove((x, y))
                    row[x] -= 1
                    col[y] -= 1
                    diagonal[x - y] -= 1
                    antiDiagonal[x + y] -= 1
        return ans

上一题

© 2024 leetcode.cn