leetcode.200 島嶼數量

這篇題解寫得非常好，值得反複看 https://leetcode-cn.com/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/

思路一：dfs深度周遊

代碼如下：

答題模闆

class Solution {
    public int numIslands(char[][] grid) {
        int result=0;
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]=='1')
                {
                    dfs(grid,i,j);
                    //當傳回時，所有相連的島嶼“面積” '1'都被填充'2';
                    result+=1;
                }
            }
        }
        return result;
    }
    private void dfs(char[][] grid,int row,int column)
    {
        //越界
        if(row<0 || column<0 || row>=grid.length || column>=grid[0].length)
        return;
        //不是島嶼
        if(grid[row][column]!='1')
        return;
        grid[row][column]='2';
        //周遊島嶼的上下左右節點
        dfs(grid,row+1,column);
        dfs(grid,row-1,column);
        dfs(grid,row,column+1);
        dfs(grid,row,column-1);     
    }
}
           

這道題屬于dfs+周遊，并且深度為上下左右，周遊所有節點

為什麼不是下和右呢？之前的都周遊過了，如果湖是工字島，那麼工字左下角無法作為一個島嶼的一部分，而是變成兩個島嶼

原題解還講了為什麼置2不置0的其它細節

第二次寫5分鐘

思路二：bfs廣度優先(借助隊列)

主循環和dfs一緻，一樣需要周遊每個節點，不同的是處理方式，dfs是每次不斷的往下深入直到碰見“0”，bfs是每次周遊每個節點的“周圍”，while控制

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null||grid[0].length==0)
        return 0;
        int result=0;
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]=='1')
                {
                bfs(grid,i,j);
                result++;
                }
            }
        }
        return result;
    }
    private void bfs(char[][] grid,int row,int col)
    {
    Queue<int[]> queue=new LinkedList<>();
    queue.add(new int[]{row,col});
    while(!queue.isEmpty())//外循環控制“下一圈”
    {
        int len=queue.size();
        while(len>0)//内循環控制“這一圈”
        {
            int[] temp=queue.poll();
            row=temp[0];
            col=temp[1];
//越界判斷，以及現節點是否是島嶼的一部分，是才将其周圍節點放入隊列
            if(row>=0 && col>=0 && row<grid.length && col<grid[0].length && grid[row][col]=='1')
            {
                grid[row][col]='2';
                queue.add(new int[]{row+1,col});
                queue.add(new int[]{row-1,col});
                queue.add(new int[]{row,col+1});
                queue.add(new int[]{row,col-1});
            }
            len--;
        }
       
    }
    }
}
           

上面這個雙重while是bfs，下面這個寫法更像周遊

class Solution {
    public int numIslands(char[][] grid) {
        if(grid==null||grid[0].length==0)
        return 0;
        int result=0;
        for(int i=0;i<grid.length;i++)
        {
            for(int j=0;j<grid[0].length;j++)
            {
                if(grid[i][j]=='1')
                {
                bfs(grid,i,j);
                result++;
                }
            }
        }
        return result;
    }
    private void bfs(char[][] grid,int row,int col)
    {
    Queue<int[]> queue=new LinkedList<>();
    queue.add(new int[]{row,col});
    while(!queue.isEmpty())
    {
        int[] temp=queue.poll();
        row=temp[0];
        col=temp[1];
        if(row>=0 && col>=0 && row<grid.length && col<grid[0].length && grid[row][col]=='1')
        {
            grid[row][col]='2';
            queue.add(new int[]{row+1,col});
            queue.add(new int[]{row-1,col});
            queue.add(new int[]{row,col+1});
            queue.add(new int[]{row,col-1});
        }
    }
    }
}
           

時間複雜度  O（m*n）

空間複雜度  O（m>n?m:n）對角線     隊列長度

第二次寫，bfs要注意細節，以及隊列存的是坐标

第三次寫，bfs  節點周遊，借助隊列，"下一圈"什麼時候入隊，判斷節點是否越界,有一些細節問題