所有的LeetCode题解索引，可以看这篇文章——【算法和数据结构】LeetCode题解。

一、题目

二、解法

  思路分析：直接利用公式法，遇到一对相邻的陆地，总周长就减去2。那么周长公式为：$C_{周长}=N_{岛屿数量}\times 4-N_{相邻陆地对数}\times 2$。因此本题只需要统计岛屿数量和相邻陆地对数即可。

  程序如下：

class Solution {
public:int islandPerimeter(vector<vector<int>>& grid) {int sum = 0;	// 陆地数量int cover = 0;	// 相邻数量for (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid[0].size(); j++) {if (grid[i][j] == 1) {sum++;// 仅需统计上边和左边相邻陆地即可，下边和右边是重复的。if (i - 1 >= 0 && grid[i - 1][j] == 1) cover++;if (j - 1 >= 0 && grid[i][j - 1] == 1) cover++;}}}return sum * 4 - cover * 2;}
};

复杂度分析：

• 时间复杂度：$O(m\times n)$，其中$m$和$n$分别是数组的行数和列数。
• 空间复杂度：$O(1)$。只需要常数空间存放若干变量。

三、完整代码

# include <iostream>
# include <vector>
using namespace std;class Solution {
public:int islandPerimeter(vector<vector<int>>& grid) {int sum = 0;	// 陆地数量int cover = 0;	// 相邻数量for (int i = 0; i < grid.size(); i++) {for (int j = 0; j < grid[0].size(); j++) {if (grid[i][j] == 1) {sum++;// 仅需统计上边和左边相邻陆地即可，下边和右边是重复的。if (i - 1 >= 0 && grid[i - 1][j] == 1) cover++;if (j - 1 >= 0 && grid[i][j - 1] == 1) cover++;}}}return sum * 4 - cover * 2;}
};int main() {vector<vector<int>> grid = { {0, 1, 0, 0}, {1, 1, 1, 0}, {0, 1, 0, 0}, {1, 1, 0, 0} };Solution s1;int result = s1.islandPerimeter(grid);cout << result << endl;system("pause");return 0;
}

end