2023-06-26：在大小為 n x n 的網(wǎng)格 grid 上，每個單元格都有一盞燈，最初燈都處于 關(guān)
2023-06-26：在大小為 n x n 的網(wǎng)格 grid 上，每個單元格都有一盞燈，最初燈都處于 關(guān)閉 狀態(tài)
給你一個由燈的位置組成的二維數(shù)組 lamps
其中 lamps[i] = [rowi, coli] 表示 打開 位于 grid[rowi][coli] 的燈
即便同一盞燈可能在 lamps 中多次列出，不會影響這盞燈處于 打開 狀態(tài)
當(dāng)一盞燈處于打開狀態(tài)，它將會照亮 自身所在單元格
以及同一 行 、同一 列 和兩條 對角線 上的 所有其他單元格
另給你一個二維數(shù)組 queries ，其中 queries[j] = [rowj, colj]
對于第 j 個查詢，如果單元格 [rowj, colj] 是被照亮的
則查詢結(jié)果為 1 ，否則為 0 。在第 j 次查詢之后 [按照查詢的順序]
關(guān)閉 位于單元格 grid[rowj][colj] 上
及相鄰 8 個方向上（與單元格 grid[rowi][coli] 共享角或邊）的任何燈。
返回一個整數(shù)數(shù)組 ans 作為答案， ans[j] 應(yīng)等于第 j 次查詢 queries[j] 的結(jié)果.
1 表示照亮，0 表示未照亮。
輸入：n = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]。
輸出：[1,0]。
答案2023-06-26：
大體步驟如下：
1.首先，定義一個存儲燈位置的二維數(shù)組 lamps，和查詢位置的二維數(shù)組 queries。
2.創(chuàng)建四個map，用于記錄每行、每列、左上到右下對角線和右上到左下對角線上的燈的數(shù)量。還有一個points map，用于存儲所有點的狀態(tài)。
3.遍歷燈的位置，將燈的狀態(tài)記錄到相關(guān)的map中，并將點的狀態(tài)記錄到points map中。
4.創(chuàng)建一個結(jié)果數(shù)組 ans，用于存儲每個查詢的結(jié)果。
5.對于每一個查詢位置，初始化結(jié)果為0。
6.如果查詢位置所在的行、列、左上到右下對角線或者右上到左下對角線上有燈，將結(jié)果設(shè)為1。
7.遍歷查詢位置周圍的8個方向，如果有燈，則關(guān)閉該燈，并在相關(guān)的map中減去相應(yīng)的數(shù)量。
8.返回結(jié)果數(shù)組 ans。
時間復(fù)雜度分析:
??遍歷燈的位置并初始化maps需要 O(lamps)，其中 lamps 是燈的數(shù)量。
??對于每個查詢位置，遍歷周圍的8個方向，檢查是否有燈需要 O(1) 的時間。
??因此，總的時間復(fù)雜度為 O(lamps + queries)。
空間復(fù)雜度分析:
??maps 和 points 的空間復(fù)雜度均為 O(lamps)，其中 lamps 是燈的數(shù)量。
??結(jié)果數(shù)組 ans 的空間復(fù)雜度為 O(queries)，其中 queries 是查詢的數(shù)量。
??因此，總的空間復(fù)雜度為 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完整代碼如下：
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;
}
