Menu

Leetcode – Walls and Gates



My code:

Question:

public class Solution { private int row = 0; private int col = 0; private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; private class Pair { int x; int y; Pair(int x, int y) { this.x = x; this.y = y; } } public void wallsAndGates(int[][] rooms) { if (rooms == null || rooms.length == 0 || rooms[0].length == 0) { return; } this.row = rooms.length; this.col = rooms[0].length; Queue<Pair> q = new LinkedList<Pair>(); for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (rooms[i][j] == 0) { q.offer(new Pair; } } } while (!q.isEmpty { Pair curr = q.poll(); int curr_x = curr.x; int curr_y = curr.y; for (int k = 0; k < 4; k++) { int x = curr_x + dir[k][0]; int y = curr_y + dir[k][1]; if (check && rooms[x][y] == Integer.MAX_VALUE) { rooms[x][y] = 1 + rooms[curr_x][curr_y]; q.offer(new Pair; } } } } private boolean check(int i, int j) { if (i < 0 || i >= row || j < 0 || j >= col) { return false; } return true; }}

图片 1Paste_Image.png

一开首拿 DFS来做,发掘 stack
overflow.或许这道标题对stack要求比较严谨。然后拿BFS做,再一次超时。。。然后本身才察觉,原本自家的BFS作用非常低,是Naive
BFS

My code:

下一场笔者自个儿写出了当今的 AC解法,论坛里旁人称作:Multi-End
BFS为何这么叫吧?笔者有协和的知晓。日常性的BFS,都是从一个点,多少个end起始,BFS,一步步扩大。不过那么些里面,一初步队列之中有多少个点,四个end

import java.util.LinkedList;import java.util.Queue;public class Solution { private int width = 0; private int height = 0; public void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) return; width = board.length; height = board[0].length; for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { if ((i == 0 || i == width - 1 || j == 0 || j == height - 1) && (board[i][j] == 'O')) { board[i][j] = 'R'; bfs(i, j, board); } } } for (int i = 0; i < width; i++) { for (int j = 0; j < height; j++) { if (board[i][j] == 'R') board[i][j] = 'O'; else if (board[i][j] == 'O') board[i][j] = 'X'; } } } private void bfs(int i, int j, char[][] board) { if (i < 0 || i >= width || j < 0 || j >= height) return; Queue<Integer> q = new LinkedList<Integer>(); q.offer(i * height + j); while (!q.isEmpty { int id = q.poll(); int tempWidth = id / height; int tempHeight = id % height; if (tempHeight - 1 >= 0) if (board[tempWidth][tempHeight - 1] == 'O') { board[tempWidth][tempHeight - 1] = 'R'; q.offer(tempWidth * height + tempHeight - 1); } if (tempHeight + 1 < height) if (board[tempWidth][tempHeight + 1] == 'O') { board[tempWidth][tempHeight + 1] = 'R'; q.offer(tempWidth * height + tempHeight + 1); } if (tempWidth - 1 >= 0) if (board[tempWidth - 1][tempHeight] == 'O') { board[tempWidth - 1][tempHeight] = 'R'; q.offer((tempWidth - 1) * height + tempHeight); } if (tempWidth + 1 < width) if (board[tempWidth + 1][tempHeight] == 'O') { board[tempWidth + 1][tempHeight] = 'R'; q.offer((tempWidth + 1) * height + tempHeight); } } } }

因而称为: Multi-End BFS

My test result:

perfect

图片 2Paste_Image.png

适用景况:一定是,在外围,向当中渗透的时候,能够用到这种BFSSurrounded
Regions 也是那般。

此次作业写了太久太久,久的本身一回都想放弃了。思路也变了大多次。让作者先停息下。然后能够总计下。刚和女对象打了个电话,小吵了一架,然后又相互明白。作者把自己对她的哀痛和他说了。笔者觉着恋爱就得那样,不要憋着,有哪些对对方不恬适的地点一定要讲出去。

然后Naive BFS 就不彰显了。此前几道标题,BFS都超时。。原本正是因为用了
naive bfs

好吧,大家继续。这道难点昨日就开头做了。然而未能做出来。又不想看答案,今天就随即做了。其实今天就早已找到拾贰分思路了,大概说,很左近的思路了。小编发觉,解决一道难题的思绪有很多,但短小消除的章程往往只有一个。而找到那些准确思路以前,须求思索好些个别样方法,然后最后的结尾,简化成了那个点子。只怕说,是模型。

