在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于关闭状态给你一个由灯的位置组成的二维数组 lamps

2025-01-14 09:12:24 阅读次数：12

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

大体步骤如下：

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)
}

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

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);
}

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

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;
}

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

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;
}

活动

智算服务

应用商城

合作伙伴

开发者

支持与服务

了解天翼云

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态 给你一个由灯的位置组成的二维数组 lamps

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于 关闭 状态 给你一个由灯的位置组成的二维数组 lamps

大体步骤如下：

go完整代码如下：

rust完整代码如下：

c++完整代码如下：

c完整代码如下：

相关文章

mysql只有在任务处于完成状态才能运行

复杂度的OJ练习

如何将一串数字用函数的方法倒过来（C语言）

jQuery遍历对象、数组、集合

多源BFS问题(4)_地图分析

递归,搜索,回溯算法(3)之穷举,暴搜,深搜,回溯,剪枝

MySQL 复合查询（重点）

多源BFS问题(2)_飞地的数量

计算机小白的成长历程——数组（1）

计算机小白的成长历程——习题演练（函数篇）

作者介绍

最新文章

jQuery遍历对象、数组、集合

typescript 将数组清空

java实现167. 两数之和 II - 输入有序数组

java 深搜

三角形最小路径和，64. 最小路径，63. 不同路径 II

移动零,11. 盛最多水的容器,15. 三数之和

热门文章

ArrayList动态数组对象 c# 1231

关于用户表根据userId分库后根据userName查询问题的思考

jdk1.8HashMap扩容后链表拆分过程解析

#yyds干货盘点# leetcode-dp-maxProduct

leetcode-dp-53. 最大子数组和

leetcode-53-dp

热门标签

相关产品

弹性云主机

天翼云电脑（公众版）

对象存储

云硬盘

随机文章

方案1 : {7, 10}； xxxx : {a , b}； 1 2 3 4； FunnyGoal = 100； OffenseGoal = 130。

对象数组快速掌拨 java

递归方式将数组变对象

指针六阶新悟生，泛用开篇趣纵横

给定一个二维数组，其中全是非负数， 每一步都可以往上、下、左、右四个方向运动。 返回从左上角走到右下角的最短距离。

#yyds干货盘点# leetcode-dp-53

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于关闭状态给你一个由灯的位置组成的二维数组 lamps

在大小为 n x n 的网格 grid 上，每个单元格都有一盏灯，最初灯都处于关闭状态给你一个由灯的位置组成的二维数组 lamps

给定一个二维数组，其中全是非负数，每一步都可以往上、下、左、右四个方向运动。返回从左上角走到右下角的最短距离。