“This is the 13th day of my participation in the First Challenge 2022. For details: First Challenge 2022”
preface
Today’s topic is difficult, but understand the meaning of the topic, this question is medium at best. Maybe because the difficult questions are not submitted by many people, so today’s submission of double beat 100%.
A daily topic
On a grid of size N x N, each cell has a light that is initially turned off.
Give you a 2D array lamps composed of lamp positions where lamps[I] = [rowi, coli] indicate turning on the lamp at grid[Rowi][coli]. Even though the same lamp may be listed multiple times in lamps, it will not affect the lamp being on.
When a light is on, it illuminates its own cell and all other cells on the same row, column, and two diagonals.
Queries [j] = [rowj, colj] For the JTH query, the result is 1 if the cell [Rowj, COLj] is illuminated, and 0 otherwise. After the JTH query [in the order of the query], turn off any lights on the cell grid[Rowj][COLj] and in 8 adjacent directions that share angles or edges with the cell grid[Rowi][coli].
Return an integer array ans as the answer, ans[j] should be equal to the result of the JTH query queries[j], 1 means illuminated, 0 means unilluminated.
Example 1:
Enter n =5, lamps = [[0.0], [4.4]], queries = [[1.1], [1.0] output: [1.0]
Copy the codeExplanation: Initially all lights were turned off. Before performing the query, turn on the lights at [0, 0] and [4, 4]. The 0th query checks whether the grid[1][1] is illuminated (blue box). The cell is illuminated, so ans[0] = 1. Then, turn off all the lights in the red box. 
Enter n =5, lamps = [[0.0], [4.4]], queries = [[1.1], [1.1] output: [1.1]
Copy the codeExample 3:
Enter n =5, lamps = [[0.0], [0.4]], queries = [[0.4], [0.1], [1.4] output: [1.1.0]
Copy the codeTip:
- 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
Answer key
Hash table
First of all, they’re going to give you an n by N matrix, and then they’re going to give you an array that holds the positions of the lights in that matrix,
-
The first problem is that we have the position of the lamp, how to preserve the position of the light emitted by the lamp. We can use horizontal, vertical, diagonal, and anti-diagonal hash tables to store lights, so let’s say we have a light at (1,1), then we can store (1,1) in the horizontal Y hash table, which means that the light is on at y = 1, and so on, We can also use the x hash table to store the vertical x coordinate, and we can use the diagonal hash table to store the diagonal coordinate, and the diagonal key, because of the properties of the diagonal equation, we can store it in x minus y, and the opposite diagonal, x plus y.
-
Saved after the lights of the four directions, we also need to save the lamp position, has mentioned in the title, a lamp may appear many times, but will be open, so we used a set under the table to hold the position of the light, the position of the lamp with the coordinates (x, y) format to store, we can create a coordinate function, Used to pass in x,y, and then return the concatenated x,y:
const coordinate = (x, y) = > {
return x + ', ' + y;
};
Copy the code-
We have successfully saved the lights and lights. Then we need to pass in the second array queries to determine whether the current location is lit and turn off the lights around it.
-
The length of the array is the same as that of the queries, and 0 or 1 on each position represents whether there is light at the current position. So, we can create a new array ans with the same length as queries, and first assign 0 to all queries, then go through our queries array, when there is a light on the front, change the ans position to 1, and then turn off the lights around the 9 cells.
-
First we need to iterate over the surrounding squares of the queries passed in. Set the abscissa of the queries passed in to queriesX and the ordinate to queriesY. Then we can iterate through the surrounding squares through a double loop:
for (let x = queriesX - 1; x < queriesX + 2; x++) {
for (let y = queriesY - 1; y < queriesY + 2; y++) { ... }}Copy the code- In the process of traversal, we can judge whether the current position exceeds the n*n matrix, and then judge whether there is a lamp in the current position.
if (x < 0 || y < 0|| x >= n || y >= n || ! points.has(coordinate(x, y))) {continue;
}
Copy the code- The current position does not exceed the matrix and there is a lamp, then delete the lamp from the lamp table and reduce the number of lights in each of the four directions by one:
points.delete(coordinate(x, y));
row.set(x, row.get(x) - 1);
col.set(y, col.get(y) - 1);
diagonal.set(x - y, diagonal.get(x - y) - 1);
antiDiagonal.set(x + y, antiDiagonal.get(x + y) - 1);
Copy the code- The final return of the ans array is the answer to the problem.
/ * * *@param {number} n
* @param {number[][]} lamps
* @param {number[][]} queries
* @return {number[]}* /
var gridIllumination = function(n, lamps, queries) {
const row = new Map(a);const column = new Map(a);const diagonal = new Map(a);const antiDiagonal = new Map(a);const lights = new Set(a);for (const lamp of lamps) {
if (lights.has(coordinate(lamp[0], lamp[1))) {continue;
}
lights.add(coordinate(lamp[0], lamp[1]));
row.set(lamp[0], (row.get(lamp[0) | |0) + 1);
column.set(lamp[1], (column.get(lamp[1) | |0) + 1);
diagonal.set(lamp[0] - lamp[1], (diagonal.get(lamp[0] - lamp[1) | |0) + 1);
antiDiagonal.set(lamp[0] + lamp[1], (antiDiagonal.get(lamp[0] + lamp[1) | |0) + 1);
}
const ans = new Array(queries.length).fill(0);
for (const [i, [queriesX, queriesY]] of queries.entries()) {
if (row.get(queriesX) || column.get(queriesY) || diagonal.get(queriesX - queriesY) || antiDiagonal.get(queriesX + queriesY)) {
ans[i] = 1;
}
for (let x = queriesX - 1; x < queriesX + 2; x++) {
for (let y = queriesY - 1; y < queriesY + 2; y++) {
if (x < 0 || y < 0|| x >= n || y >= n || ! lights.has(coordinate(x, y))) {continue;
}
lights.delete(coordinate(x, y));
row.set(x, row.get(x) - 1);
column.set(y, column.get(y) - 1);
diagonal.set(x - y, diagonal.get(x - y) - 1);
antiDiagonal.set(x + y, antiDiagonal.get(x + y) - 1); }}}return ans;
}
const coordinate = (x, y) = > {
return x + ', ' + y;
};
Copy the code