MaxAreaOfIsland [source code]

public class MaxAreaOfIsland {
static
/******************************************************************************/
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        if (m == 0 || n == 0)
            return 0;
        boolean[][] visited = new boolean[m][n];
        int maxArea = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] == 1)
                    maxArea = Math.max (maxArea, dfs (i, j, grid, visited));
            }
        }
        return maxArea;
    }

    int dfs (int x, int y, int[][] grid, boolean[][] visited) {
        // Must check VISITED: (x,y) could be some point still on calling stack;
        if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length || grid[x][y] == 0 || visited[x][y])
            return 0;
        // Has to flag VISITED before recursion
        visited[x][y] = true;
        return 1 + dfs (x - 1, y, grid, visited) + dfs (x + 1, y, grid, visited) + dfs (x, y - 1, grid, visited) + dfs (x, y + 1, grid, visited);
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MaxAreaOfIsland.Solution tester = new MaxAreaOfIsland.Solution();
        int[][][] inputs = {
            {{1,1,0,0,0},{1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,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}},
             {{0,0,0,0,0,0,0,0}},
        };
        int[] answers = {
            4,
            6,
            0,
        };
        for (int i = 0; i < inputs.length; i++) {
            int[][] grid = inputs[i];
            int ans = answers[i];
            System.out.println (Printer.separator ());
            int output = tester.maxAreaOfIsland (grid);
            System.out.printf ("%s -> %s, expected: %d\n",
                Matrix.printMatrix (grid), Printer.wrapColor (output, output == ans ? "green" : "red"), ans
            );
        }
    }
}

大概扫了一眼题目, 好像不是特别复杂, 一个DFS应该可以搞定;

这个题目可以说是非常简单了, 不过最后花的时间还是超了, 很丢人; 最后的速度是40ms (50%), 一般性; 不过这题其实很多时间花在写脚本上面了; 另外, 注意我自己写的两个comment, 用DFS解connectivity问题其实我还是第一次, 所以有些细节还是要注意;

critical comment

我鼓励自己以后多写这样的comment, 来提醒自己一些关键性的细节; 真正面试的时候很多时候就是回忆这些你之前已经写过了的算法, 或者说题型, 而最后决定你写出来的成功与否的, 很多时候就是这种代码上的小细节, 比如不同操作之间的顺序关系;

另外, 这题注意一个小问题, 就是这种类似flooding的DFS, 你肯定要记得bound的判断; 我这里的做法是加在了leaf位置来判断, 当然, 也可以加在pre-leaf的位置来完成, 这题本身比较简单所以具体来说差别不是很大; 但是这里加在leaf位置判断代码稍微精简了一些; 如果非要加在pre-leaf的位置, 可以用三目运算符来精简代码;

editorial1:

class Solution {  
    int[][] grid;  
    boolean[][] seen;  

    public int area(int r, int c) {  
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length ||  
                seen[r][c] || grid[r][c] == 0)  
            return 0;  
        seen[r][c] = true;  
        return (1 + area(r+1, c) + area(r-1, c)  
                  + area(r, c-1) + area(r, c+1));  
    }  

    public int maxAreaOfIsland(int[][] grid) {  
        this.grid = grid;  
        seen = new boolean[grid.length][grid[0].length];  
        int ans = 0;  
        for (int r = 0; r < grid.length; r++) {  
            for (int c = 0; c < grid[0].length; c++) {  
                ans = Math.max(ans, area(r, c));  
            }  
        }  
        return ans;  
    }  
}

这个跟我自己的写法几乎是如出一辙的;

第二个做法就是用iterative来写:

