BricksFallingWhenHit [source code]
public class BricksFallingWhenHit {
static
/******************************************************************************/
class Solution {
int C;
public int[] hitBricks(int[][] grid, int[][] hits) {
int R = grid.length;
C = grid[0].length;
int[][] A = new int[R][C];
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++)
A[i][j] = grid[i][j];
for (int[] hit : hits)
A[hit[0]][hit[1]] = 0;
UnionFind uf = new UnionFind (R * C + 1);
for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
if (A[i][j] == 1) {
int index = i * C + j;
if (i == 0)
uf.union (R * C, index);
else if (A[i - 1][j] == 1)
uf.union (index, (i - 1) * C + j);
if (j > 0 && A[i][j - 1] == 1)
uf.union (index, i * C + j - 1);
}
}
int[] ans = new int[hits.length];
int[] moves = {-1, 0, 1, 0, -1};
for (int i = hits.length - 1; i >= 0; i--) {
int hitx = hits[i][0], hity = hits[i][1], hit_index = hitx * C + hity;
if (grid[hitx][hity] == 0)
continue;
A[hitx][hity] = 1; // this cannot be skipped, think about why
int old_top = uf.top ();
for (int k = 0; k < 4; k++) {
int nx = hitx + moves[k], ny = hity + moves[k + 1];
if (inBound (grid, nx, ny) && A[nx][ny] == 1) {
uf.union (hit_index, nx * C + ny);
}
}
if (hitx == 0)
uf.union (hit_index, R * C);
ans[i] = Math.max (0, uf.top () - old_top - 1);
}
return ans;
}
class UnionFind {
int[] size;
int[] rank;
int[] parent;
UnionFind (int len) {
size = new int[len];
rank = new int[len];
parent = new int[len];
for (int i = 0; i < len; i++) {
size[i] = 1;
parent[i] = i;
}
}
int find (int x) {
if (parent[x] != x)
parent[x] = find (parent[x]);
return parent[x];
}
boolean union (int x, int y) {
int rootx = find (x), rooty = find (y);
if (rootx != rooty) {
if (rank[rootx] < rank[rooty]) {
int tmp = rooty;
rooty = rootx;
rootx = tmp;
}
if (rank[rootx] == rank[rooty])
rank[rootx]++;
parent[rooty] = rootx;
size[rootx] += size[rooty];
return true;
}
return false;
}
int size (int x) {
return size[find (x)];
}
int top () {
return size (this.size.length - 1) - 1;
}
public String toString () {
StringBuilder sb = new StringBuilder ();
for (int i = 0; i < this.size.length; i++) {
sb.append (parent[i] + "\t");
if (i % C == C - 1)
sb.append ("\n");
}
return sb.toString ();
}
}
boolean inBound (int[][] grid, int x, int y) {
return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length;
}
}
/******************************************************************************/
public static void main(String[] args) {
BricksFallingWhenHit.Solution tester = new BricksFallingWhenHit.Solution();
int[][][] inputs = {
// {{1,0,0,0},{1,1,0,0}}, {{1,1},{1,0}}, {{0,0}},
// {{1,0,0,0},{1,1,1,0}}, {{1,0}}, {{2}},
{{0,1,1,1,1,1},{1,1,1,1,1,1},{0,0,1,0,0,0},{0,0,0,0,0,0},{0,0,0,0,0,0}}, {{1,3},{3,5},{0,3},{3,3},{1,1},{4,2},{1,0},{3,0},{4,5},{2,1},{4,4},{4,0},{2,4},{2,5},{3,4},{0,5},{0,4},{3,2},{1,5},{4,1},{2,2},{0,2}}, {{0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,1}},
// {{0,1,1,1,1},{1,1,1,1,0},{1,1,1,1,0},{0,0,1,1,0},{0,0,1,0,0},{0,0,1,0,0},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}}, {{6,0},{1,0},{4,3},{1,2},{7,1},{6,3},{5,2},{5,1},{2,4},{4,4},{7,3}}, {{0,0,0,0,0,0,0,0,0,0,0}},
};
for (int i = 0; i < inputs.length / 3; i++) {
System.out.println (Printer.separator ());
int[][] grid = inputs[3 * i], hits = inputs[3 * i + 1];
String grid_str = Matrix.printMatrix (grid);
int[] ans = inputs[3 * i + 2][0], output = tester.hitBricks (grid, hits);
String ans_str = Printer.array (ans), output_str = Printer.array (output);
System.out.printf ("%s and %s\n%s, expected: %s\n",
grid_str, Arrays.deepToString (hits), Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
);
}
}
}
最后写出来是这个算法:
class Solution {
static int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public int[] hitBricks(int[][] grid, int[][] hits) {
int R = grid.length, C = grid[0].length;
int[][] sources = new int[R][C];
for (int j = 0; j < C; j++) {
pollute (grid, sources, 0, j, new boolean[R][C], 1);
}
int[] res = new int[hits.length];
for (int i = 0; i < hits.length; i++) {
int hit_x = hits[i][0], hit_y = hits[i][1];
sources[hit_x][hit_y] = 1;
res[i] = pollute (grid, sources, hit_x, hit_y, new boolean[R][C], -1) - 1;
}
return res;
}
int pollute (int[][] grid, int[][] sources, int rx, int ry, boolean[][] visited, int increment) {
int res = 0;
if (inBound (grid, rx, ry) && !visited[rx][ry] && (!(increment > 0) || grid[rx][ry] == 1)) {
visited[rx][ry] = true;
if (!(increment < 0) || sources[rx][ry] > 0) {
sources[rx][ry] += increment;
res++;
res += pollute (grid, sources, rx + 1, ry, visited, increment);
if (rx > 0) {
res += pollute (grid, sources, rx, ry - 1, visited, increment);
res += pollute (grid, sources, rx, ry + 1, visited, increment);
}
}
}
return res;
}
boolean inBound (int[][] grid, int x, int y) {
return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length;
}
}
调了很久, 设计上也花了一些脑筋; 不过最后写完的时候意识到, 这个逻辑是有问题的; 我的逻辑是, 当我们hit了一个cell之后, 从这个cell向下或者两边进行flood, flood到的都-1, 也就是对被感染cell提供支持的金主-1, 如果-1之后不是0, 那么感染到这里就停止了, 否则继续; 2018-05-18 10:32:51 回头看看, 这个思路其实跟find eventual safe state那一题那个从sink开始remove link的思路是有点像的, 虽然没有解决这道题目本身;
但是这个逻辑连题目本身给的第二个test实际上都过不了: 当我们hit (1,2)的时候, 实际上是不应该影响(1,1)的金主的数量的;
所以难道要保留完整的指针? 每一个cell保留自己的所有parent(在第一次pollute过程当中的parent), 然后最后hit的时候, ...不对, 应该是保留自己的child, 这样hit的时候, 直接drop掉自己的child就行了;
但是感觉这样还是很多地方没有设计周到; 而且这个设计已经是非常复杂了; 每一个顶层的cell都要维护一个完整的tree; 诶, 好像也不是特别复杂? 不用直接在grid里面修改, 这些tree可以在其他的地方维护啊?
不行, 单独做tree好像不行, 因为tree之间会overlap, 所以你分别drop最后会有问题:
1 0 1 0
1 1 1 0
比如你hit(1,0)然后hit(1,2), 这两个tree实际上是有交集的; 用单独的tree很不好处理;
所以最后实际上只能转化为一个完整的graph;
如果正常的graph的node定义, 每一个node只记录几个next的话, 感觉不够? 因为这个graph里面, 一个node可能有好几个parent, 所以当你hit掉一个parent的时候, 你怎么知道应该drop哪些? 2018-05-18 10:34:40 补充说明:
首先, 我们这里的规定就是, 上边沿, 也就是hang的地方, 作为上层, 比如root之类对应的位置; 这里讨论的是一个polytree, 也就是实际上有多个root, 多个parent的这种情况; 这个上ML的时候也是讲过的;
问题就在于, 比如你把这里的A1砍掉之后, 你不知道B是不是应该drop, 因为A1是不知道A2和A3的存在的;
当然, 好像可以类似于当时find eventual safe state问题的时候的方法, 一个一个的remove link? 可行吗?
不对哦, 突然发现, 我contest当时写的做法就是这样: 你最好还是大概看一下那个算法, 因为其实写的还挺好的, 包括复用性这些, 而且代码本身里面还多次使用了imply这个技巧;
我上面这个失败代码, 用的就是思路, 最后还是错了; 具体的原因实际上上面也说过了; 就是代码里那个test1,
1 0 0 0
1 1 1 1
这个, 先hit (1,2), 我的代码会把(1,1)的in-degree也减少; 但是这个是不应该的, 因为(1,2)实际上还仰仗着(1,1), 结果反而过来砍他的in-degree了;
这个按照之前讨论的结果, 感觉也是无法解决的; 不知道怎么保留历史信息, 来辨别这种pollute的方向性;
也许可以有这样一个做法, 就完全模仿find eventual safe state当时的做法, 我们知道要hit这几个, 我们不应该从hit位置直接开始pollute, 我们应该是从sink, 也就是这里的root, 开始pollute;
然后在从多个root向下走的时候, 每当看到一个属于hit的cell, 才进行向下pollute?
好像可以? 试试看;
我想了想, 其实我这个做法还是有问题, 你仔细看我的pollute的写法, 其实是只向下, 向左, 向右走的, 这个是有问题的:
这种的, 我这个DFS思路就不对了;
那么我能不能把这个向上也加进去? 如果加进去, 怎么避免重复visit?
好像上面用的visited直接就能保证了?
这个应该不是什么大问题, 但是我发现一个新的问题, 这里给的这个input, 好像是让你对每一个给你的hit位置, 都单独返回一个drop count, 所以我之前这个从root开始直接捋的方法, 感觉效率不太好, 因为每一个hit要单独走一遍完整的grid?
看了一下editorial给的复杂度, 好像也是差不多的, 那么这个应该不是很大的问题; 2018-05-18 11:27:16
不想了; 看了一下awice已经po了editorial了;
话说回来, 这题真的是很难得, contest结束的时候, 只有这些人做出来了:
图挂了, 反正就是人很少就是了;
草稿也丢了. 反正也没写多少东西其实;
还是想要尝试一下用我之前的remove link的思路去写一下; 大概的思路上面已经介绍过了; contest一开始写的这个思路之所以有问题是因为我直接把所有的hit本身作为一个sink, 然后开始remove link;
但是回头想想, 我认为更好的做法, 应该是针对每一个hit, 我们都要从所有的sink开始走一遍; 这个在上面的解释当中也大概解释了一下;
这个multi-head remove link的操作你可能认为说不定BFS更好? 好不好? 好像也行; 其实都无所谓, 直接DFS一起写掉算了;
写的时候其实一点把握都没有, 因为我这里这个pollute函数希望包含的功能, 也就是通用性太多了, 写起来的时候要考虑的东西很多, 很头疼; 我对于这种通用性函数(用参数来控制用途)的实现一直很苦手;
写的时候就用一个很简单的例子来思考:
当然了, 是相对的, 不能太简单, 因为我们要解决的一个基本问题, 就是multi-parent情况下的这个overlap的问题, 所以这个例子要涵盖到;
failed attempt is not waste
真的真的, 还在开发阶段的时候, 不要想太复杂, 不要担心自己的代码会浪费; 首先, 没有白写的代码, 所有写出来的代码都是锻炼, 就算是最后不work的, 也是对你的锻炼; 其次, 根据我到目前这么多题的训练量来看, 很少碰到过比如说一个题的第一版的代码, 是完全的错误, 完全的浪费的; 所以, 只要有了适当程度的思考, 就可以找一个典型但是不复杂的例子, 先开始写; 不要总是想着用最复杂最general的例子, 搞得一行代码都写不出来;
实现的难点感觉还是因为想要用这个increment函数来保证整个函数的复用性; 这样你在这个函数里面写没一行代码的时候, 很自然的就不停的要想, 这一行代码, 对于increment的三种情况(>0, =0, <0)是否适用? 是否需要加特别的conditional wrap来保护起来? 包括我多次使用的imply逻辑, 也是为了完成这个目的;
感觉我的逻辑有点误区; 你看他给的第二个例子:
可以看到, 他认为最后给的结果应该是0, 0, 也就是第一个hit, drop的是0个, 这个是很正常的, 但是第二个hit, drop的也是0个, 这个意思是, 所有的hit之间不是独立的; 第一个hit造成的结果, 是被保留了的;
然后写了半天只过了一半的test, 被一个有点大的test给break掉了; 不想调了, 代码保存一下:
class Solution {
int hit_x, hit_y;
public int[] hitBricks(int[][] grid, int[][] hits) {
int R = grid.length, C = grid[0].length;
hit_x = -1;
hit_y = -1;
int[][] sources = new int[R][C];
for (int j = 0; j < C; j++) {
pollute (grid, sources, 0, j, new boolean[R][C], 1);
}
int[] res = new int[hits.length];
for (int i = 0; i < hits.length; i++) {
hit_x = hits[i][0];
hit_y = hits[i][1];
sources[hit_x][hit_y] = 1;
for (int j = 0; j < C; j++) {
res[i] += pollute (grid, sources, 0, j, new boolean[R][C], 0);
}
}
return res;
}
int pollute (int[][] grid, int[][] sources, int rx, int ry, boolean[][] visited, int increment) {
if (!inBound (grid, rx, ry) || visited[rx][ry])
return 0;
int res = 0;
if (rx == hit_x && ry == hit_y)
increment = -1;
if (!(increment > 0) || grid[rx][ry] == 1) {
visited[rx][ry] = true;
if (!(increment <= 0) || sources[rx][ry] > 0) { // only increment >0 can enter freely
sources[rx][ry] += increment;
if (sources[rx][ry] == 0 && !(rx == hit_x && ry == hit_y)) {
res++;
}
res += pollute (grid, sources, rx + 1, ry, visited, increment);
res += pollute (grid, sources, rx - 1, ry, visited, increment);
if (rx > 0) {
res += pollute (grid, sources, rx, ry - 1, visited, increment);
res += pollute (grid, sources, rx, ry + 1, visited, increment);
}
}
}
return res;
}
boolean inBound (int[][] grid, int x, int y) {
return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length;
}
}
其实还是花了点功夫的, 代码很多逻辑的设计, 我觉得也算是用了一定的毕生所学这种程度了, 最后没有过, 有点难受; 不过时间紧张, 后面有时间再调了; 代码本身的思路就是每次有一个hit, 就从所有的sink(悬挂点)开始捋, 捋到hit点的时候, 就开始remove link(之前不remove, 对应的, increment是0);
break掉的test就是这里的test3;
好像其实也不是特别大? 想调一下;
是这样一个board和算出来的sources:
{==================
0 1 1 1 1 1
1 1 1 1 1 1
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
==================}
sources:
{==================
0 5 5 5 5 5
5 5 5 5 5 5
0 0 5 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
==================}
好像是向上回头出了问题; 稍微改一下, 不能向上回头到第一行: 你看几个sink居然全都给了5;
得到新的结果:
sources:
{==================
0 1 1 1 1 1
5 5 5 5 5 5
0 0 5 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
==================}
{==================
0 1 1 1 1 1
1 1 1 1 1 1
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
==================}
好像没什么问题? 结果还是错的;
只看简单一点的trace:
可以看到, hit4发生之后, 我们应该判断(1,0)这个应该drop, 但是我的逻辑没有发现这一个;
这个是发生之后的情况:
after hit 4 = (1, 1), res: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 , sources:
{==================
0 1 1 0 1 1
4 0 4 0 4 4
0 0 4 0 0 0
0 0 0 1 0 1
0 0 0 0 0 0
==================}
那这个逻辑就很有问题, 最后(1,0)只有一个indegree被删掉了; 为什么呢?
这个逻辑改起来居然不难, 只要每次要hit之前, 把hit位置的sources改成C, 这样比如我这里我先从(0,1)这个sink开始捋的时候, 不会因为我把(1,1)的sources给清零了导致后面的sink捋不到他了;
然后被test4给break;
{==================
0 1 1 1 1
1 1 1 1 0
1 1 1 1 0
0 0 1 1 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
sources:
{==================
0 1 1 1 1
3 3 3 3 0
3 3 3 3 0
0 0 3 3 0
0 0 3 0 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
这个sources计算有点奇怪, 按理说可能应该是大家都是4这样比较好? 但是因为(0, 4)这个sink我目前的代码里面是禁止在第一行左右转的, 所以(0, 4)这个sink其实是跟谁都没有贡献, 所以所有cell最后只拿到了三个sink的贡献值;
这个决定是否正确还不得而知, 但是先看hit的时候逻辑错误在哪里;
hit0..hit2全都是drop 0, 对的, 然后hit3应该是drop0, 我drop了4;
after hit 0 = (6, 0), res: 0 0 0 0 0 0 0 0 0 0 0 , sources:
{==================
0 1 1 1 1
3 3 3 3 0
3 3 3 3 0
0 0 3 3 0
0 0 3 0 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
after hit 1 = (1, 0), res: 0 0 0 0 0 0 0 0 0 0 0 , sources:
{==================
0 1 1 1 1
0 3 3 3 0
2 3 3 3 0
0 0 3 3 0
0 0 3 0 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
after hit 2 = (4, 3), res: 0 0 0 0 0 0 0 0 0 0 0 , sources:
{==================
0 1 1 1 1
0 2 1 1 0
1 2 2 1 0
0 0 2 1 0
0 0 2 0 0
0 0 2 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
after hit 3 = (1, 2), res: 0 0 0 4 0 0 0 0 0 0 0 , sources:
{==================
0 1 1 1 1
0 1 0 0 0
0 1 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
不知道怎么处理这个, 为什么hit2之后居然有这么多变化? hit2明明是打空了的啊;
干脆直接把所有打空的hit全都跳掉, 但是还是不行;
sources:
{==================
0 1 1 1 1
3 3 3 3 0
3 3 3 3 0
0 0 3 3 0
0 0 3 0 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
after hit 1 = (1, 0), res: 0 0 0 0 0 0 0 0 0 0 0 , sources:
{==================
0 1 1 1 1
0 3 3 3 0
2 3 3 3 0
0 0 3 3 0
0 0 3 0 0
0 0 3 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
after hit 3 = (1, 2), res: 0 0 0 1 0 0 0 0 0 0 0 , sources:
{==================
0 1 1 1 1
0 1 0 2 0
0 1 2 2 0
0 0 2 2 0
0 0 2 0 0
0 0 2 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
==================}
这里好像就看出这个DFS做法的漏洞了, 你看hit1, hit1把(1,0)给打掉之后, (2,0)居然也更新了; 这个其实是不合理的;
进一步; 当你把(1,0)给打掉之后, 你认为(2, 1..3)这几个点应该怎么动作? 我这里的写法是没有被影响, 但是最后这些点会不会被减少sources, 很大程度上取决于你四个recursion call写的相互之间的顺序;
这个方法的逻辑缺陷也就大概看出来了, 顺序在这个问题当中应该是不重要的, 但是我的写法, 却成了无法避免的一环;
搞到这里感觉就调不出来了; 反正还是花了很多思考, 是很好的锻炼, 不过就这样了;
最终失败代码:
class Solution {
int hit_x, hit_y;
public int[] hitBricks(int[][] grid, int[][] hits) {
int R = grid.length, C = grid[0].length;
hit_x = -1;
hit_y = -1;
int[][] sources = new int[R][C];
for (int j = 0; j < C; j++) {
pollute (grid, sources, 0, j, new boolean[R][C], 1);
}
int[] res = new int[hits.length];
for (int i = 0; i < hits.length; i++) {
hit_x = hits[i][0];
hit_y = hits[i][1];
if (grid[hit_x][hit_y] == 0)
continue;
sources[hit_x][hit_y] = C;
for (int j = 0; j < C; j++) {
int tmp = pollute (grid, sources, 0, j, new boolean[R][C], 0);
res[i] += tmp;
}
sources[hit_x][hit_y] = 0;
}
return res;
}
int pollute (int[][] grid, int[][] sources, int rx, int ry, boolean[][] visited, int increment) {
if (!inBound (grid, rx, ry) || visited[rx][ry])
return 0;
int res = 0;
if (rx == hit_x && ry == hit_y)
increment = -1;
if (!(increment > 0) || grid[rx][ry] == 1) {
visited[rx][ry] = true;
if (!(increment <= 0) || sources[rx][ry] > 0) { // only increment >0 can enter freely
sources[rx][ry] += increment;
if (sources[rx][ry] == 0 && !(rx == hit_x && ry == hit_y)) {
res++;
}
res += pollute (grid, sources, rx + 1, ry, visited, increment);
if (rx > 1)
res += pollute (grid, sources, rx - 1, ry, visited, increment);
if (rx > 0) {
res += pollute (grid, sources, rx, ry - 1, visited, increment);
res += pollute (grid, sources, rx, ry + 1, visited, increment);
}
}
}
return res;
}
boolean inBound (int[][] grid, int x, int y) {
return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length;
}
}
开始看editorial;
自己实现editorial做法的时候, 一个小问题: 他这里UF的size, 给了一个+1, 你认为这个+1是放在UF内部自己处理好呢, 还是client处理好呢?
- 前者对应client pass给UF的length是RxC, 然后UF自己constructor的时候, +1;
- 后者对应的就是awice本来的写法, client给pass进去的就是RxC+1, UF本身就是给多少就用多少, 不管;
我感觉应该是前者, 因为一个很重要的问题是, client是知道RC这个node的存在的, 他会频繁的access这个node; 所以既然client知道所有的1D坐标的综合, 应该是0..(RC-1)加上一个RC, 那么自然传给UF的length是RC+1就更合理;
以前模仿awice的代码, 喜欢用r和c来iterate, 但是最近我觉得这个还是有点危险, 最好还是用i和j来iterate, 因为一个问题是就算是在editor里面写代码的时候, 也经常会不小心把c和C比如, 弄混掉, 就是一个shift忘记按了或者没按紧.
真正面试的时候, 白板上面c和C就更加难以分辨了; 不如直接用i和j, 反正大家都懂;
自己写一开始的union的时候, 发现awice这个三个if的做法实际上是很好的, 可以导致最后的代码是最简的; 如果用else, 写起来很麻烦, 因为这里每一个yes condition其实都是多个条件的&&判断;
整个代码还是比较长的, 写着写着又有点把自己绕进去的感觉了;
为了避免这种问题, 写代码的时候旁边放着一个例子: 不一定是一个完全具体的例子, 但是基本的逻辑特征要满足: 也就是基本的需要让你考虑到的feature, 要有;
更进一步, 这个例子甚至应该尽量避免太复杂, 比如, 这里这个倒序补全的思路, 可以假设hits只有一个嘛, 对吧, 用这个来理解逻辑就行了;
我还是要提醒一下自己: 我现在其实或多或少还是有点害怕做无用功的思想; 千万不要有这个念头; 你自己打字有多快, 你又不是不知道; 打字快你怕什么打字无用功; 有什么想法有什么code, 有什么comment, 立刻就打下来; 后面就算要删掉重写, 也是无所谓的;
自己第一次写的时候, 漏掉了两点, 一点就是上面提到过的,
if (r == 0)
dsu.union(i, R*C);
果然是很容易忘记; 另外一点是这个东西:
if (grid[r][c] == 0) {
t--;
} else
这个感觉其实更加subtle; 我当时还想了, 需要判断A(r, c)是1还是0吗? 想了想, 肯定是0啊, 因为是hit位置, 只要还没有还原这个位置, 那么肯定就是还在归零的状态;
结果这里更重要的判断, 应该是判断grid[r, c], 也就是这个hit位置在原来的grid里面是什么状况? 为什么要判断这个? 因为这个就是在判断这个hit到底有没有打中;
你一开始做A的时候, 就是所有的hit, 都归零, 但是实际上有些hit完成的是1->0的操作, 这些是打中的, 有些hit完成的实际上是0->0的操作;
为什么这两种hit需要分开考虑呢? 他这里认为, 如果是0->0, 也就是没打中的hit, 我们最后还原过程的时候, 直接跳过; 背后的逻辑是什么?
很简单嘛, 原来是0, 你现在还原, 当然不能给他重新补回到1了;
说是这么说, 这个点我还真的是一开始没有想到;
还有一个忘记的东西:
ans[i] = Math.max (0, uf.top () - old_top - 1);
因为top是有可能没变的, 所以这个difference计算的时候需要注意一下;
看起来很简单的代码, 实际写起来真的是不自己写就不知道, 要考虑的东西还是很多的;
最后也是各种写bug;
很丢人的, 最后还是要给UF加了toString的debug之后, 才真正做出来了; 最后一个bug实际上是因为在union那一步的时候, 应该检查A, 但是我顺手就写了grid; 还是粗心;
最后速度是24(33), 还可以;
UNFINISHED
editorial
这篇editorial的分又很低, 凑合看看拉倒了; 代码也是长的很可怕;
不过这个DSU大概扫了一眼, 好像就是UF啊, 那核心逻辑估计不算太长;
Approach #1: Reverse Time and Union-Find [Accepted]
Intuition
The problem is about knowing information about the connected components of a graph as we cut vertices. In particular, we'll like to know the size of the "roof" (component touching the top edge) between each cut. Here, a cut refers to the erasure of a vertex.
As we may know, a useful data structure for joining connected components is a disjoint set union structure. The key idea in this problem is that we can use this structure if we work in reverse: instead of looking at the graph as a series of sequential cuts, we'll look at the graph after all the cuts, and reverse each cut.
很聪明的idea, 不过后面实现难不难就还很难说了; 下面algorithm又开始要半读半猜了;
Algorithm
We'll modify our typical disjoint-set-union structure to include a dsu.size operation, that tells us the size of this component. The way we do this is whenever we make a component point to a new parent, we'll also send it's size to that parent.
很简单的UF修改, 自己玩过;
We'll also include dsu.top, which tells us the size of the "roof", or the component connected to the top edge. We use an ephemeral "source" node with label R * C where all nodes on the top edge (with row number 0) are connected to the source node.
就是加一个dummy root的意思, 避免deal with multi-root tree. 有什么好处还不知道;
这个root和top的数值定义还不好说;
For more information on DSU, please look at Approach #2 in the article here.
Next, we'll introduce A, the grid after all the cuts have happened, and initialize our disjoint union structure on the graph induced by A (nodes are grid squares with a brick; edges between 4-directionally adjacent nodes).
跟小岛问题的UF定义好像是差不多的; 特指node和edge的定义;
After, if we get an cut at (r, c) but the original grid[r][c] was always 0, then we couldn't have had a meaningful cut - the number of dropped bricks is 0.
Otherwise, we'll look at the size of the new roof after adding this brick at (r, c), and compare them to find the number of dropped bricks.
这里看完倒是不觉得很复杂, 就有点像making a large island里面那个, UF场景下, 0->1之后看更新; 我记得number of islands ii那一题也有这个东西;
还是看看具体实现怎么样了;
Since we were working in reverse time order, we should reverse our working answer to arrive at our final answer.
class Solution {
public int[] hitBricks(int[][] grid, int[][] hits) {
int R = grid.length, C = grid[0].length;
int[] dr = {1, 0, -1, 0};
int[] dc = {0, 1, 0, -1};
int[][] A = new int[R][C];
for (int r = 0; r < R; ++r)
A[r] = grid[r].clone();
for (int[] hit: hits)
A[hit[0]][hit[1]] = 0;
DSU dsu = new DSU(R*C + 1);
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
if (A[r][c] == 1) {
int i = r * C + c;
if (r == 0)
dsu.union(i, R*C);
if (r > 0 && A[r-1][c] == 1)
dsu.union(i, (r-1) *C + c);
if (c > 0 && A[r][c-1] == 1)
dsu.union(i, r * C + c-1);
}
}
}
int t = hits.length;
int[] ans = new int[t--];
while (t >= 0) {
int r = hits[t][0];
int c = hits[t][1];
int preRoof = dsu.top();
if (grid[r][c] == 0) {
t--;
} else {
int i = r * C + c;
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k];
int nc = c + dc[k];
if (0 <= nr && nr < R && 0 <= nc && nc < C && A[nr][nc] == 1)
dsu.union(i, nr * C + nc);
}
if (r == 0)
dsu.union(i, R*C);
A[r][c] = 1;
ans[t--] = Math.max(0, dsu.top() - preRoof - 1);
}
}
return ans;
}
}
class DSU {
int[] parent;
int[] rank;
int[] sz;
public DSU(int N) {
parent = new int[N];
for (int i = 0; i < N; ++i)
parent[i] = i;
rank = new int[N];
sz = new int[N];
Arrays.fill(sz, 1);
}
public int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]);
return parent[x];
}
public void union(int x, int y) {
int xr = find(x), yr = find(y);
if (xr == yr) return;
if (rank[xr] < rank[yr]) {
int tmp = yr;
yr = xr;
xr = tmp;
}
if (rank[xr] == rank[yr])
rank[xr]++;
parent[yr] = xr;
sz[xr] += sz[yr];
}
public int size(int x) {
return sz[find(x)];
}
public int top() {
return size(sz.length - 1) - 1;
}
}
大概可以看一下他这里的UF的实现方式, 整体是类似的; 他给的初始化的size是R x C + 1, 这个是为什么呢? 难道是因为给一个1的offset? 因为我之前也写过这种1D代表2D的UF, 那时候也没有觉得需要专门给这个一个+1啊;
然后UF初始化, rank一开始都是0, size都是1, 这个很正常的;
看他union的写法, 有一个swap的操作, 来维护rank[xr] >= rank[yr], 这样避免后面真正union的时候需要写两段对称的代码;
注意这里为什么只要swap两个root就行了: UF里面所有的信息, 都是被root id给identify的, 所以一个root代表的就是一个group; 你可以理解为这里这个swap最后对调的其实是两个group本身;
然后真正的merge操作也写的很简练, 先判断rank怎么更新; 然后parent和size的更新就是简单的很类似的; awice这个UF其实写的不错的; 我一开始还有点担心他模仿uwi那个写法;
uwi那个写法完全就是他自己熟悉了, 所以一段代码贴上去, 他知道怎么用就行了; 根本懒得去管内部的实现; 他那个UF的实现, 相对于这里的, 还是要复杂很多了;
我反正给了一个五星, awice这篇文章其实讲的还不错了;
size就很简单, 直接要先找到root, 然后返回size; 这个也是讲过的, UF get信息的时候, 一定要找到root, 而不是直接返回自己的;
这个top干嘛的? 看不太懂;
symmetric union
然后看他UF初始化之后的主函数里面的union操作, 可以看到, 他这个是跟uwi用的一样的逻辑, 也就是有方向性的union. 他这里也是类似的, 只允许向上和向左进行union;
然后RC这个是一个dummy, 那么这个好像就解释了为什么他的UF需要有RC+1的size;
第一行的所有的1, 他都跟RC进行了union; 然后所有其他位置的, 正常的向左向上union操作就行了;
t一开始一个--操作, 也就是t实际上是从hits.length - 1开始的, 所以t的定义应该是一个类似next position to fetch之类的定义, 这个也是熟悉的semantics;
t是一个倒序, 这个也是上面介绍过了的;
感觉这个top好像就是不会掉的cell的总数? 是不是这样? 所有的第一行的cell都和RC进行了连接, 然后所有能够碰到第一行的, 也都跟第一行的sink进行了连接, 所以最后对应的, 他的top实现, 你看, 是size(RC) - 1, -1是因为把RC自己给减掉; 所以实际上就是现在还安全挂着的所有的cell的总数;
他t--的时机不是很好; 不用两个branch处理, 直接一个conditional只处理确实hit的那些hits就行了;
最后reverse hit的代码其实也不是很难理解, 一个不好理解的地方:
if (r == 0)
dsu.union(i, R*C);
严格来说这个也能理解吧, 只不过很容易忘记掉;
同时也体现出来为什么要有RC这个dummy; 因为计算总悬挂量的时候, 会方便很多: 有一个专门的group;
题目本身就是, 虽然好像给的是multi sink这样的一个结构, 但是最后问你的信息, 只关系实际上有多少cell能挂住; 那么我们就用dummy把能挂住这个概念给具体化: 他们都在一个group里面, 你想怎么搞, 都很方便;
总体来看代码不是很复杂, 这个做法的难点还是在于想法, 怎么想到把这个问题改成UF倒序补全的问题;
没时间所以没有认真看, 因为editorial这个解法最后居然很慢, 所以瞄了一眼submission, 这个17(87):
class Solution {
public int[] hitBricks(int[][] grid, int[][] hits) {
int m = grid.length;
int n = grid[0].length;
int c = hits.length;
//Mark whether there is a brick at the each hit
for(int[] h: hits){
if (grid[h[0]][h[1]] == 1) grid[h[0]][h[1]] = 0;
else grid[h[0]][h[1]] = -1;
}
//Mark all root bricks as value 2 after all hits, no counting
for(int i = 0; i < n; i++)
dfs(0, i, grid);
//Reversely add the block of each hit back and get count of saved bricks
int[] ret = new int[c];
for(int i = c-1; i >= 0; i--) {
int[] h = hits[i];
if(grid[h[0]][h[1]] == -1) continue; //This brick is originally empty
grid[h[0]][h[1]] = 1; //Bring this brick back
if(!isConnected2Top(h[0], h[1], grid)) continue;
ret[i] = dfs(h[0], h[1], grid)-1;
}
return ret;
}
//Connect unconnected bricks and mark visited bricks as value 2
//Return how many extra bricks will be saved bacause of adding (i, j) back, including (i, j) itself
private int dfs(int i, int j, int[][] grid){
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != 1)
return 0;
int ret = 1;
grid[i][j] = 2;
ret += dfs(i-1, j, grid);
ret += dfs(i+1, j, grid);
ret += dfs(i, j-1, grid);
ret += dfs(i, j+1, grid);
return ret;
}
//Check whether (i, j) is connected to top
private boolean isConnected2Top(int i, int j, int[][] grid){
// Check if adjacent bricks are not falling or (i, j) itself is on the top
if ((i-1 >= 0 && grid[i-1][j] == 2)
|| (i+1 < grid.length && grid[i+1][j] == 2)
|| (j-1 >= 0 && grid[i][j-1] == 2)
|| (j+1 < grid[0].length && grid[i][j+1] ==2 )
|| (i == 0)) return true;
return false;
}
}
所以UF并不是这题的唯一办法;
但是人家这里最后核心思路还是想到了倒序补全这个思路, 所以看来这个insight是解这个题目的关键;
deletion is hard
这个学OS的时候也是碰到过的一个观点, delete总是很难的; 好像就很多人喜欢反过来用addition来解决deletion的问题, 或许是值得培养的一个思想方式?
回头想想, 之前那种把方向变量存在一个数组里面然后用循环来写四方向遍历, 实际上优势也不是特别明显; 尤其是如果你参考我之前自己的那个失败的方法的代码, 四个方向当中可能你会对部分方向想要有单独的conditional方法来wrap, 这个你用循环方向变量的方法来写, 最后反而就麻烦了;
这个人的思路虽然很类似editorial的reversed UF, 但是感觉还是有不少差别的; 他这里的这个DFS又是一个通用函数, 所以理解起来其实还是有点困难;
他一开始在删除hit位置的时候, 用的方法就是一个固定的--, 也就是1->0, 0->-1这两个操作, 这样的好处是他只需要维护一个版本的grid(瘦身之后的版本)就行了, 而不用跟editorial那样, 两个版本都要保留下来; 后面补全的时候, 直接看瘦身之后的值, 就知道最开始的这个hit是不是命中, 也就知道这个hit是否应该被补全;
另外, 其实这个DFS解法也未见得就比UF解法好很多, 实际上24和17差的也不是很多, 而且awice的原版的UF我刚提交了一下, 21(66), 也很不错的了;
当然了, 能多掌握一个解法, 肯定是很好的, 比如爱问Follow-Up的Google, 可能就问你, 不用UF, 用传统的DFS/BFS能不能做之类的;
盯着发呆看不懂, 不弄了, 直接跑一下看看, 打trace(我上面已经有一个AC的代码, 直接comment掉就行了, 不用删掉);
比较幸运的是这个代码最后没想到有这么完整的comment;
第一个DFS他直接标注了(主函数里面), 只是把所有的root, 也就是我说的sink, 给mark成2; 比如我们一开始的这个例子: test3:
一开始的grid:
0 1 1 1 1 1
1 1 1 1 1 1
0 0 1 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
然后hit归零之后:
0 1 0 0 0 0
0 0 1 0 1 0
0 -1 0 0 -1 -1
-1 0 -1 -1 -1 -1
-1 -1 -1 0 -1 -1
然后第一个DFS结束之后:
0 2 0 0 0 0
0 0 1 0 1 0
0 -1 0 0 -1 -1
-1 0 -1 -1 -1 -1
-1 -1 -1 0 -1 -1
好像也没有多少改变的样子; 只是一个mark, 所以返回值这里被无视了;
最后一个循环是主要逻辑; 循环也是一个倒序进行, 因为是倒序补全, 这个已经说过了;
第一个continue是判断打空的情况: 这个很好判断, 上面一开始hit清零的时候保存了这个信息;
然后是0->1的flip, 然后就到了他这个connected函数的实现上面了;
诶, 我好像懂了他这个概念了啊, 他其实就是在这个倒序补全的过程当中, 每次一个命中的hit, 补全之后(grid对应的位置重新设置到1), 然后他重新又是一个DFS, 意思就是重新一个mark, 这个很慢吧? 这要进行很多次的完整DFS;
注意不同的DFS mark之间是互相独立的, 因为之前被mark的全都搞成了2, 那么后面的新的DFS是会跳过这些的;
大概知道意思了, 不多花时间了; 思路是可以学习的, 也是适合在面试的时候提的思路; 不过应该不是最优解, 不知道为什么最后比UF还要快;
唯一一个还没有搞清楚的, 就是这个DFS的返回值到底是干什么的了;
理解这个, 还是从Bottom-Up的initialization开始理解;
假设一个leaf位置, 是什么样的? 首先他要能够通过DFS一开始的这个if, 也就是说他自己要还不是2, 然后进去了之后, 立刻标2, 然后ret是1, 然后找自己的child; 因为是leaf节点, 所以所有child的DFS无效(要么超界, 要么已经是2或者-1或者0之类的, 反正不能标2(只有1能够标2));
那么这个leaf最后就返回了1; 结合他DFS上面给的这个comment, 是可以理解的, 我这个leaf只能把我自己给挂到top上面去(对应于可以标2), 所以只能返回1;
那么向上的层面的这些, 也就能类似理解了;
总体来说他这个通用函数本身不是设计的特别复杂, 跟我自己之前写的那个的复杂程度还是有点差距的; 当然啦, 人家写的是对的, 所以 :) 你懂的;
其实不是一个特别复杂的算法, 应该是CxN的算法, C是hit数量, N是grid大小;
不对, 他这个你看, 每次恢复一个hit之后, 我们先确定这个hit是一个能够跟top连接的, 然后他的第二个DFS, 是从hit位置出发的; 这个很多时候估计是不用O(N)的; 不是我那种, 直接从所有的sink全部开始走一遍, 那个就慢了;
其实他这个DFS思路也是有点类似UF的不是吗? 每次恢复一个hit之后, 先看看他四周, 四个方向如果有一个已经是2, 也就是已经是连接top的, 那么才开始DFS, 这个DFS实际上...也有可能很大好像? 因为我们只知道四个方向上面至少有一个是2, 所以四个方向上面, 至少有一个能够很快terminate, 但是其他至多三个方向上这个DFS能走多远, 其实是没有保证的;
所以又不太理解为什么他这个算法能够这么快了;
话说回来, UF的做法还是很值得好好掌握的, 我认为UF应该才是这题的钦定做法, 实现的时候虽然有细节(毕竟是hard, 要么是idea很难很难想, 要么是实现很难, 这题实际上有点折中在两者之间)难点, 但是整体完全属于应该掌握的范畴;
contest:
class Solution {
int n,m;
int dfs(int[][] grid, int x,int y)
{
if (x<0 || x>=n || y<0 || y>=m || (grid[x][y]+1)/2!=1) return 0;
grid[x][y]=3;
int ans=1;
ans+=dfs(grid,x,y-1);
ans+=dfs(grid,x,y+1);
ans+=dfs(grid,x-1,y);
ans+=dfs(grid,x+1,y);
return ans;
}
boolean have(int[][] grid, int x,int y)
{
if (x<0 || x>=n || y<0 || y>=m || grid[x][y]!=3) return false; else return true;
}
public int[] hitBricks(int[][] grid,int[][] hits) {
n=grid.length;m=grid[0].length;
int t=hits.length;
boolean[] bo=new boolean[t];
for (int k=0;k<t;k++)
{
int[] h=hits[k];
bo[k]=(grid[h[0]][h[1]]==1);
grid[h[0]][h[1]]=0;
}
for (int i=1;i<n;i++)
for (int j=0;j<m;j++)
if (grid[i][j]==1) grid[i][j]=2;
for (int j=0;j<m;j++)
if (grid[0][j]==1) dfs(grid,0,j);
int[] ans=new int[t];
for (int k=t-1;k>=0;k--)
if (bo[k])
{
int[] h=hits[k];
//if (1==1) return h;
grid[h[0]][h[1]]=2;
if (!(have(grid,h[0],h[1]-1) ||have(grid,h[0],h[1]+1) ||have(grid,h[0]-1,h[1]) ||have(grid,h[0]+1,h[1])|| h[0]==0)) continue;
ans[k]=dfs(grid,h[0],h[1])-1;
}
return ans;
}
}
还没来得及看, 代码写的还算干净;
Problem Description
We have a grid of 1s and 0s; the 1s in a cell represent bricks. A brick will not drop if and only if it is directly connected to the top of the grid, or at least one of its (4-way) adjacent bricks will not drop.
We will do some erasures sequentially. Each time we want to do the erasure at the location (i, j), the brick (if it exists) on that location will disappear, and then some other bricks may drop because of that erasure.
Return an array representing the number of bricks that will drop after each erasure in sequence.
Example 1:
Input:
grid = [[1,0,0,0],[1,1,1,0]]
hits = [[1,0]]
Output: [2]
Explanation:
If we erase the brick at (1, 0), the brick at (1, 1) and (1, 2) will drop. So we should return 2.
Example 2:
Input:
grid = [[1,0,0,0],[1,1,0,0]]
hits = [[1,1],[1,0]]
Output: [0,0]
Explanation:
When we erase the brick at (1, 0), the brick at (1, 1) has already disappeared due to the last move. So each erasure will cause no bricks dropping. Note that the erased brick (1, 0) will not be counted as a dropped brick.
Note:
- The number of rows and columns in the grid will be in the range [1, 200].
- The number of erasures will not exceed the area of the grid.
- It is guaranteed that each erasure will be different from any other erasure, and located inside the grid.
- An erasure may refer to a location with no brick - if it does, no bricks drop.
Difficulty:Hard
Total Accepted:1.2K
Total Submissions:5.7K
Contributor:awice
Companies
google
Related Topics
union find