- 921. Minimum Add to Make Parentheses Valid 使括号有效的最少添加
- 915. Partition Array into Disjoint Intervals 分割数组
- 932. Beautiful Array 漂亮数组
- 940. Distinct Subsequences II 不同的子序列 II
题目地址:https://leetcode.com/problems/available-captures-for-rook/
Ona N x N
grid of cells, each cell (x, y)
with 0 <= x < N
and 0 <= y < N
has a lamp.
Initially, some number of lamps are on. lamps[i]
tells us the location of the i-th lamp that is on. Each lamp that is on illuminates every square on its x-axis, y-axis, and both diagonals (similar to a Queen in chess).
Forthe i-th query queries[i] = (x, y), the answer to the query is 1 if the cell (x, y) is illuminated, else 0.
After each query (x, y)
[in the order given by queries
], we turn off any lamps that are at cell (x, y)
or are adjacent 8-directionally (ie., share a corner or edge with cell (x, y)
.)
Return an array of answers. Each value answer[i]
should be equal to the answer of the i
-th query queries[i]
.
Example 1:
Input: N = 5, lamps = [[0,0],[4,4]], queries = [[1,1],[1,0]]
Output: [1,0]
Explanation:
Before performing the first query we have both lamps [0,0] and [4,4] on.
The grid representing which cells are lit looks like this, where [0,0] is the top left corner, and [4,4] is the bottom right corner:
1 1 1 1 1
1 1 0 0 1
1 0 1 0 1
1 0 0 1 1
1 1 1 1 1
Then the query at [1, 1] returns 1 because the cell is lit. After this query, the lamp at [0, 0] turns off, and the grid now looks like this:
1 0 0 0 1
0 1 0 0 1
0 0 1 0 1
0 0 0 1 1
1 1 1 1 1
Before performing the second query we have only the lamp [4,4] on. Now the query at [1,0] returns 0, because the cell is no longer lit.
Note:
1、 1<=N<=10^9;
2、 0<=lamps.length<=20000;
3、 0<=queries.length<=20000;
4、 lamps[i].length==queries[i].length==2;
给出了一个N*N的格子空间,在lams[i]位置上有灯,每个灯会照亮相同x方向、相同y方向、和两条对角线方向共四个方向。我们给出了一系列的queries,这个queries[i]代表查询该位置是否有亮光,同时每次查询的话会把该位置和该位置的8联通方向的亮灯全部关掉。如果queries[i]有光亮的话,那么返回1,否则返回0,问最后的查询结果是多少。
这个题目其实已经告诉我们,类似于象棋的皇后问题。那么就联想起前面做过的51. N-Queensopen in new window问题,在N皇后问题中,判断两个点是否相同的x和y坐标当然容易,判断两点是否在对角线上怎么做呢?
在同一条左斜线上的点,方程式都形如x+y = c,也就是他们的坐标之和相等 在同一条右斜线上的点,方程式都刑辱y = x+c,也就是他们的坐标之差相等
所以,如果知道了这个结论,我们只需要四个字典,分别保存每个点的横坐标、纵坐标、x + y、x - y,然后如果有两个点的满足其中任何一个相等就说明两者共线。
代码还是很简单的,只是别手误就行。
C++代码如下:
class Solution {
public:
vector<int> gridIllumination(int N, vector<vector<int>>& lamps, vector<vector<int>>& queries) {
unordered_map<int, int> xcount;
unordered_map<int, int> ycount;
unordered_map<int, int> l_diagcount;
unordered_map<int, int> r_diagcount;
set<pair<int, int>> lset;
for (auto l : lamps) {
++xcount[l[0]];
++ycount[l[1]];
++l_diagcount[l[0] + l[1]];
++r_diagcount[l[0] - l[1]];
lset.insert({l[0], l[1]});
}
vector<int> res;
for (auto q : queries) {
if (xcount[q[0]] || ycount[q[1]] || l_diagcount[q[0] + q[1]] || r_diagcount[q[0] - q[1]]) {
res.push_back(1);
} else {
res.push_back(0);
}
for (int i = -1; i <= 1; ++i) {
for (int j = -1; j <= 1; ++j) {
pair<int, int> xy = {q[0] + i, q[1] + j};
if (lset.count(xy)) {
--xcount[xy.first];
--ycount[xy.second];
--l_diagcount[xy.first + xy.second];
--r_diagcount[xy.first - xy.second];
lset.erase(xy);
}
}
}
}
return res;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
2022
DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有
本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发
我正在练习我的 Javascript,所以我制作了一个跟随鼠标的功能。我成功了,但现在我有了一个新想法,但我不确定是否可行。 有没有办法让“视觉球体”跟随鼠标,以便该区域中的所有内容都可见?。有点像使
对my question的回答表明 DOT3 光照可以帮助 OpenGL ES 渲染,但我很难找到 DOT3 光照的合适定义。 编辑 1 非常感谢 iPhone 相关信息。 最佳答案 DOT3 照明通
所以我一直在研究照明,为了阴影贴图的目的,我根据半径而不是三个衰减因子(常数、线性和二次)进行光衰减,而且,嗯......它看起来不太好靠近边缘。 /image/H680a.png 它切断得非常快,着
我已经问过这个问题了,但没有得到答案。顺便说一句,我发现了一些新东西。我想显示由 Solid Works 导出的 WRL 文件的 3D 模型。该文件包含三角形的顶点,我用 glBegin(GL_TRI
我在我的 JOGL 项目中添加了一个光源,当物体静止时,它似乎工作得很好,当我移动相机时,它随着它旋转而逐渐变暗,这是我所期望的,但一旦它旋转 90 度屏幕完全黑了,有人知道这是为什么吗?另一侧是否需
我正在尝试使用 iPhone LED 执行渐进式照明。为此,我尝试使用 setTorchModeOnWithLevel 方法, float 值定期增加,从 0.1 到 AVCaptureMaxAvai
我有一个我无法解决的问题。我刚刚在我的项目中添加了一个点光源,它使纹理完全变黑。我不知道为什么。 我认为这可能是法线没有正确更新,也可能是 s.x、s.y 和 s.z 的计算。 如果有人有时间看一下并
我有一张碰撞图,有些地方我想成为光源。光源提供的光实际上是我可以看到地面的形状。现在看起来像这样: 所以光线穿过墙壁。我想让它看起来像这样: (我用深黄色标记了与墙壁的碰撞) 因此光线在遇到墙壁时停止
我正在阅读 opengl.org 中的以下 Phong 照明着色器: Phong Illumination in Opengl.org 顶点和片段着色器如下: 顶点着色器: varying vec3
我读过的几乎所有文章和书籍都指出最终颜色的构成是:finalColor = ambientColor + lambertianTerm * diffuseColor (= material color
我一直在尝试检测移动的车辆。但是由于云的不同光照条件(不是云的阴影,只是照明)背景减法失败。 我已经在这里上传了我的输入视频 --> Youtube (30secs) 这是我使用 opencv 中可用
我只想点亮键盘上的一个键 (Logitech G910),同时设置鼠标颜色(罗技G303)。 在键盘上设置一个键可以正常工作,但是如果不同时将键盘上的所有键都设置为该颜色,我就无法设置鼠标的颜色。 我
我正在尝试获取 Logitech's own LED SDK使用我的 G502,但我不能。我使用的是 SDK 版本 8.82.7,这是目前最新的版本。我在 SO 或互联网的其他部分也找不到任何东西,所
因为我是着色器的完全菜鸟,所以我在尝试使用 2D 照明系统时遇到了一些问题,该系统基本上用 2D 黑色纹理覆盖屏幕,在亮区所在的位置有透明孔。 因为我只使用一个纹理,所以我想我必须在片段着色器中执行此
我试图使用此处的代码在 Laravel 中创建迁移。但不幸的是它会弹出一个像这里给出的错误。我看到了一些我手动创建表的答案..但这与迁移的整个想法非常相悖..不是吗? 迁移文件 2018_05_05_
我是一名优秀的程序员,十分优秀!