LeetCode 827 Making A Large Island Java代码错误原因排查求助

代码问题排查 #

核心错误原因 #

重复使用未重置的visited数组导致面积统计遗漏

• 你在largestIsland方法开头仅初始化了一次visited数组，遍历每一个0并临时改为1计算岛屿面积时，全程复用同一个visited数组。第一次计算后所有访问过的1的位置都会被标记为true，后续计算其他位置的岛屿面积时，这些已经被标记的1不会被重复统计，最终得到的面积比实际值小。

对应你报错的测试用例[[1,1,0],[0,0,0], [1,1,0]]：当遍历到坐标(1,1)的0并改为1时，理论上可以连通上方2个1、下方2个1加上自己总共5的面积，但因为之前计算其他位置的面积时已经把(0,0)、(0,1)标记为已访问，本次统计时这两个位置不会被计入，最终得到错误的3。

逻辑修复方案 #

把visited数组的初始化放到每次计算面积之前即可，修改后代码如下：

class Solution {
    public int largestIsland(int[][] grid) {
        int n=grid.length;
        int max=0;
        boolean hasZero=false;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    grid[i][j]=1;
                    // 每次计算前新建空白的visited数组，避免之前的标记影响当前统计
                    boolean[][] visited = new boolean[n][n];
                    max=Math.max(max,area(grid,n,i,j,visited));  
                    grid[i][j]=0;
                    hasZero=true;
                }
            }
        }
        
        return hasZero?max:n*n;
    }
    
    private int area(int[][] grid, int n, int i, int j, boolean[][] visited){
        if(i<0 || i>n-1 || j>n-1 || j<0 || grid[i][j]==0 || visited[i][j])
            return 0;
        
        visited[i][j]=true;
        int a1 =  area(grid,n,i+1,j,visited);
        int a2 =  area(grid,n,i,j+1,visited);
        int a3 = area(grid,n,i-1,j,visited);
        int a4 =  area(grid,n,i,j-1,visited);
            
        return 1+a1+a2+a3+a4;
    }
}

注：修改后仅修复逻辑正确性，时间复杂度仍然为O(N^4)，仅适用于小数据量场景，大数据量测试用例会超时。

内容的提问来源于stack exchange，提问作者nanosoft