2023-06-26：在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于关闭状态给你一个由灯的位置组成的二维数组 lamps 其中 lamps[i] = [rowi,

作者：福大大架构师每日一题

2023-06-26
北京
本文字数：5259 字
阅读完需：约 17 分钟

2023-06-26：在大小为 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 表示未照亮。

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

输出：[1,0]。

答案 2023-06-26：

大体步骤如下：

1.首先，定义一个存储灯位置的二维数组 lamps，和查询位置的二维数组 queries。

2.创建四个 map，用于记录每行、每列、左上到右下对角线和右上到左下对角线上的灯的数量。还有一个 points map，用于存储所有点的状态。

3.遍历灯的位置，将灯的状态记录到相关的 map 中，并将点的状态记录到 points map 中。

4.创建一个结果数组 ans，用于存储每个查询的结果。

5.对于每一个查询位置，初始化结果为 0。

6.如果查询位置所在的行、列、左上到右下对角线或者右上到左下对角线上有灯，将结果设为 1。

7.遍历查询位置周围的 8 个方向，如果有灯，则关闭该灯，并在相关的 map 中减去相应的数量。

8.返回结果数组 ans。

时间复杂度分析:

遍历灯的位置并初始化 maps 需要 O(lamps)，其中 lamps 是灯的数量。
对于每个查询位置，遍历周围的 8 个方向，检查是否有灯需要 O(1) 的时间。
因此，总的时间复杂度为 O(lamps + queries)。

空间复杂度分析:

maps 和 points 的空间复杂度均为 O(lamps)，其中 lamps 是灯的数量。
结果数组 ans 的空间复杂度为 O(queries)，其中 queries 是查询的数量。
因此，总的空间复杂度为 O(lamps + queries)。

go 完整代码如下：

package main
import "fmt"
var move = [][]int{  {0, 0},  {0, -1},  {0, 1},  {-1, 0},  {-1, -1},  {-1, 1},  {1, 0},  {1, -1},  {1, 1},}
func gridIllumination(n int, lamps [][]int, queries [][]int) []int {  limit := int64(n)  row := make(map[int]int)  col := make(map[int]int)  leftUpDiag := make(map[int]int)  rightUpDiag := make(map[int]int)  points := make(map[int64]bool)
  for _, p := range lamps {    if points[limit*int64(p[0])+int64(p[1])] == false {      points[limit*int64(p[0])+int64(p[1])] = true      row[p[0]]++      col[p[1]]++      leftUpDiag[p[0]-p[1]]++      rightUpDiag[p[0]+p[1]]++    }  }
  ans := make([]int, len(queries))  for i, q := range queries {    ans[i] = 0    if row[q[0]] != 0 || col[q[1]] != 0 || leftUpDiag[q[0]-q[1]] != 0 || rightUpDiag[q[0]+q[1]] != 0 {      ans[i] = 1    }    for _, m := range move {      r := q[0] + m[0]      c := q[1] + m[1]      lu := r - c      ru := r + c      if r < 0 || r >= n || c < 0 || c >= n {        continue      }      if points[limit*int64(r)+int64(c)] {        points[limit*int64(r)+int64(c)] = false        minusOrRemove(row, r)        minusOrRemove(col, c)        minusOrRemove(leftUpDiag, lu)        minusOrRemove(rightUpDiag, ru)      }    }  }
  return ans}
func minusOrRemove(m map[int]int, key int) {  if m[key] == 1 {    delete(m, key)  } else {    m[key]--  }}
func main() {  n := 5  lamps := [][]int{{0, 0}, {4, 4}}  queries := [][]int{{1, 1}, {1, 0}}  result := gridIllumination(n, lamps, queries)  fmt.Println(result)}

复制代码

rust 完整代码如下：

use std::collections::{HashMap, HashSet};
fn grid_illumination(n: i32, lamps: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {    let limit = n;    let mut row = HashMap::new();    let mut col = HashMap::new();    let mut left_up_diag = HashMap::new();    let mut right_up_diag = HashMap::new();    let mut points = HashSet::new();
    for p in lamps {        if points.insert(limit * p[0] + p[1]) {            *row.entry(p[0]).or_insert(0) += 1;            *col.entry(p[1]).or_insert(0) += 1;            *left_up_diag.entry(p[0] - p[1]).or_insert(0) += 1;            *right_up_diag.entry(p[0] + p[1]).or_insert(0) += 1;        }    }
    let mut ans = Vec::with_capacity(queries.len());
    for q in queries {        let mut illumination = 0;
        if row.contains_key(&q[0])            || col.contains_key(&q[1])            || left_up_diag.contains_key(&(q[0] - q[1]))            || right_up_diag.contains_key(&(q[0] + q[1]))        {            illumination = 1;        }
        for m in vec![            vec![0, 0],            vec![0, -1],            vec![0, 1],            vec![-1, 0],            vec![-1, -1],            vec![-1, 1],            vec![1, 0],            vec![1, -1],            vec![1, 1],        ] {            let r = q[0] + m[0];            let c = q[1] + m[1];            let lu = r - c;            let ru = r + c;
            if r < 0 || r >= n || c < 0 || c >= n {                continue;            }
            if points.contains(&(limit * r + c)) {                points.remove(&(limit * r + c));                minus_or_remove(&mut row, r);                minus_or_remove(&mut col, c);                minus_or_remove(&mut left_up_diag, lu);                minus_or_remove(&mut right_up_diag, ru);            }        }
        ans.push(illumination);    }
    ans}
fn minus_or_remove(map: &mut HashMap<i32, i32>, key: i32) {    if let Some(count) = map.get_mut(&key) {        if *count == 1 {            map.remove(&key);        } else {            *count -= 1;        }    }}
fn main() {    let n = 5;    let lamps = vec![vec![0, 0], vec![4, 4]];    let queries = vec![vec![1, 1], vec![1, 0]];
    let result = grid_illumination(n, lamps, queries);    println!("{:?}", result);}

复制代码

c++完整代码如下：

#include <iostream>#include <vector>#include <unordered_map>#include <unordered_set>
using namespace std;
vector<vector<int>> move222 = {    {0, 0},    {0, -1},    {0, 1},    {-1, 0},    {-1, -1},    {-1, 1},    {1, 0},    {1, -1},    {1, 1}};
void minusOrRemove(unordered_map<int, int>& map, int key) {    if (map[key] == 1)        map.erase(key);    else        map[key]--;}
vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {    long limit = n;    unordered_map<int, int> row, col, leftUpDiag, rightUpDiag;    unordered_set<long long> points;    for (vector<int>& p : lamps) {        if (points.insert(limit * p[0] + p[1]).second) {            row[p[0]]++;            col[p[1]]++;            leftUpDiag[p[0] - p[1]]++;            rightUpDiag[p[0] + p[1]]++;        }    }    vector<int> ans(queries.size());    int ansi = 0;    for (vector<int>& q : queries) {        ans[ansi++] = (row.count(q[0]) || col.count(q[1]) || leftUpDiag.count(q[0] - q[1]) || rightUpDiag.count(q[0] + q[1])) ? 1 : 0;        for (vector<int>& m : move222) {            int r = q[0] + m[0];            int c = q[1] + m[1];            int lu = r - c;            int ru = r + c;            if (r < 0 || r >= n || c < 0 || c >= n)                continue;            if (points.count(limit * r + c)) {                points.erase(limit * r + c);                minusOrRemove(row, r);                minusOrRemove(col, c);                minusOrRemove(leftUpDiag, lu);                minusOrRemove(rightUpDiag, ru);            }        }    }    return ans;}
int main() {    int n = 5;    vector<vector<int>> lamps = { {0, 0}, {4, 4} };    vector<vector<int>> queries = { {1, 1}, {1, 0} };
    vector<int> result = gridIllumination(n, lamps, queries);
    for (const int& res : result) {        cout << res << " ";    }    cout << endl;
    return 0;}

复制代码

c 完整代码如下：

#include <stdio.h>#include <stdlib.h>
typedef struct {    int x;    int y;} Lamp;
int move[9][2] = {    {0, 0},    {0, -1},    {0, 1},    {-1, 0},    {-1, -1},    {-1, 1},    {1, 0},    {1, -1},    {1, 1}};
void minusOrRemove(int* map, int key) {    if (map[key] == 1) {        map[key] = 0;    }    else {        map[key]--;    }}
int* gridIllumination(int n, Lamp* lamps, int lampsSize, int* lampsColSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {    long limit = n;    int* row = (int*)calloc(n, sizeof(int));    int* col = (int*)calloc(n, sizeof(int));    int* leftUpDiag = (int*)calloc(2 * n - 1, sizeof(int));    int* rightUpDiag = (int*)calloc(2 * n - 1, sizeof(int));    int* points = (int*)calloc(n * n, sizeof(int));
    for (int i = 0; i < lampsSize; i++) {        int x = lamps[i].x;        int y = lamps[i].y;        if (points[limit * x + y] == 0) {            points[limit * x + y] = 1;            row[x]++;            col[y]++;            leftUpDiag[x - y + n - 1]++;            rightUpDiag[x + y]++;        }    }
    int* ans = (int*)calloc(queriesSize, sizeof(int));
    for (int i = 0; i < queriesSize; i++) {        int x = queries[i][0];        int y = queries[i][1];
        ans[i] = (row[x] || col[y] || leftUpDiag[x - y + n - 1] || rightUpDiag[x + y]) ? 1 : 0;
        for (int j = 0; j < 9; j++) {            int r = x + move[j][0];            int c = y + move[j][1];            int lu = r - c + n - 1;            int ru = r + c;
            if (r < 0 || r >= n || c < 0 || c >= n) {                continue;            }
            if (points[limit * r + c] == 1) {                points[limit * r + c] = 0;                minusOrRemove(row, r);                minusOrRemove(col, c);                minusOrRemove(leftUpDiag, lu);                minusOrRemove(rightUpDiag, ru);            }        }    }
    free(row);    free(col);    free(leftUpDiag);    free(rightUpDiag);    free(points);
    *returnSize = queriesSize;    return ans;}
int main() {    int n = 5;    int lampsSize = 2;    int lampsColSize[2] = { 2, 2 };    Lamp lamps[2] = { {0, 0}, {4, 4} };
    int queriesSize = 2;    int queriesColSize[2] = { 2, 2 };    int** queries = (int**)malloc(queriesSize * sizeof(int*));    for (int i = 0; i < queriesSize; i++) {        queries[i] = (int*)malloc(2 * sizeof(int));    }    queries[0][0] = 1;    queries[0][1] = 1;    queries[1][0] = 1;    queries[1][1] = 0;
    int returnSize;    int* result = gridIllumination(n, lamps, lampsSize, lampsColSize, queries, queriesSize, queriesColSize, &returnSize);
    for (int i = 0; i < returnSize; i++) {        printf("%d ", result[i]);    }    printf("\n");
    for (int i = 0; i < queriesSize; i++) {        free(queries[i]);    }    free(queries);    free(result);
    return 0;}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/b39fb9a2c3475decb02c7e567】。

福大大架构师每日一题

关注

公众号：福大大架构师每日一题 2021-02-15 加入

公众号：福大大架构师每日一题

发布

暂无评论

创作场景

2023-06-26：在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态 给你一个由灯的位置组成的二维数组 lamps 其中 lamps[i] = [rowi,

大体步骤如下：

go 完整代码如下：

rust 完整代码如下：

c++完整代码如下：

c 完整代码如下：

福大大架构师每日一题

评论

2023-06-26：在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于关闭状态给你一个由灯的位置组成的二维数组 lamps 其中 lamps[i] = [rowi,