LeetCode [695] Max Area of Island

 695. Max Area of Island

Medium

Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,1,1,0,1,0,0,0,0,0,0,0,0],
 [0,1,0,0,1,1,0,0,1,0,1,0,0],
 [0,1,0,0,1,1,0,0,1,1,1,0,0],
 [0,0,0,0,0,0,0,0,0,0,1,0,0],
 [0,0,0,0,0,0,0,1,1,1,0,0,0],
 [0,0,0,0,0,0,0,1,1,0,0,0,0]]

Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.

Example 2:

[[0,0,0,0,0,0,0,0]]

Given the above grid, return 0.

Note: The length of each dimension in the given grid does not exceed 50.

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

class Solution { int maxArea = 0; int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; int m, n; public int maxAreaOfIsland(int[][] grid) { m = grid.length; if(m==0) return 0; n = grid[0].length; if(n==0) return 0; for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ int[] area = new int[1]; if(grid[i][j]==1) dfs(grid, i, j, area); maxArea = Math.max(maxArea, area[0]); } } return maxArea; } void dfs(int[][] grid, int i0, int j0, int[] area){ grid[i0][j0] = 0; area[0]++; for(int[] d : dirs){ int i = i0+d[0], j = j0+d[1]; if(i>=0 && i<m && j>=0 && j<n && grid[i][j]==1){ dfs(grid, i, j, area); } } } }

YMSF

给一个0 1 array代表land and water,找最大的land locked area面积。 先找了内陆的entry，然后用了dfs把它们连成area。中间卡了巨久如何用union find 连，最后放弃。。然后时间就不够了。

union find是面试官要求的么？ 我感觉直接用dfs 把不同的相连的land标成一种颜色，最后再遍历一遍数size就行了。

楼主第二轮内陆的水的面积也需要算在最后返回的面积里面啊?感觉需要先identify出来跟边界连接的open water area

对的只包含小写字母，你说的字符变换顺序是对的。 union find是我自己想这么做，的确dfs就能写出来了。

顺便求米呀～

水的面积不算。只算周围没水的陆地面积，所以要先把这些陆地identify出来。

顺便求米呀～

加了～那第一题就是把字符串倒序吗？但是没有上下翻转啥的对吗？

明天面试今天疯狂抱佛脚555，感谢楼主回复！

要上下翻转，面试官会给你一个dictionary比如u变n,w变m之类，你可以假设你知道所有会互相变的case。哈哈不慌，面试加油!