200. Number of Islands
题目：
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
11110
11010
11000
00000
Answer: 1
Example 2:
11000
11000
00100
00011
Answer: 3
链接： http://leetcode.com/problems/number-of-islands/
题解：
Find number of islands。无向图求connected components，用dfs + bfs就可以解决了。这里其实有dfs剪枝。空间复杂度主要是递归栈的大小。
Time Complexity - O(mn)， Space Complexity - O(mn)。
public class Solution {
public int numIslands(char[][] grid) { //undirected graph find connected components
if(grid == null || grid.length == 0)
return 0;
int count = 0;
for(int i = 0; i < grid.length; i++)
for(int j = 0; j < grid[0].length; j++)
if(grid[i][j] == '1') { // if isIsland, do dfs
dfs(grid, i, j);
count++;
}
return count;
}
private void dfs(char[][] grid, int i, int j) {
if(i > grid.length - 1 || j > grid[0].length - 1 || i < 0 || j < 0)
return;
if(grid[i][j] != '1')
return;
grid[i][j] = '0';
dfs(grid, i - 1, j); // Start BFS
dfs(grid, i, j - 1);
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
}
}
题外话： 11/14/2015，终于200题了！好高兴，又一个里程碑。下午休息休息，明天继续开始201，有时间的话也要回头总结题目，题型，加深思维能力， 主要是分析能力和思考速度。希望下个月能够完成300题，然后早日开始第二遍。 第二遍打算刷题，精炼代码的同时学习Python和JavaScript，也要了解一下Golang(原因是The Go Programming Language是柯尼汉大神写的，要买)。第二遍结束后就可以练一些小公司了。之间还要做一些项目，学习多线程，设计模式，系统设计，OO设计等等， Cousera的Crytography课和算法1课也要跟着上，时间真的很难够用。 继续加油吧！ 也要锻炼身体。
法国被恐怖分子袭击了，好可怜。现在自己工作的WTC也是恐怖分子的焦点之一，要注意安全。希望法国人民平安，希望其他国家努力惩戒恐怖分子。
二刷:
回头看看自己之前写的代码...BFS和DFS都搞不清楚 -____-!! 现在有进步了...
这道题可以用DFS, BFS和Union-Find来完成。BFS和Union-Find要把2D 转换为 1D来对待，否则的话还要另外建立private class Node。
Java:
DFS: 因为有剪枝，所以时间复杂度是O(mn)。 其实应该设立一个boolean[][] visited矩阵来保存访问过的节点，这样就不用更改原始数组了。否则我们每次dfs时要把当前节点置'0'，避免重复计算。
Time Complexity - O(mn)， Space Complexity - O(mn)。
public class Solution {
public int numIslands(char[][] grid) {
if (grid == null) return 0;
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
countIslands(grid, i, j);
count++;
}
}
}
return count;
}
private void countIslands(char[][] grid, int i, int j) {
if (grid[i][j] != '1') return;
grid[i][j] = '0';
if (i - 1 >= 0) countIslands(grid, i - 1, j);
if (i + 1 <= grid.length - 1) countIslands(grid, i + 1, j);
if (j - 1 >= 0) countIslands(grid, i, j - 1);
if (j + 1 <= grid[0].length - 1) countIslands(grid, i, j + 1);
}
}
BFS， 写得烂速度慢
public class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rowNum = grid.length, colNum = grid[0].length;
boolean[][] visited = new boolean[rowNum][colNum];
Queue<int[]> q = new LinkedList<>();
int count = 0;
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
if (!visited[i][j] && grid[i][j] == '1') {
q.offer(new int[] {i, j});
while (!q.isEmpty()) {
int[] location = q.poll();
int k = location[0], l = location[1];
if (visited[k][l]) continue;
visited[k][l] = true;
if (k - 1 >= 0 && grid[k - 1][l] == '1' && !visited[k - 1][l]) q.offer(new int[] {k - 1, l});
if (k + 1 <= rowNum - 1 && grid[k + 1][l] == '1' && !visited[k + 1][l]) q.offer(new int[] {k + 1, l});
if (l - 1 >= 0 && grid[k][l - 1] == '1' && !visited[k][l - 1]) q.offer(new int[] {k, l - 1});
if (l + 1 <= colNum - 1 && grid[k][l + 1] == '1' && !visited[k][l + 1]) q.offer(new int[] {k, l + 1});
}
count++;
}
}
}
return count;
}
}
BFS简化版， 速度还是慢。用Queue<int[]>的好处是我们不用每次都新建一个Node了。不过使用int[2]的空间开销和 Node(int x, int y)的开销都差不多。
- 在64位系统里， int[2] 是24 bytes + 4 * 2 bytes= 32 bytes
- Node {int x int y} 是16 bytes (object overhead) + 4 * 2 bytes = 24 bytes
- 比较一下还是新建Node比较划算。假如有Reference field的话那也是8 bytes.
public class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int rowNum = grid.length, colNum = grid[0].length;
Queue<int[]> q = new LinkedList<>();
int count = 0;
for (int i = 0; i < rowNum; i++) {
for (int j = 0; j < colNum; j++) {
if (grid[i][j] == '1') {
q.offer(new int[] {i, j});
while (!q.isEmpty()) {
int[] location = q.poll();
int k = location[0], l = location[1];
if (grid[k][l] != '1') continue;
grid[k][l] = 0;
if (k - 1 >= 0) q.offer(new int[] {k - 1, l});
if (k + 1 <= rowNum - 1) q.offer(new int[] {k + 1, l});
if (l - 1 >= 0) q.offer(new int[] {k, l - 1});
if (l + 1 <= colNum - 1) q.offer(new int[] {k, l + 1});
}
count++;
}
}
}
return count;
}
}
使用Union-Find速度可能会更慢一些
四刷:
class Solution {
int[][] directions = new int[][] {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int count = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
private void dfs (char[][] grid, int i, int j) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] != '1') return;
grid[i][j] = '0';
for (int[] direction : directions)
dfs(grid, i + direction[0], j + direction[1]);
}
}
Reference:
https://leetcode.com/discuss/31014/java-undirected-graph-connected-components
https://leetcode.com/discuss/41053/java-dfs-and-bfs-solution
https://leetcode.com/discuss/79537/java-union-find-solution
最新文章
- http请求相关
- dpm-release3.1在windows下的配置
- CentOS找回root密码
- ahjesus SSHkey登陆linux服务器，无需密码，ubuntu
- HDOj 1010 DFS优化
- Ultra Pull To Refresh下拉刷新
- spring源码学习之【准备】cglib动态代理例子
- JDBC getMetaData将结果集组装到List
- java解析XML几种方式
- 非web项目中使用XDT的实例(续)
- 执行gem install dryrun错误
- Java SE ——TCP协议网络编程（三）
- ST-3- Installing and Testing IUnit, Hamcrest and Eclemma
- KingView 6.53漏洞学习研究
- Python Skelve 库
- 201771010126 王燕《面向对象程序设计（Java）》第十六周学习总结
- POE 供电
- Laravel-mix 中文文档
- Linux kafka 单机安装
- Inside NGINX: How We Designed for Performance & Scale