CodingNotes(01)

岛屿系列题目

695.岛屿的最大面积

我的思路

最简单的想法

1. 有一个函数输入是某个为1的点，然后去找这个点所在岛屿的面积。
2. 函数计算的方式是DFS，向四周遍历直到碰到0。
3. 遍历所有为1的点取最大值。

Code

第一版code

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ret = -1;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(grid[i][j]==1)
                {
                    int tmp =  islandSize(grid, i, j);
                    ret = (tmp>ret) ? tmp : ret;
                }

            }
        }

        return ret;
    }
    
    int islandSize(vector<vector<int>>& grid, int x, int y)
    {
        if(x < 0  || x >=grid.size() || y<0 || y>=grid[0].size()) return 0;
        if(grid[x][y] == 1)
            return 1 + islandSize(grid, x+1, y) + islandSize(grid, x-1, y)
                        + islandSize(grid, x, y+1) + islandSize(grid, x, y-1);
        else
            return 0;
    }
};

但是这里没有考虑到重复访问的问题，没有将已经计数过的陆地置为0，陷入无限递归而导致栈溢出。
修改后的code:

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ret = 0; // 从0开始，因为面积不能是负数
        for(int i = 0; i < grid.size(); i++) {
            for(int j = 0; j < grid[0].size(); j++) {
                if(grid[i][j] == 1) {
                    int tmp = islandSize(grid, i, j);
                    ret = std::max(tmp, ret);
                }
            }
        }
        return ret;
    }
    
    int islandSize(vector<vector<int>>& grid, int x, int y) {
        // 检查边界
        if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == 0) {
            return 0;
        }
        
        // 标记单元格为已访问
        grid[x][y] = 0;
        
        // 对相邻单元格进行递归调用
        return 1 + islandSize(grid, x + 1, y) + islandSize(grid, x - 1, y)
                   + islandSize(grid, x, y + 1) + islandSize(grid, x, y - 1);
    }
};

1905. 统计子岛屿

我的思路

1. 同上题 不过dfs函数的返回值改为bool类型，基本思想是边遍历边判断。

code

class Solution {
public:
    int countSubIslands(vector<vector<int>>& grid1, vector<vector<int>>& grid2) {
        int ret = 0;
        for(int i=0;i<grid2.size();i++)
            for(int j=0;j<grid2[0].size();j++)
            {
                if(grid2[i][j] == 1)
                {
                    auto tmp = isVaildIsland(grid1, grid2, i, j);
                    if(tmp) ret++;
                }
            }
        return ret;
    }

    bool isVaildIsland(vector<vector<int>>& grid1, vector<vector<int>>& grid2, int x, int y) {
        // 检查边界
        if(x < 0 || x >= grid2.size() || y < 0 || y >= grid2[0].size()) {
            return true;
        }
        // if(grid1[x][y] ^ grid2[x][y]) return false;

        if(grid2[x][y]==0) return true;
        // 标记单元格为已访问
        grid2[x][y] = 0;
        bool flag = true;
        if(grid1[x][y] == 0)
        {
            flag = false;
            //return false;
        }
    
        auto tmp1 = isVaildIsland(grid1, grid2, x + 1, y);
        auto tmp2 =  isVaildIsland(grid1, grid2, x - 1, y);
        auto tmp3 = isVaildIsland(grid1, grid2, x, y + 1) ;
        auto tmp4 =  isVaildIsland(grid1, grid2, x, y - 1);
  
        return  flag&&tmp1&&tmp2&&tmp3&&tmp4;
        // return  tmp1&&tmp2&&tmp3&&tmp4;
    }
};

一开始踩了几个坑

1. 首先是觉得grid1和grid2的不同时就返回false，显然当grid1==1 && grid2 == 0 时是不成立的
2. 其次是grid1 == 0 && grid2 == 1时不能直接返回false，否则递归会直接中止。

1020. 飞地的数量

我的思路

先把所有和边界联通的陆地都沉了，然后再去统计剩余的陆地数量。

code

class Solution{
public:
    int numEnclaves(vector<vector<int>>& grid) {
        int ret = 0;
        int row = grid.size();
        int col = grid[0].size();
        

        for(int i=0;i<col;i++)
        {
            if(grid[0][i]==1)
            {
                turn2sea(grid, 0, i);
            }
            if(grid[row-1][i]==1)
            {
                turn2sea(grid, row-1, i);
            }
        }
        for(int i=0;i<row;i++)
        {
            if(grid[i][0]==1)
            {
                turn2sea(grid, i, 0);
            }
            if(grid[i][col-1]==1)
            {
                turn2sea(grid, i, col-1);
            }
        }
       

        for(int i=0;i<row;i++)
            for(int j=0;j<col;j++)
            {
                if(grid[i][j]==1)
                {
                    ret++;
                }
            }
        return ret;
    }

    void turn2sea(vector<vector<int>>& grid, int x, int y)
    {
        if(x<0|| y<0|| x>=grid.size() || y>=grid[0].size() ||grid[x][y]==0 ) return;
        else
        {
            grid[x][y]=0;
            turn2sea(grid, x+1,y);
            turn2sea(grid, x-1,y);
            turn2sea(grid, x,y+1);
            turn2sea(grid, x,y-1);
            return ;
        }
    }

    
};