leetcode刷题指南数组和矩阵(打基础之LeetCode算法题第31日)
leetcode刷题指南数组和矩阵(打基础之LeetCode算法题第31日)所以我们可以遍历数组,查看那些方格的值是1,算出总的边数,同时查看值为1的方格是否紧挨着其他的方格,然后去掉那些紧挨着的边数。思路:对于一个独立的"岛屿"正方形方格,它是有4个边的,但是当它的上下左右紧挨着一个同样的"岛屿"正方形方格的时候,这两个方格紧挨着的两个边就不能算作它们围成的更大"岛屿"的周长,所以要去掉。给定一个包含 0 和 1 的二维网格地图,其中 1 表示陆地 0 表示水域。网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。岛屿中没有"湖"("湖" 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。
一直很纠结算法的文章应该怎么写。最后觉得还是从最简单的level开始写吧,一开始就弄些重量级的,什么人工智能,机器学习的算法,还要有大量的数学以及优化的知识,小白们估计会很郁闷,当然我也不一定能做出来对吧。
我计划每题给出两种语言的解决方案,一种静态语言,一种动态语言。
我选择C语言和python,本来考虑Java,但是篇幅有限,有兴趣的朋友自己试试
LeetCode 463. 岛屿周长(Island Perimeter)
问题描述:给定一个包含 0 和 1 的二维网格地图,其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。
岛屿中没有"湖"("湖" 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例:思路:对于一个独立的"岛屿"正方形方格,它是有4个边的,但是当它的上下左右紧挨着一个同样的"岛屿"正方形方格的时候,这两个方格紧挨着的两个边就不能算作它们围成的更大"岛屿"的周长,所以要去掉。
所以我们可以遍历数组,查看那些方格的值是1,算出总的边数,同时查看值为1的方格是否紧挨着其他的方格,然后去掉那些紧挨着的边数。
代码如下:
python的实现和C语言的实现大体类似。不再撰述。