class Solution {  
    public int maxAreaOfIsland(int[][] grid) {  
        boolean[][] seen = new boolean[grid.length][grid[0].length];  
        int[] dr = new int[]{1, -1, 0, 0};  
        int[] dc = new int[]{0, 0, 1, -1};  

        int ans = 0;  
        for (int r0 = 0; r0 < grid.length; r0++) {  
            for (int c0 = 0; c0 < grid[0].length; c0++) {  
                if (grid[r0][c0] == 1 && !seen[r0][c0]) {  
                    int shape = 0;  
                    Stack<int[]> stack = new Stack();  
                    stack.push(new int[]{r0, c0});  
                    seen[r0][c0] = true;  
                    while (!stack.empty()) {  
                        int[] node = stack.pop();  
                        int r = node[0], c = node[1];  
                        shape++;  
                        for (int k = 0; k < 4; k++) {  
                            int nr = r + dr[k];  
                            int nc = c + dc[k];  
                            if (0 <= nr && nr < grid.length &&  
                                    0 <= nc && nc < grid[0].length &&  
                                    grid[nr][nc] == 1 && !seen[nr][nc]) {  
                                stack.push(new int[]{nr, nc});  
                                seen[nr][nc] = true;  
                            }  
                        }  
                    }  
                    ans = Math.max(ans, shape);  
                }  
            }  
        }  
        return ans;  
    }  
}

比较无聊的; 当然实际面试的时候还是有可能考到的; 当我LeetCode一周目刷完之后, 要专门花时间重点照顾一下iterative dfs这个问题, 一定要能够做到滚瓜烂熟, 毕竟这个几乎可以作为任何一个需要recursion的题目的Follow-Up;

至于这题这个代码, 暂时就懒得看了;

评论里面有人提到, 如果immutability不需要保证的话, 不需要seen; 这个实际上也是一个小的trivial优化, 其实就是inplace flag技巧而已;

这个是discussion里面一个不使用seen的例子:

@Vincent-Cai said in [Java/C++] Straightforward dfs solution:

The idea is to count the area of each island using dfs. During the dfs, we set the value of each point in the island to 0. The time complexity is O(mn).

Java version:

    public int maxAreaOfIsland(int[][] grid) {  
        int max_area = 0;  
        for(int i = 0; i < grid.length; i++)  
            for(int j = 0; j < grid[0].length; j++)  
                if(grid[i][j] == 1)max_area = Math.max(max_area, AreaOfIsland(grid, i, j));  
        return max_area;  
    }  

    public int AreaOfIsland(int[][] grid, int i, int j){  
        if( i >= 0 && i < grid.length && j >= 0 && j < grid[0].length && grid[i][j] == 1){  
            grid[i][j] = 0;  
            return 1 + AreaOfIsland(grid, i+1, j) + AreaOfIsland(grid, i-1, j) + AreaOfIsland(grid, i, j-1) + AreaOfIsland(grid, i, j+1);  
        }  
        return 0;  
    }

这里这个InPlace flag实际上的做法跟我想象的有点区别, 我以为是改成比如-1这样的东西, 不过看来并没有必要, 直接改成0就行了; 这两种实现方式在这一题实际上没有区别, 但是在有些题目里面, 改成0这个方式可能有点优势, 这个有点类似之前Moore voting的时候的one-time count一样的技巧; 脑子里有个印象就好;

另外, 如果别人问你空间复杂度:

@FlorenceMachine said in [Java/C++] Straightforward dfs solution:

Worst-case recursion depth will be O(mn), where m is the width of the grid and n is the height, correct?

So space complexity will be O(mn)?

不要直接就说是O(1), Stack的空间也要考虑上;

这个是一个更贱简练的写法:

class Solution {  
    public int maxAreaOfIsland(int[][] grid) {  
        int m = grid.length, n = grid[0].length, maxarea = 0;  
        for (int i = 0; i < m; i++)  
            for (int j = 0; j < n; j++)  
                maxarea = Math.max(maxarea, dfs(i, j, grid));  
        return maxarea;  
    }  

    private int dfs(int i, int j, int[][] grid) {  
        return (i < 0 || grid.length <= i || j < 0 || grid[0].length <= j || grid[i][j] <= 0) ? 0  
            : grid[i][j]-- + dfs(i, j+1, grid) + dfs(i+1, j, grid) + dfs(i, j-1, grid) + dfs(i-1, j, grid);  
    }  
}

discussion基本就没有什么其他印象深刻的解法了; submission里面比较领先的解法好像多数也是一些比较trivial的差别;

Problem Description

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.

Difficulty:Easy
Total Accepted:15.4K
Total Submissions:29.3K
Contributor:chiragbm
Companies
intuit
Related Topics
arraydepth-first search
Similar Questions
Number of IslandsIsland Perimeter

LC695 MaxAreaOfIsland

MaxAreaOfIsland [source code]

critical comment

Problem Description

results matching ""

No results matching ""