Leetcode日记—463.island perimeter

发布于 2020-10-30  111 次阅读


碎碎念:学校已经连续两天2G网了,我要死了。校园网,给点作用啊校园网。。

题目如下:

You are given row x col grid representing a map where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water.

Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).

The island doesn't have "lakes", meaning the water inside isn't connected to the water around the island. One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

Example 1:

Input: grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
Output: 16
Explanation: The perimeter is the 16 yellow stripes in the image above.

Example 2:

Input: grid = [[1]]
Output: 4

Example 3:

Input: grid = [[1,0]]
Output: 4

思路

方法一:(加法)

可以知道,当一条边的旁边是边界外的水域,或者是旁边不为陆地(值为0)则当前边可算入答案边数。

因此我们遍历每个陆地点,得出结果即可。

细节

这里有个细节就是边界外水域会出现index not in array (忘记具体叫啥)的error。

我们这里使用Java中if语句的特点,若if语句为或的关系,即使用了“||”的时候,会进行一次判断,若前面的判断为真则不会执行后面的布尔判断。那么,我们可以先用index的范围判断是否为边界水域,若不为边界水域再判断是否为陆地即可。

代码如下:

	class Solution {
    public int islandPerimeter(int[][] grid) {
        int res=0;
        for(int i =0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]==1){
                    if(j-1<0||grid[i][j-1]==0)
                        ++res;
                    if(j+1>grid[0].length-1||grid[i][j+1]==0)
                        ++res;
                    if(i-1<0||grid[i-1][j]==0)
                        ++res;
                    if(i+1>grid.length-1||grid[i+1][j]==0)
                        ++res;
                }
            }
        }
        return res;
    }
}

方法二:减法

不考虑周围的情况下,每个陆地的边数贡献值为4,若其有一个相邻陆地,则两块陆地各损失1点贡献值。

那么:res=4*land个数—2*相邻边个数。

代码如下:

class Solution {

    public int islandPerimeter(int[][] grid) {
        // 举例推导出公式 res = 4 * 岛屿格子数量 - 2 * 岛屿格子之间的相邻边
        int m = 0, n= 0;
        if(grid == null || (m = grid.length) == 0 || (n = grid[0].length) == 0) return 0;
        
        int count = 0; // 岛屿格子数量
        int edge = 0; // 岛屿格子之间的相邻边
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(grid[i][j] == 0) continue;
                count++;
                             
                if(j+1 < n && grid[i][j+1] == 1)    edge++; // 判断右边是不是 陆地格子
          
                if(i+1 < m && grid[i+1][j] == 1)    edge++; // 判断下面是不是 陆地格子
            }
        }

        return 4 * count - 2 * edge;
    }
}

你好哇!欢迎来到雷公马碎碎念的地方:)