dietpepsi 那篇小说写得挺不错的。分析了

那道标题就是寻觅被包围的某些。怎么找呢?小编刚开始飞速就找到了思路。能和外围的O连在一块的内部的O,就必将是未被包围的,其余的都以被包围的,可以被产生X。那么,最关键的标题是,以何种方式来寻找那一个和外界连着的O呢?这里笔者正是思量被局限了。或然说,笔者事先对BFS的认知还相当不够深。作者傻逼的按了下
提醒。见到说用
BFS。BFS在自己脑子里是怎样的东西啊?多个行列。然后从最左上角开头,遍历。然后设置贰个标记位数组来评释每一种节点是不是曾经被访问过。然后本身就在
是不是被访问 这些标题上
陷进去了。相对十分小概是简约的,访问过了一遍,就算已经被访谈了。 举例,
在此之前的因素是 X, 访谈的要素是O。 那么,这一个O
纵然未被访问过。同理可得,里面包车型大巴情形会比较复杂。为啥那样复杂,正是因为小编站的角度不对。正确的角度应该是,访谈那么些在外面的,
O 点。对各样点开展
BFS。并不是直接从左上角那一个点起来举办BFS。况且,这里还或许有一个要静心的位置。如若设置四个合併的系列来贮存在那个点,那么就能够促成
stackoverflow。
所以,必得在章程里新建队列。并且对每三个点,设置自个儿的连串。况兼,唯有O点能够被放进队列。那是一个自家此前主张没能想到的位置。具体地说,当你碰着X的时候,就能够告一段落了。纵然与X相邻的有O,那又何以呢?你们中间隔着X,说明你们未有连接在一块。要是你们实在是三番五次在一块的,那一定也是透过别的的水渠,连接在一块的,一定不是由此那些X链接在一块的。所以,一旦蒙受X,就止住,不用塞入队列。还应该有个小技能。将与边缘O连在一块的O全体制改正成哈弗,然后搜索进程中只要境遇XC60,那就认证已经访谈过了,该O已经在队列也许已经管理过了,就无需再被思考了,间接退出。所以,此前看的BFS总计未来估测计算很有含义。什么样的结点,满意哪些的情状,技术够走入队列。那是BFS须要思索的。而DFS供给怀念的是,DFS是树立在递归之上的,那么,几时,知足哪些条件时,该截至DFS,结束递归。

MultiEnd BFS,Naive BFS,DFS

LJ
第20题。前日重做,我写出了DFS的章程。当中会有个测量检验过不了,爆栈。oooooooooxxxxxxxxoooooooooooxxxxxxxxoooooooooxxxxxxxxoooooooooo….当遭逢那样一种情势的时候,假若DFS写的太随便太莽撞,就能够很轻巧二次递归把具有这一个O全部走下来,导致stack装不下这么多东西。然后直接爆栈。所以要多用几遍DFS,分摊压力。那么正是自家多少个月前说的,DFS该思考,满意哪些标准是,就停止递归。为了分摊压力,当满意,扫描的当前点,如果已经在边缘上了,那么就不扫描了。因为随意她是O/X,笔者都不能改动啊。那样就过了测量试验。别的,对bfs,现在的驾驭还是很荒唐。得多磨炼。代码如下:

reference:

public void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) return; boolean[][] isVisited = new boolean[board.length][board[0].length]; for (int i = 0; i < board[0].length; i++) if (!isVisited[0][i] && board[0][i] == 'O') transform(board, isVisited, 0, i); for (int i = 0; i < board[0].length; i++) if (!isVisited[board.length - 1][i] && board[board.length - 1][i] == 'O') transform(board, isVisited, board.length - 1, i); for (int i = 0; i < board.length; i++) if (!isVisited[i][0] && board[i][0] == 'O') transform(board, isVisited, i, 0); for (int i = 0; i < board.length; i++) if (!isVisited[i][board[0].length - 1] && board[i][board[0].length - 1] == 'O') transform(board, isVisited, i, board[0].length - 1); for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (board[i][j] == 'R') board[i][j] = 'O'; else if (board[i][j] == 'O') board[i][j] = 'X'; } } } private void transform(char[][] board, boolean[][] isVisited, int i, int j) { if (isVisited[i][j]) return; isVisited[i][j] = true; int row = board.length; int col = board[0].length; board[i][j] = 'R'; if (i - 1 >= 1 && !isVisited[i - 1][j] && board[i - 1][j] == 'O') transform(board, isVisited, i - 1, j); if (i + 1 < row - 1 && !isVisited[i + 1][j] && board[i + 1][j] == 'O') transform(board, isVisited, i + 1, j); if (j - 1 >= 1 && !isVisited[i][j - 1] && board[i][j - 1] == 'O') transform(board, isVisited, i, j - 1); if (j + 1 < col - 1 && !isVisited[i][j + 1] && board[i][j + 1] == 'O') transform(board, isVisited, i, j + 1); }

