星空网 > 软件开发 > Java

Leetcode: 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:11110110101100000000Answer: 1Example 2:11000110000010000011Answer: 3

DFS的Flood Fill方法,

使用额外Visited数组的做法:

 1 public class Solution { 2   public int numIslands(char[][] grid) { 3     if (grid==null || grid.length==0 || grid[0].length==0) return 0; 4     int count = 0; 5     boolean[][] visited = new boolean[grid.length][grid[0].length]; 6     for (int i=0; i<grid.length; i++) { 7       for (int j=0; j<grid[0].length; j++) { 8         if (grid[i][j] != '1') continue; 9         else {10           count++;11           floodFill(grid, i, j, visited);12         }13       }14     }15     return count;16   }17   18   public void floodFill(char[][] grid, int i, int j, boolean[][] visited) {19     if (i<0 || i>=grid.length || j<0 || j>=grid[0].length) return;20     if (visited[i][j]) return;21     if (grid[i][j] != '1') return;22     grid[i][j] = '2';23     floodFill(grid, i-1, j, visited);24     floodFill(grid, i+1, j, visited);25     floodFill(grid, i, j-1, visited);26     floodFill(grid, i, j+1, visited);27   }28 }

更节省空间的方法:不使用额外visited数组,但是用‘1’变成‘2’表示visited的方法

 1 public class Solution { 2   public int numIslands(char[][] grid) { 3     if (grid==null || grid.length==0 || grid[0].length==0) return 0; 4     int count = 0; 5     for (int i=0; i<grid.length; i++) { 6       for (int j=0; j<grid[0].length; j++) { 7         if (grid[i][j] != '1') continue; 8         else { 9           count++;10           floodFill(grid, i, j);11         }12       }13     }14     return count;15   }16   17   public void floodFill(char[][] grid, int i, int j) {18     if (i<0 || i>=grid.length || j<0 || j>=grid[0].length) return;19     if (grid[i][j] != '1') return; //either 0(water) or 2(visited)20     grid[i][j] = '2';21     floodFill(grid, i-1, j);22     floodFill(grid, i+1, j);23     floodFill(grid, i, j-1);24     floodFill(grid, i, j+1);25   }26 }

 




原标题:Leetcode: Number of Islands

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

旺季节日报名时段太短,如何解决备货难题?:https://www.ikjzd.com/articles/6304
Shopify携手ArcMEAD与全球大卖共话中国品牌出海新征途:https://www.ikjzd.com/articles/6306
这可能是史上最全的eBay运营指南了:https://www.ikjzd.com/articles/631
亚马逊旺季中如何保证账号运营安全策略:https://www.ikjzd.com/articles/632
亚马逊运营之Listing打造中需要了解的几个要素:https://www.ikjzd.com/articles/6328
wish全明星商户标识是什么?如何获得全明星商户标识?:https://www.ikjzd.com/articles/633
大福地快捷酒店预订 大福酒店怎么走:https://www.vstour.cn/a/365187.html
三亚有哪些酒店值得入住?:https://www.vstour.cn/a/366173.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流