1001. 网格照明_2022_02_08
2022/2/8 23:18:22
本文主要是介绍1001. 网格照明_2022_02_08,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
1001. 网格照明
在大小为 n x n
的网格 grid
上,每个单元格都有一盏灯,最初灯都处于 关闭 状态。
给你一个由灯的位置组成的二维数组 lamps
,其中 lamps[i] = [row<sub style="display: inline;">i</sub>, col<sub style="display: inline;">i</sub>]
表示 打开 位于 grid[row<sub style="display: inline;">i</sub>][col<sub style="display: inline;">i</sub>]
的灯。即便同一盏灯可能在 lamps
中多次列出,不会影响这盏灯处于 打开 状态。
当一盏灯处于打开状态,它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。
另给你一个二维数组 queries
,其中 queries[j] = [row<sub style="display: inline;">j</sub>, col<sub style="display: inline;">j</sub>]
。对于第 j
个查询,如果单元格 [row<sub style="display: inline;">j</sub>, col<sub style="display: inline;">j</sub>]
是被照亮的,则查询结果为 1
,否则为 0
。在第 j
次查询之后 [按照查询的顺序] ,关闭 位于单元格 grid[row<sub style="display: inline;">j</sub>][col<sub style="display: inline;">j</sub>]
上及相邻 8 个方向上(与单元格 grid[row<sub style="display: inline;">i</sub>][col<sub style="display: inline;">i</sub>]
共享角或边)的任何灯。
返回一个整数数组 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 <= 10<sup>9</sup>
0 <= lamps.length <= 20000
0 <= queries.length <= 20000
lamps[i].length == 2
0 <= row<sub style="display: inline;">i</sub>, col<sub style="display: inline;">i</sub> < n
queries[j].length == 2
0 <= row<sub style="display: inline;">j</sub>, col<sub style="display: inline;">j</sub> < n
Solution
理解就是,给定的lamps表示一个灯的序列,该序列中的每个灯所在行和列以及对角线上的灯是亮的,表示这个灯是
打开
的,并且序列之间的灯导致亮是叠加的,互不干涉,现在需要遍历queries中的位置,每遍历一个灯,就需要把这个位置的灯紧邻的灯都设置为关闭
// 官方题解,golang练手 func gridIllumination(n int, lamps [][]int, 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 }
这篇关于1001. 网格照明_2022_02_08的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?