Anyway, Good luck, Richardo!

**总括:什么样的结点,满足哪些的情状,才方可进去队列。那是BFS须要思索的。而DFS必要考虑的是,DFS是创建在递归之上的,那么,几时,满意哪些标准时,该与世长辞DFS,结束递归。别的,
Java中
queue是贰个接口,interface,不能一贯用。供给采用三个数据结构。举个例子Queue<Integer>
q = new LinkedList<Integer>();**

Anyway, Good luck, Richardo!

那道难点仍旧采取了二种艺术来做。DFS, BFS, Union-Find

DFS:My code:

public class Solution { private int row = 0; private int col = 0; private boolean[][] mark; private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; private class Pair { int x; int y; Pair(int x, int y) { this.x = x; this.y = y; } } public void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) { return; } this.row = board.length; this.col = board[0].length; mark = new boolean[row][col]; for (int i = 0; i < row; i++) { if (board[i][0] == 'O' && !mark[i][0]) { visit(i, 0, board); } if (board[i][col - 1] == 'O' && !mark[i][col - 1]) { visit(i, col - 1, board); } } for (int i = 1; i < col - 1; i++) { if (board[0][i] == 'O' && !mark[0][i]) { visit(0, i, board); } if (board[row - 1][i] == 'O' && !mark[row - 1][i]) { visit(row - 1, i, board); } } for (int i = 1; i < row - 1; i++) { for (int j = 1; j < col - 1; j++) { if (board[i][j] == 'O' && !mark[i][j]) { board[i][j] = 'X'; } } } } private void visit(int i, int j, char[][] board) { mark[i][j] = true; for (int k = 0; k < 4; k++) { int x = i + dir[k][0]; int y = j + dir[k][1]; if (check && board[x][y] == 'O' && !mark[x][y]) { visit(x, y, board); } } } private boolean check(int i, int j) { if (i <= 0 || i >= row - 1 || j <= 0 || j >= col - 1) { return false; } return true; }}

和 number of islands 大致的。这里注意的是,一早先,最终七个例证平素stackoverflow可能就差不离。然后做了创新,check处, 假设定义的点在一侧,也不用再深切做dfs了。万一她正好成一种 zigzag条状的花样
往下链接,那么栈就能够爆。还不及,就老实做好团结这几个点上的事。别的的,由另外边上的点来做。

BFS:My code:

