岛屿的周长 (Island Perimeter)

题目：

总结

遍历方式： 1. 双层for循环， 2. while操作双下标 3. 递归统计的思路是：

求某个陆地所有有效边，所有陆地所有效边求和
公式： 4 * 陆地 - 2 * 交接边
求某一个边是否是有效边（边界，或者交接的是海），所有有效边相加简化代码小技巧：每个陆地，上下左右，实际是一个规律，如果拿代码硬写，代码行太多了，可以考虑用数组简化代码

    public static int[] dx = {-1, 0, 1, 0};
    public static int[] dy = {0, -1, 0, 1};
    int x = i + dx[e];
    int y = j + dx[e];

总结：遍历方法 + 配合任意算法，都可以求出结果，当然有些遍历方法配合某一个思路更完美

反省

遍历方式，3种我都想到，但是统计的思路，我只想到一种，求某个陆地所有有效边，所有陆地所有效边求和，递归的时候，没有找到最好的递归点

实现

自己实现

双层for循环配合，求某个陆地所有有效边，所有陆地所有效边求和，求出结果
代码

class Solution {
     public int islandPerimeter(int[][] grid) {
         int perimeter = 0;
         for (int i = 0; i < grid.length; i++) {
             for (int j = 0; j < grid[i].length; j++) {
                 int place = grid[i][j];
                 if (place == 0) {
                     continue;
                 }
                 int c = 4;
                 if (i - 1 >= 0) {
                     if (grid[i - 1][j] == 1) {
                         c--;
                     }
                 }
                 if (j - 1 >= 0) {
                     if (grid[i][j - 1] == 1) {
                         c--;
                     }
                 }
                 if (i + 1 < grid.length) {
                     if (grid[i + 1][j] == 1) {
                         c--;
                     }
                 }
                 if (j + 1 < grid[i].length) {
                     if (grid[i][j + 1] == 1) {
                         c--;
                     }
                 }
                 perimeter += c;
             }
         }
         return perimeter;
     }   
}

遍历配合公式

双层for配合遍历求和陆地数量，交接熟练给，利用公式求出结果
代码：

class Solution {
   public int islandPerimeter(int[][] grid) {
        int land = 0;
        int border = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    land++;
                    if (i + 1 < grid.length) {
                        if (grid[i + 1][j] == 1) {
                            border++;
                        }
                    }
                    if (j + 1 < grid[i].length) {
                        if (grid[i][j + 1] == 1) {
                            border++;
                        }
                    }
                }
            }
        }
        return 4 * land - 2 * border;
    }
}

遍历配合统计3

2层for配合有效边判断，求出所有有效边和
代码


class Solution {
   public int islandPerimeter(int[][] grid) {
        int n = grid.length, m = grid[0].length, perimeter = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int e = 0; e < dx.length; e++) {
                        int x = i + dx[e];
                        int y = j + dy[e];
                        if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == 0) {
                            perimeter++;
                        }
                    }
                }
            }
        }
        return perimeter;
    }
}

递归配合有效边求和

理论上，这个应该是最优，因为通过递归，规避很多非陆地遍历过程，但是实际运行结果却很差

class Solution {
    public int myOwnWayOfThinkingFour(int[][] grid) {
        int row = grid.length, column = grid[0].length;
        int sum = 0;
        for (int i = 0; i < row; row++) {
            for (int j = 0; j < column; j++) {
                if (grid[i][j] == 1) {
                    sum += dfs(grid, i, j, row, column);
                }
            }
        }
        return sum;
    }

    public int dfs(int[][] grid, int x, int y, int row, int column) {
        // 边界算一个边, 或者说外面不是陆地算一个边
        if (x < 0 || x >= row || y < 0 || y >= column || grid[x][y] == 0) {
            return 1;
        }
        if (grid[x][y] == 2) {
            return 0;
        }
        grid[x][y] = 2;
        int res = 0;
        for (int i = 0; i < dx.length; i++) {
            res += dfs(grid, x + dx[i], y + dy[i], row, column);
        }
        return res;
    }
}

foolishbird-cn / arithmetic

岛屿的周长 (Island Perimeter)

题目：

总结

反省

实现

自己实现

遍历配合公式

遍历配合统计3

递归配合有效边求和

简介

发行版

贡献者

近期动态

foolishbird-cn / arithmetic .gitee-modal { width: 500px !important; }

岛屿的周长 (Island Perimeter)

题目：

总结

反省

实现

自己实现

遍历配合公式

遍历配合统计3

递归配合有效边求和

简介

发行版

贡献者

近期动态

搜索帮助

foolishbird-cn / arithmetic