岛屿数量JAVA_LeetCode刷题 463. Island Perimeter 岛屿的周长 Java

亦凉 2022-11-10 05:38 173阅读 0赞

LeetCode刷题 463. Island Perimeter 岛屿的周长 Java

题目介绍

链接：https://leetcode-cn.com/problems/island-perimeter

给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。

网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围，但其中恰好有一个岛屿(或者说，一个或多个表示陆地的格子相连组成的岛屿)。

岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例图片如下：

![f80183785a0ae7a3872419b7f90c3a58.png][]

二维数组代替一个地图区域，0表示水域1表示小岛，所有水域都是联通集。

题目的要求主要就是实现对二维数组中上下左右相邻元素数值的判断，因为一旦相邻就会造成两者结合部分的消失。

解法一

从图中看到所有的小岛，或者说所有的相邻元素之间存在的状态只可能是四种情况。

单独的一个单位为1的小岛，那么他会贡献小岛总的长度为4的四个边长

![b7ff9720541ea65505305f13e5a5df1a.png][]

当前小岛只有一个边会与另外一个小岛相接，那么当前的小岛会贡献其余的三个边作为总的边长

![5209c7868e10583bcde60f1c346d7791.png][]

当前小岛有两个方向与其他小岛相接，会贡献其余的两边给整个小岛的周长

![b2842d78434250ea3661fff8fb26635f.png][]

当前小岛有三个方向与其他小岛相接，剩余的一条边会作为整个小岛的周长

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-T5XtSeeh-1604059924354)(三边相连.png)\]

![79446ebf7b0d0d61ab51fe7b8e8dffb6.png][]

当前小岛所有相邻方向全与别的小岛相接，成为一个内陆部分不贡献自己的任何边

![1cd07701e47bf2a007cccd69a0df0887.png][]

因此只要遍历数组中\*\*所有种类小岛的个数\*\*，根据各种类会贡献的周长就可以算出小岛周长总和。

