LeetCode695:Max Area of Island 解答

曾经终败给现在 2022-06-07 08:24 111阅读 0赞

写这道题用了我一个小时的时间，算是比较难的一道题目，解题的过程也很干净利落  
\#下面来看一下题目

> 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.)  
> 题目大意为：给定一个二维数组，它的全部元素为0和1，其中1代表陆地，0代表水域，并且假设数组的边缘是被水域包围的（意思是数组的边界之外的地方全是0）。陆地的面积是相连的1的个数，只有四面有相连的1的区域才能算是一整块陆地。要求你找到这个数组中最大的陆地面积。

> 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.  
> 图中加粗的那块就是最大的陆地面积，可以看到它的面积为6。  
> 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.

\#解题过程  
数组的题目通常都要遍历，但是经验告诉我最好的算法是尽量少的遍历，最好只遍历一次，在一遍遍历的过程中解决问题，像这样二维数组的题目，多次遍历就算了，就算CPU有耐心跑，我也没有耐心写。那怎么办呢，我们想一下寻找陆地的过程，对于每个非零的元素，寻找它的上下左右，那么对于每一个元素执行的操作是一样的，有了，那就用递归！递归的过程就是往当前元素的上下左右寻找非零的元素，遇到0返回，还有一点要注意的是遍历完当前非零元素记得将它置为零，避免重复计算。  
下面上我的代码：

class Solution {
        public int maxAreaOfIsland(int[][] grid) {
            int area=0;
            int temp=0;
            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid[0].length;j++){
                    if(grid[i][j]==1){
                        temp=findNeighbor(grid,j,i);
                        area=Math.max(area,temp);
                    }
                }
            }
            return area;
        }
        public int findNeighbor(int[][] map,int x,int y){
            int sum=1;
            if(map[y][x]==0){
                return 0;
            }else{
                map[y][x]=0;
            }
            if(y<=map.length-2)
                sum+=findNeighbor(map,x,y+1);
            if(x<=map[0].length-2)
                sum+=findNeighbor(map,x+1,y);
            if (x>=1)
                sum+=findNeighbor(map,x-1,y);
            if (y>=1)
                sum+=findNeighbor(map,x,y-1);
            return sum;
        }
    }

runtime为36ms  
\#更优的算法  
我在accept之后的页面看到一个runtime为32ms的算法，先将代码贴出来：

class Solution {
        public int maxAreaOfIsland(int[][] grid) {
            int i = 0, j = 0;
            int m = grid.length;
            int n = grid[0].length;
            int area = 0, max = 0;
            for (i = 0; i < m; i++) {
                for (j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        area = dfs(i, j, m, n, grid, 0);
                        max = Math.max(area, max);
                    }
                }
            }
            return max;
        }
        
        private int dfs(int i, int j, int m, int n, int[][] grid, int c_area) {
            if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0) {
                return c_area;
            }
            grid[i][j] = 0; //必须set为0以示访问过，否则无限循环，StackOverflowError
            c_area = c_area + 1;
            c_area = dfs(i + 1, j, m, n, grid, c_area);
            c_area = dfs(i - 1, j, m, n, grid, c_area);
            c_area = dfs(i, j + 1, m, n, grid, c_area);
            c_area = dfs(i, j - 1, m, n, grid, c_area);
            return c_area;
        }
    }

乍一看思路是相同的，但是我看到他的函数名dfs，这不是深度优先算法嘛，原谅我脱离图太久了，我一直以为tag为array的题目就只能用数组或者链表来解，然而我错了，用图也可以的。