public class Solution { private int row = 0; private int col = 0; private boolean[][] mark; private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; private class Pair { int x; int y; Pair(int x, int y) { this.x = x; this.y = y; } } public void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) { return; } this.row = board.length; this.col = board[0].length; mark = new boolean[row][col]; for (int i = 0; i < row; i++) { if (board[i][0] == 'O' && !mark[i][0]) { visit(i, 0, board); } if (board[i][col - 1] == 'O' && !mark[i][col - 1]) { visit(i, col - 1, board); } } for (int i = 1; i < col - 1; i++) { if (board[0][i] == 'O' && !mark[0][i]) { visit(0, i, board); } if (board[row - 1][i] == 'O' && !mark[row - 1][i]) { visit(row - 1, i, board); } } for (int i = 1; i < row - 1; i++) { for (int j = 1; j < col - 1; j++) { if (board[i][j] == 'O' && !mark[i][j]) { board[i][j] = 'X'; } } } } private void visit(int i, int j, char[][] board) { Queue<Pair> q = new LinkedList<Pair>(); q.offer(new Pair; while (!q.isEmpty { Pair curr = q.poll(); int curr_x = curr.x; int curr_y = curr.y; mark[curr_x][curr_y] = true; for (int k = 0; k < 4; k++) { int x = curr_x + dir[k][0]; int y = curr_y + dir[k][1]; if (check && board[x][y] == 'O' && !mark[x][y]) { q.offer(new Pair; } } } } private boolean check(int i, int j) { if (i < 0 || i >= row || j < 0 || j >= col) { return false; } return true; }}

TLE, BFS 总是超时。

Union-Find

My code:

public class Solution { private int[] id; private int row = 0; private int col = 0; private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; public void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) { return; } this.row = board.length; this.col = board[0].length; id = new int[row * col]; for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'O' && (i == 0 || i == row - 1 || j == 0 || j == col - 1)) { id[i * col + j] = -1; } else { id[i * col + j] = i * col + j; } } } for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'O') { visit(i, j, board); } } } for (int i = 1; i < row - 1; i++) { for (int j = 1; j < col - 1; j++) { if (board[i][j] == 'O' && find(i * col + j) != -1) { board[i][j] = 'X'; } } } } private void visit(int i, int j, char[][] board) { for (int k = 0; k < 4; k++) { int curr_x = i + dir[k][0]; int curr_y = j + dir[k][1]; if (check(curr_x, curr_y) && board[curr_x][curr_y] == 'O') { union(i * col + j, curr_x * col + curr_y); } } } private void union(int x, int y) { int left = find; int right = find; if (left == right) { return; } else if (left == -1) { id[right] = -1; } else if (right == -1) { id[left] = -1; } else { id[left] = right; } } private int find { if (id[x] == -1 || id[x] == x) { return id[x]; } else { int ret = find; id[x] = ret; return ret; } } private boolean check(int i, int j) { if (i <= 0 || i >= row - 1 || j <= 0 || j >= col - 1) { return false; } return true; } }

和 number of islands
差不离。那多少个标题是画块,那些也大都的。只可是边上的 O
都属于同一块。所以作者略微改写了下 union find
方法。让那一个边上的点都同一时间继续于二个 virtual head: -1

然后自个儿再做同样的事。最后,作者遍历内层的多寡,假设是
O何况祖先是-1,那么一定和外围相连的。就flip

差不离就这么了。

明日抽取了两封拒信,激情糟糕很好。何况都以真人给笔者发拒信,实际不是系统据。看了背景还不是很强。1010data感到自身答得很好,没悟出依然拒了。二〇一五年真的不知道能走多少路程,能或不能够进个大公司。真的不领悟。继续刷题,继续投。不撤废,不放弃。然后等待机遇,抓住她。

是那样吗?是的。

明天才知道,BFS之所以那么那么轻便TLE,因为是Naive BFS

下一场针对于那类别型的题目,还可能有种更火速的BFS,Multi-End BFS

My code:

public class Solution { private int row = 0; private int col = 0; private int[][] dir = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; private class Pair { int x; int y; Pair(int x, int y) { this.x = x; this.y = y; } } public void solve(char[][] board) { if (board == null || board.length == 0 || board[0].length == 0) { return; } this.row = board.length; this.col = board[0].length; Queue<Pair> q = new LinkedList<Pair>(); for (int i = 0; i < row; i++) { if (board[i][0] == 'O') { q.offer(new Pair; } if (col > 1 && board[i][col - 1] == 'O') { q.offer(new Pair(i, col - 1)); } } for (int j = 1; j < col - 1; j++) { if (board[0][j] == 'O') { q.offer(new Pair; } if (row > 1 && board[row - 1][j] == 'O') { q.offer(new Pair(row - 1, j)); } } while (!q.isEmpty { Pair curr = q.poll(); int curr_x = curr.x; int curr_y = curr.y; board[curr_x][curr_y] = 'R'; for (int k = 0; k < 4; k++) { int x = curr_x + dir[k][0]; int y = curr_y + dir[k][1]; if (check && board[x][y] == 'O') { q.offer(new Pair; } } } for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (board[i][j] == 'R') { board[i][j] = 'O'; } else if (board[i][j] == 'O') { board[i][j] = 'X'; } } } } private boolean check(int i, int j) { if (i <= 0 || i >= row - 1 || j <= 0 || j >= col - 1) { return false; } return true; } }

Anyway, Good luck, Richardo! — 09/09/2016

标签:,

发表评论

电子邮件地址不会被公开。 必填项已用*标注

相关文章

网站地图xml地图