class Solution \{

public int islandPerimeter(int\[\]\[\] grid) \{

int n = grid.length;

int m = grid\[0\].length;

int ans=0;

int \[\] dx=\{0,1,0,-1\};//位移数组

int \[\] dy=\{1,0,-1,0\};//分别访问当前元素下，右，上，左位置

for(int i=0;i

for(int j=0;j

if(grid\[i\]\[j\]==0)\{

continue;//不是小岛元素直接continue

\}//底下是小岛单位

int count=0//count记录当前小岛上下左右四个位置是否有相邻

for(int k=0;k

int nx = i+dx\[k\];

int ny = j+dy\[k\];

if(nx>=0&&nx=0&&ny

count++;

switch(count)\{//当前单位小岛相邻位置判断结束，根据count计算最终结果

case 0 :ans+=4;break;

case 1 :ans+=3;break;

case 2 :ans+=2;break;

case 3 :ans+=1;break;

case 4 :ans=ans;break;

return ans;

解法二

解法一存在的问题

思考上一种的解法可以发现，每次遍历的时候是会出现\*\*重复判断\*\*的。也就是在上一行当中已经判断过元素a与下一行的元素b相接，但是到下一行元素b时又会判断是否与上一行的元素a相接。

解决办法

从第一个元素开始判断是否是岛屿元素，是则直接默认贡献四边的长度count+=4，然后再向右和向下判断是否和其他元素相邻，若相邻一条边则消失两条边的周长count-=2(两条边重合并且都不再是岛屿的边缘)。等于遍历到底部元素时不会在继续判断上方已经判断过的元素。

class Solution \{

public int islandPerimeter(int\[\]\[\] grid) \{

int n = grid.length;

int m = grid\[0\].length;

int count=0;//记录总的小岛边数

int \[\] dx=\{0,1\};//位移数组，向右享下

int \[\] dy=\{1,0\};

for(int i=0;i

for(int j=0;j

if(grid\[i\]\[j\]==0)\{

continue;//不是小岛元素直接continue

count+=4;//时元素默认直接时单独的，再继续向右向下判断

for(int k=0;k

int nx = i+dx\[k\];

int ny = j+dy\[k\];

if(nx

count-=2;//相邻一条边，减去最终的两条边

return count;

一点思考

因为题目当前限定的是一个相连再一起的岛屿，不会存在类似与两个单独空心湖泊存在的情况。那么就一定确保了岛屿在四个面方向上\*\*对立面的个数总是相同的\*\*。比如说岛屿的左面有三个面就一定确保了右面也只有三个面，能否只通过检测两个对立面中的其中一个方向获取总的岛屿周长呢？大家一起交流讨论把。

LeetCode刷题 463. Island Perimeter 岛屿的周长 Java相关教程

LeetCode BST专题 538 把二叉搜索树转换成累加树 java

LeetCode BST专题 538 把二叉搜索树转换成累加树 java 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树(Greater Sum Tree)，使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 本题是BST，关于BST我们要明确一点，中

【力扣每日一题/30】463. 岛屿的周长

【力扣每日一题/30】463. 岛屿的周长 感谢茫茫人海中我们能够相遇，特别是这么优秀可爱的你还能来关注我，真的很感恩 俗话说：当你的才华和能力，不足以支撑你的梦想的时候，请静下心来学习。 希望优秀的你可以和我一起学习，一起努力，实现属于自己的梦想。

LeetCode-岛屿的周长

LeetCode-岛屿的周长 题目要求 原题链接 ：463. 岛屿的周长 给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地 0 表示水域。 网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围，但其中恰好有一个岛屿(或者说，一个或多个表示

LeetCode 376 摇摆序列

LeetCode 376 摇摆序列 分析 这道题是是个贪心的题目，如果把数组中的点在二位坐标中画出来，是一个折线，只需要计算拐点的次数就可以了， 需要注意的是代码利用了自动机的思想，比只写if else的代码可读性强 如果在面试中写出这样的代码，能体现出扎实的基本

leetcode刷题.530. 二叉搜索树的最小绝对差.每日打卡

leetcode刷题.530. 二叉搜索树的最小绝对差.每日打卡 class Solution \{public: int threeMin(int a, int b, int c) \{ return (a b) ? ((b c) ? c : b) : ((a c) ? c : a); \} int maxTreeNode(TreeNode \*root) \{ while(nullptr != root-right) root = root-rig

Leetcode 463. 岛屿的周长 (四个方向遍历找规律)

Leetcode 463. 岛屿的周长 (四个方向遍历找规律) 我们发现，岛屿的边的个数可以如下计算，如果从这一方格出发，遍历上下左右，如果周围出界了或者是水，那么这个周围就是一条边。因为题目保证了只有一个岛屿，所以可以不用DFS，直接对整个方格进行遍历就能解

LeetCode - 589.N叉树的前序遍历、后序遍历、层序遍历(递归、迭

LeetCode - 589.N叉树的前序遍历、后序遍历、层序遍历(递归、迭代) 589.N叉树的前序遍历 例如，给定一个 3叉树 : 题目： 给定一个 N 叉树，返回其节点值的前序遍历。 返回其前序遍历: \[1,3,5,6,2,4\]。 方法一 ：递归 class Solution \{ public ListInteger p

leetcode463:岛屿的周长

leetcode463:岛屿的周长 给定一个包含 0 和 1 的二维网格地图，其中 1 表示陆地， 0 表示水域。 网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围，但其中恰好有一个岛屿(或者说，一个或多个表示陆地的格子相连组成的岛屿)。 岛

[f80183785a0ae7a3872419b7f90c3a58.png]: /images/20221023/6afe7c90568441b9bab4282e14f38cb1.png
[b7ff9720541ea65505305f13e5a5df1a.png]: /images/20221023/4d9763831d434641aea8a2364531a22e.png
[5209c7868e10583bcde60f1c346d7791.png]: /images/20221023/cb5a121407eb4b6bb2281e4d355d3976.png
[b2842d78434250ea3661fff8fb26635f.png]: /images/20221023/0ae83a9a78ba4365a4fa86b96798c88f.png
[79446ebf7b0d0d61ab51fe7b8e8dffb6.png]: /images/20221023/da0f075001124297bb45b6e0b317dd12.png
[1cd07701e47bf2a007cccd69a0df0887.png]: /images/20221023/bff256d65bf04cb78db2dda8c33e2839.png