力扣1001网格照明解法

力扣1001 网格照明 题解问题分析网格照明问题LeetCode 1001要求模拟在n x n网格上的一系列操作放置灯和查询位置是否被照亮。核心挑战在于高效处理大规模网格n 可达 10^9和大量操作lamps 和 queries 长度可达 2 * 10^4。直接存储和遍历网格的二维数组显然不可行。问题的关键在于理解一盏灯会照亮其所在的行、列和两条对角线。因此我们可以通过维护四个哈希表来分别记录被照亮的行、列和两条对角线的状态从而将空间复杂度从 O(n²) 降低到 O(L Q)其中 L 是灯的数量Q 是查询的数量。算法思路与数据结构设计1. 核心数据结构使用四个哈希表在C中为unordered_map来分别记录row行索引 - 该行上亮着的灯的数量。col列索引 - 该列上亮着的灯的数量。diag1主对角线左上-右下索引 - 该对角线上亮着的灯的数量。对角线索引可通过行索引 - 列索引计算。diag2副对角线右上-左下索引 - 该对角线上亮着的灯的数量。对角线索引可通过行索引 列索引计算。此外需要一个快速查找灯位置的数据结构用于在关闭周边灯时判断该位置是否真的有灯。使用unordered_set存储灯的唯一位置编码例如长整型或字符串是高效的选择。2. 算法步骤初始化将所有灯的位置加入灯位置集合并更新四个哈希表的计数。处理查询对于每个查询位置(query_x, query_y)检查四个哈希表中对应的计数是否大于0。只要有一个大于0则该位置被照亮答案记录为1否则为0。随后关闭查询位置及其周围8个相邻格子九宫格内的所有灯。遍历九宫格内的每个位置(nx, ny)。如果(nx, ny)在灯位置集合中则将其从集合中移除并将四个哈希表中对应的计数减1如果减到0可以选择删除该键值对以节省空间。返回结果返回所有查询结果的数组。C 代码实现#include vector #include unordered_map #include unordered_set using namespace std; class Solution { public: vectorint gridIllumination(int n, vectorvectorint lamps, vectorvectorint queries) { // 核心数据结构初始化 unordered_mapint, int row, col, diag1, diag2; // 使用长整型编码灯的位置避免字符串操作开销 unordered_setlong long lampSet; // 方向数组表示查询位置周围的8个邻居和自身共9个位置 int dirs[9][2] {{0,0}, {0,1}, {0,-1}, {1,0}, {-1,0}, {1,1}, {1,-1}, {-1,1}, {-1,-1}}; // 步骤1放置所有灯初始化哈希表 for (const auto lamp : lamps) { int x lamp[0]; int y lamp[1]; long long key (long long)x * n y; // 将二维坐标编码为一维唯一键 // 防止重复的灯被重复添加 if (lampSet.insert(key).second) { row[x]; col[y]; diag1[x - y]; // 主对角线索引 diag2[x y]; // 副对角线索引 } } vectorint ans; ans.reserve(queries.size()); // 预分配空间提升效率 // 步骤2处理每个查询 for (const auto query : queries) { int x query[0]; int y query[1]; // 判断当前位置是否被照亮检查对应的行、列、对角线是否有灯 bool isLit (row[x] 0) || (col[y] 0) || (diag1[x - y] 0) || (diag2[x y] 0); ans.push_back(isLit ? 1 : 0); // 步骤3关闭九宫格内的灯 for (const auto dir : dirs) { int nx x dir[0]; int ny y dir[1]; // 检查新坐标是否在网格范围内 if (nx 0 nx n ny 0 ny n) { long long key (long long)nx * n ny; // 如果该位置有灯则关闭它 if (lampSet.erase(key)) { // 从哈希表中移除该灯的影响 if (--row[nx] 0) row.erase(nx); if (--col[ny] 0) col.erase(ny); if (--diag1[nx - ny] 0) diag1.erase(nx - ny); if (--diag2[nx ny] 0) diag2.erase(nx ny); } } } } return ans; } };复杂度分析维度复杂度说明时间复杂度O(L Q)其中 L 是lamps的长度Q 是queries的长度。放置灯为 O(L)每个查询的检查和关灯操作是常数时间最多检查9个位置。空间复杂度O(L)主要用于存储lampSet和四个哈希表最坏情况下都与灯的数量 L 成正比。关键点与技巧总结坐标编码将二维坐标(x, y)编码为(long long)x * n y确保在unordered_set中唯一且高效。对角线索引计算主对角线斜率1索引值为x - y。同一条主对角线上的点此值相同。副对角线斜率-1索引值为x y。同一条副对角线上的点此值相同。避免重复灯使用unordered_set的insert方法返回值来判断灯是否已存在防止哈希表计数错误增加。哈希表清理当某个行、列或对角线的灯数量减为0时使用erase方法删除该键有助于减少哈希表的大小提升后续查询效率尽管不是必须的。方向遍历使用预定义的方向数组dirs使代码更简洁避免手动书写9个条件判断。此解法通过将空间状态从网格转换到线性的哈希表巧妙地解决了超大网格带来的内存限制问题是典型的利用数据结构降维思想的案例。参考来源JavaScript版LeetCode题解你值得拥有golang力扣leetcode 1001.网格照明力扣hot 100 题解记录一【题解】—— LeetCode一周小结25瑞_力扣LeetCode_二叉搜索树相关题LeetCode 第 290 场周赛 题解及思路