网格照明"/>
1001. 网格照明
1001. 网格照明
难度困难98
在大小为 n x n
的网格 grid
上,每个单元格都有一盏灯,最初灯都处于 关闭 状态。
给你一个由灯的位置组成的二维数组 lamps
,其中 lamps[i] = [rowi, coli]
表示 打开 位于 grid[rowi][coli]
的灯。即便同一盏灯可能在 lamps
中多次列出,不会影响这盏灯处于 打开 状态。
当一盏灯处于打开状态,它将会照亮 自身所在单元格 以及同一 行 、同一 列 和两条 对角线 上的 所有其他单元格 。
另给你一个二维数组 queries
,其中 queries[j] = [rowj, colj]
。对于第 j
个查询,如果单元格 [rowj, colj]
是被照亮的,则查询结果为 1
,否则为 0
。在第 j
次查询之后 [按照查询的顺序] ,关闭 位于单元格 grid[rowj][colj]
上及相邻 8 个方向上(与单元格 grid[rowi][coli]
共享角或边)的任何灯。
返回一个整数数组 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 <= 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
在解决这个问题前,我们先弱化一下题目难度,找找思路
假设现在我们可以认为lamps中不会存在重复的元素(即不会有一个位置存在灯这个情况出现两次),同时假设queries[j]之后不会进行灭灯的操作。
思路一:首先读题,一个亮的灯泡可以同时点亮其所在行、列、主副对角线上的位置。值得注意的是,一个位置亮的条件是只需要有一个灯泡照亮它即可;也就是说一个位置可能会被多个灯泡点亮。朴素的思路是我们开一个数组lighted_num[i][j]用于记录位置(i,j)被点亮的次数,当某一个灯泡亮的时候,将其同行、列、主副对角线上的所有位置的被点亮次数+1;若某一个灯泡被熄灭则将同行、列、主副对角线上的所有位置的被点亮次数-1,查询该位置是否亮则等价于该位置的被点亮次数是否大于1。来看一下数据规模,n最大为10^9,在存储上存在困难;另外按照上述更新策略,每次点亮一个灯泡,需要O(4*N)的复杂度来更新被点亮次数。
思路二:从N皇后问题中收到启发,该题和N皇后问题很类似,可以借鉴其思想。
采用记数数组的方式记录行、列、正副对角线被点亮的次数:
lighted_row_num:某一行被点亮的次数。
lighted_col_num:某一列被点亮的次数。
lighted_diagonal_num:对于正对角线,我们取一条来看看:(0,1)->(1,2)->(2,3),因此我们可以发现row-col是一个定值,通过这个定值就可以确定一条正对角线;在实际实现的时候,为了避免负数导致索引越界,因此可以加上一个偏置值。
lighted_counter_diagonal_num:对于副对角线,同理也取一条来看看:(2,0)->(1,1)->(0,2),会发现row+col是一个定值,可以确定一条副对角线。
因此判断[i][j]位置是否被点亮只需要判断是否 lighted_row[i] + lighted_col[j] + diagonal[i - j + n] + counter_diagonal[i + j] > 0 即可。
class Solution {
public:vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {int rows_num = lamps.size(), cols_num = lamps[0].size(), i, j, row, col;int lighted_row_num[n + 5], lighted_col_num[n + 5], lighted_diagonal_num[(n << 1) + 5], lighted_counter_diagonal_num[(n << 1) + 5];memset(lighted_row_num, 0, sizeof(lighted_row_num));memset(lighted_col_num, 0, sizeof(lighted_col_num));memset(lighted_diagonal_num, 0, sizeof(lighted_diagonal_num));memset(lighted_counter_diagonal_num, 0, sizeof(lighted_counter_diagonal_num));for(vector<int> lamp : lamps){row = lamp[0], col = lamp[1];++ lighted_row_num[row];++ lighted_col_num[col];++ lighted_diagonal_num[row - col + n];++ lighted_counter_diagonal_num[row + col];}vector<int> lighted_res;for(vector<int> query : queries){row = query[0], col = query[1];if(lighted_row_num[row] || lighted_col_num[col] || lighted_diagonal_num[row - col + n] || lighted_counter_diagonal_num[row + col]){lighted_res.push_back(1);}else{lighted_res.push_back(0);}}return lighted_res;}
};
注:笔者在实现的时候并没有使用 lighted_row[i] + lighted_col[j] + diagonal[i - j + n] + counter_diagonal[i + j] > 0 的方式来判断点亮情况,而是采用 if(lighted_row_num[row] || lighted_col_num[col] || lighted_diagonal_num[row - col + n] || lighted_counter_diagonal_num[row + col]),这样做是考虑到每个位置点亮的次数必定是满足>=0的,因此用逻辑或的短路逻辑也许可以加快点判断(猜的)-_-||
现在我们来看看我们弱化题目时做的假设:
1.对于lamps中的重复点,我们可以进行打标记去重操作。
2.对于queries[j]查询后要灭灯的重操作,我们可以遍历查询点的8邻接点,如果有光源,则进行灭灯操作,操作方式无非就是将点亮方式减1。
queries.size() <= 20000,所以实际上查询点是离散的,为了节省空间,可以用哈希套哈希结构用于打光源标记。
以下代码有点超时,还在修改,估计是因为动态分配内存的问题-。-
class Solution {public:int dir[9][2] = {{-1, -1},{-1, 0},{-1, 1},{0, -1},{0, 0},{0, 1},{1, -1},{1, 0},{1, 1},};vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {unordered_map<int, unordered_set<int>> LightSource; int rows_num = lamps.size(), cols_num = lamps[0].size(), i, j, row, col, nrow, ncol;int *lighted_row_num = new int[n + 5](), *lighted_col_num = new int [n + 5](), *lighted_diagonal_num = new int[(n << 1) + 5](), *lighted_counter_diagonal_num = new int[(n << 1) + 5]();for(vector<int> lamp : lamps){row = lamp[0], col = lamp[1];if(LightSource.find(row) == LightSource.end()){unordered_set<int> hash_cols_index;LightSource[row] = hash_cols_index;}else if(LightSource[row].find(col) != LightSource[row].end()){continue; //去重}unordered_set<int> &cols_index = LightSource[row];cols_index.insert(col);++ lighted_row_num[row];++ lighted_col_num[col];++ lighted_diagonal_num[row - col + n];++ lighted_counter_diagonal_num[row + col];}vector<int> lighted_res;for(vector<int> query : queries){row = query[0], col = query[1];if(lighted_row_num[row] || lighted_col_num[col] || lighted_diagonal_num[row - col + n] || lighted_counter_diagonal_num[row + col]){lighted_res.push_back(1);}else{lighted_res.push_back(0);}for(i = 0; i < 9; ++ i){nrow = row + dir[i][0];ncol = col + dir[i][1];if(LightSource.find(nrow) != LightSource.end() && LightSource[nrow].find(ncol) != LightSource[nrow].end()){//存在光源 不用做越界判断是因为越界的数据不可能会在哈希表里-- lighted_row_num[nrow];-- lighted_col_num[ncol];-- lighted_diagonal_num[nrow - ncol + n];-- lighted_counter_diagonal_num[nrow + ncol];//从哈希表中删除LightSource[nrow].erase(ncol);}}}return lighted_res;}
};
现在我们回看数据规模,lamps.size() < 20000,也就是说,灯泡放置点实际上离散程度也很大,因此不用数组,考虑也是用哈希表,减轻动态分配内存带来的性能压力,终于过了-_-||
class Solution {public:int dir[9][2] = {{-1, -1},{-1, 0},{-1, 1},{0, -1},{0, 0},{0, 1},{1, -1},{1, 0},{1, 1},};vector<int> gridIllumination(int n, vector<vector<int>>& lamps, vector<vector<int>>& queries) {unordered_map<int, unordered_set<int>> LightSource; int rows_num = lamps.size(), cols_num = lamps[0].size(), i, j, row, col, nrow, ncol;unordered_map<int, int> lighted_row_num, lighted_col_num, lighted_diagonal_num, lighted_counter_diagonal_num;for(vector<int> lamp : lamps){row = lamp[0], col = lamp[1];if(LightSource.find(row) == LightSource.end()){unordered_set<int> hash_cols_index;LightSource[row] = hash_cols_index;}else if(LightSource[row].find(col) != LightSource[row].end()){continue; //去重}unordered_set<int> &cols_index = LightSource[row];cols_index.insert(col);++ lighted_row_num[row];++ lighted_col_num[col];++ lighted_diagonal_num[row - col + n];++ lighted_counter_diagonal_num[row + col];}vector<int> lighted_res;for(vector<int> query : queries){row = query[0], col = query[1];if(lighted_row_num[row] || lighted_col_num[col] || lighted_diagonal_num[row - col + n] || lighted_counter_diagonal_num[row + col]){lighted_res.push_back(1);}else{lighted_res.push_back(0);}for(i = 0; i < 9; ++ i){nrow = row + dir[i][0];ncol = col + dir[i][1];if(LightSource.find(nrow) != LightSource.end() && LightSource[nrow].find(ncol) != LightSource[nrow].end()){//存在光源 不用做越界判断是因为越界的数据不可能会在哈希表里-- lighted_row_num[nrow];-- lighted_col_num[ncol];-- lighted_diagonal_num[nrow - ncol + n];-- lighted_counter_diagonal_num[nrow + ncol];//从哈希表中删除LightSource[nrow].erase(ncol);}}}return lighted_res;}
};
更多推荐
1001. 网格照明
发布评论