​LeetCode刷题实战463:岛屿的周长

今天和大家聊的问题叫做 岛屿的周长,我们先来看题面:https://leetcode-cn.com/problems/island-perimeter/


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.

给定一个 row x col 的二维网格地图 grid ,其中:grid[i][j] = 1 表示陆地, grid[i][j] = 0 表示水域。网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例                             

​LeetCode刷题实战463:岛屿的周长

解题


解题思路:模拟题。理论上出现1的位置会贡献4的周长,但是周围的邻居如果是1会减小贡献值。找到数值为1的点。计算它上下左右(如果有)中1的个数num当前点对周长的贡献则是4-num。统计所有点的贡献值即可。

class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int sizex = grid.size();
        if (sizex == 0) return 0;
        int sizey = grid[0].size();
        if (sizey == 0) return 0;
        int res = 0;
        for (int i = 1; i <= sizex; i++) {
            for (int j = 1; j <= sizey; j++) {
                if (grid[i - 1][j - 1] == 1) {
                    res += 4;
                    if (i > 1 && grid[i - 2][j - 1] == 1) res--;
                    if (i < sizex&&grid[i][j - 1] == 1) res--;
                    if (j > 1 && grid[i - 1][j - 2] == 1) res--;
                    if (j < sizey&&grid[i - 1][j] == 1) res--;
                }
            }
        }
        return res;
    }
};

//下面关掉没有用的接口

static const auto _____ = []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return nullptr;
}();


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个
在看或者转发吧,你们的支持是我最大的动力 。


上一篇:​LeetCode刷题实战485:最大连续 1 的个数


下一篇:做报表的朋友偷偷告诉我月薪5w的秘密:让报表动起来