1001. Grid Illumination
Имеется двумерная сетка размером n x n, в каждой ячейке которой есть лампа, изначально выключенная. Вам дан двумерный array позиций ламп lamps, где lamps[i] = [rowi, coli] означает, что лампа в ячейке grid[rowi][coli] включена. Даже если одна и та же лампа указана несколько раз, она включена. Когда лампа включена, она освещает свою ячейку и все остальные ячейки в той же строке, столбце или диагонали. Вам также дан другой двумерный array queries, где queries[j] = [rowj, colj]. Для j-го запроса определите, освещена ли сетка[rowj][colj] или нет. После ответа на j-й запрос выключите лампу в сетке[rowj][colj] и 8 соседних ламп, если они существуют. Лампа является смежной, если ее ячейка имеет общую сторону или угол с сеткой[rowj][colj]. return array целых чисел ans, где ans[j] должно быть 1, если ячейка в j-м запросе была освещена, или 0, если лампа не была освещена.
Example:
Input: n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
C# solution
matched/originalpublic class Solution {
public int[] GridIllumination(int n, int[][] lamps, int[][] queries) {
var lamps_on = new HashSet<(int, int)>();
var rows = new Dictionary<int, int>();
var cols = new Dictionary<int, int>();
var diag1 = new Dictionary<int, int>();
var diag2 = new Dictionary<int, int>();
foreach (var lamp in lamps) {
int r = lamp[0], c = lamp[1];
var key = (r, c);
if (lamps_on.Contains(key)) continue;
lamps_on.Add(key);
if (!rows.ContainsKey(r)) rows[r] = 0;
if (!cols.ContainsKey(c)) cols[c] = 0;
if (!diag1.ContainsKey(r - c)) diag1[r - c] = 0;
if (!diag2.ContainsKey(r + c)) diag2[r + c] = 0;
rows[r]++;
cols[c]++;
diag1[r - c]++;
diag2[r + c]++;
}
var directions = new (int, int)[] {(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)};
var result = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int r = queries[i][0], c = queries[i][1];
if (rows.ContainsKey(r) && rows[r] > 0 || cols.ContainsKey(c) && cols[c] > 0 || diag1.ContainsKey(r - c) && diag1[r - c] > 0 || diag2.ContainsKey(r + c) && diag2[r + c] > 0) {
result[i] = 1;
} else {
result[i] = 0;
}
foreach (var dir in directions) {
int nr = r + dir.Item1, nc = c + dir.Item2;
var key = (nr, nc);
if (lamps_on.Contains(key)) {
lamps_on.Remove(key);
rows[nr]--;
cols[nc]--;
diag1[nr - nc]--;
diag2[nr + nc]--;
}
}
}
return result;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public vector<int>& GridIllumination(int n, int[][] lamps, int[][] queries) {
var lamps_on = new HashSet<(int, int)>();
var rows = new unordered_map<int, int>();
var cols = new unordered_map<int, int>();
var diag1 = new unordered_map<int, int>();
var diag2 = new unordered_map<int, int>();
foreach (var lamp in lamps) {
int r = lamp[0], c = lamp[1];
var key = (r, c);
if (lamps_on.Contains(key)) continue;
lamps_on.push_back(key);
if (!rows.count(r)) rows[r] = 0;
if (!cols.count(c)) cols[c] = 0;
if (!diag1.count(r - c)) diag1[r - c] = 0;
if (!diag2.count(r + c)) diag2[r + c] = 0;
rows[r]++;
cols[c]++;
diag1[r - c]++;
diag2[r + c]++;
}
var directions = new (int, int)[] {(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)};
var result = new int[queries.size()];
for (int i = 0; i < queries.size(); i++) {
int r = queries[i][0], c = queries[i][1];
if (rows.count(r) && rows[r] > 0 || cols.count(c) && cols[c] > 0 || diag1.count(r - c) && diag1[r - c] > 0 || diag2.count(r + c) && diag2[r + c] > 0) {
result[i] = 1;
} else {
result[i] = 0;
}
foreach (var dir in directions) {
int nr = r + dir.Item1, nc = c + dir.Item2;
var key = (nr, nc);
if (lamps_on.Contains(key)) {
lamps_on.Remove(key);
rows[nr]--;
cols[nc]--;
diag1[nr - nc]--;
diag2[nr + nc]--;
}
}
}
return result;
}
}Java solution
auto-draft, review before submitimport java.util.*;
import java.math.*;
// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
public int[] GridIllumination(int n, int[][] lamps, int[][] queries) {
var lamps_on = new HashSet<(int, int)>();
var rows = new HashMap<int, int>();
var cols = new HashMap<int, int>();
var diag1 = new HashMap<int, int>();
var diag2 = new HashMap<int, int>();
foreach (var lamp in lamps) {
int r = lamp[0], c = lamp[1];
var key = (r, c);
if (lamps_on.Contains(key)) continue;
lamps_on.add(key);
if (!rows.containsKey(r)) rows[r] = 0;
if (!cols.containsKey(c)) cols[c] = 0;
if (!diag1.containsKey(r - c)) diag1[r - c] = 0;
if (!diag2.containsKey(r + c)) diag2[r + c] = 0;
rows[r]++;
cols[c]++;
diag1[r - c]++;
diag2[r + c]++;
}
var directions = new (int, int)[] {(0, 0), (0, 1), (0, -1), (1, 0), (-1, 0), (1, 1), (-1, -1), (1, -1), (-1, 1)};
var result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int r = queries[i][0], c = queries[i][1];
if (rows.containsKey(r) && rows[r] > 0 || cols.containsKey(c) && cols[c] > 0 || diag1.containsKey(r - c) && diag1[r - c] > 0 || diag2.containsKey(r + c) && diag2[r + c] > 0) {
result[i] = 1;
} else {
result[i] = 0;
}
foreach (var dir in directions) {
int nr = r + dir.Item1, nc = c + dir.Item2;
var key = (nr, nc);
if (lamps_on.Contains(key)) {
lamps_on.Remove(key);
rows[nr]--;
cols[nc]--;
diag1[nr - nc]--;
diag2[nr + nc]--;
}
}
}
return result;
}
}JavaScript solution
matched/originalclass Solution {
gridIllumination(n, lamps, queries) {
const lamps_on = new Set();
const rows = new Map();
const cols = new Map();
const diag1 = new Map();
const diag2 = new Map();
for (const [r, c] of lamps) {
const key = r * n + c;
if (lamps_on.has(key)) continue;
lamps_on.add(key);
rows.set(r, (rows.get(r) || 0) + 1);
cols.set(c, (cols.get(c) || 0) + 1);
diag1.set(r - c, (diag1.get(r - c) || 0) + 1);
diag2.set(r + c, (diag2.get(r + c) || 0) + 1);
}
const directions = [[0, 0], [0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [-1, -1], [1, -1], [-1, 1]];
const result = [];
for (const [r, c] of queries) {
if ((rows.get(r) || 0) > 0 || (cols.get(c) || 0) > 0 || (diag1.get(r - c) || 0) > 0 || (diag2.get(r + c) || 0) > 0) {
result.push(1);
} else {
result.push(0);
}
for (const [dr, dc] of directions) {
const nr = r + dr, nc = c + dc;
const key = nr * n + nc;
if (lamps_on.has(key)) {
lamps_on.delete(key);
rows.set(nr, rows.get(nr) - 1);
cols.set(nc, cols.get(nc) - 1);
diag1.set(nr - nc, diag1.get(nr - nc) - 1);
diag2.set(nr + nc, diag2.get(nr + nc) - 1);
}
}
}
return result;
}
}Algorithm
1⃣Инициализация данных:
Используйте множества для хранения включенных ламп, освещенных строк, столбцов, диагоналей и обратных диагоналей.
Инициализируйте множества и словари для отслеживания количества ламп, освещающих каждую строку, столбец, диагональ и обратную диагональ.
2⃣Обработка запросов:
Для каждого запроса проверьте, освещена ли ячейка, используя словари строк, столбцов, диагоналей и обратных диагоналей.
После ответа на запрос выключите лампу в указанной ячейке и 8 соседних ячейках, обновив множества и словари.
3⃣Обновление состояний ламп:
Обновите состояния ламп и освещенных ячеек после каждого запроса, чтобы корректно обрабатывать следующие запросы.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.