本文主要是介绍【LeetCode】463. 岛屿的周长(Java),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
给定一个包含 0 和 1 的二维网格地图,其中 1 表示陆地 0 表示水域。
网格中的格子水平和垂直方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。
岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。
解法一
迭代,最容易想到的解法。
class Solution {public int islandPerimeter(int[][] grid) {// 迭代// 这道岛屿问题之所以是简单类型的题目,是因为题目已经把难度降低了很多了,如只有一个岛屿,并且岛屿中没有湖。int constexpr = 0;// 遍历数组for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {// 如果当前为陆地,判断前后左右是否为水域或者边界,如果是,周长加1if (grid[i][j] == 1) {// 判断陆地上边if (i == 0 || grid[i - 1][j] == 0) constexpr++;// 判断陆地下边if (i == grid.length - 1 || grid[i + 1][j] == 0) constexpr++;// 判断陆地左边if (j == 0 || grid[i][j - 1] == 0) constexpr++;// 判断陆地右边if (j == grid[i].length - 1 || grid[i][j + 1] == 0) constexpr++;}}}return constexpr;}
}
这道岛屿问题之所以是简单类型的题目,是因为题目已经把难度降低了很多了,如只有一个岛屿,并且岛屿中没有湖。
解法二
dfs,深度优先遍历。
class Solution {public int islandPerimeter(int[][] grid) {// dfsfor (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {// 因为只有一个岛屿,所以只要碰到陆地,即可返回结果if (grid[i][j] == 1) {return dfs(grid, i, j);}}}return 0;}private int dfs(int[][] grid, int c, int r) {// 判断当前是否越界,如果是,返回1(周长加1)if (c < 0 || c >= grid.length || r < 0 || r >= grid[c].length) {return 1;}// 判断是否为水域,如果是返回1(周长加1)if (grid[c][r] == 0) {return 1;}// 判断是否已走过,如果是返回0(已走过,不加)if (grid[c][r] == 2) {return 0;}// 把当前陆地1污染为2,代表已走过grid[c][r] = 2;// 返回前后左右的递归返回值的总和return dfs(grid, c - 1, r) + dfs(grid, c, r - 1) + dfs(grid, c + 1, r) + dfs(grid, c, r + 1);}
}
解法三
量子纠缠解法,由画家王铁男
大佬提供思路。
class Solution {public int islandPerimeter(int[][] grid) {// 量子纠缠解法,在北面有一条边,对应的南面也会有一条边,东西同理,才能形成闭环int constexpr = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {// 是陆地if (grid[i][j] == 1) {// 上一个不是陆地(和水域相接或边界),有一条边,那么下边也有一条边与其对应if (i == 0 || grid[i - 1][j] == 0) {// 因为上下都有一条边,所以是加二constexpr += 2;}if (j == 0 || grid[i][j - 1] == 0) {// 同理constexpr += 2;}}}}return constexpr;}
}
解法四
公式:岛屿周长 = 陆地数 * 4 - 陆地接壤边数 * 2,由笨猪爆破组
大佬提供思路。
class Solution {public int islandPerimeter(int[][] grid) {// 公式 岛屿周长 = 陆地数 * 4 - 陆地接壤边数 * 2int constexpr = 0;for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[i].length; j++) {// 是陆地,加4if (grid[i][j] == 1) {constexpr += 4;// 先判断是否当最下边,然后再判断下一个是否也是陆地,如果是既有一条接壤边,减2if (i < grid.length - 1 && grid[i + 1][j] == 1) {constexpr -= 2;}// 判断右边,同上(只判断两边,避免重复)if (j < grid[i].length - 1 && grid[i][j + 1] == 1) {constexpr -= 2;}}}}return constexpr;}
}
这篇关于【LeetCode】463. 岛屿的周长(Java)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!