序言
虽然算法很难,但不应该就放弃。这是一个学习笔记,希望你们喜欢~
先自己尝试写,大概十几分钟仍然写不出来
看思路,再尝试跟着思路写
仍然写不出来,再看视频
b站up视频推荐:爱学习的饲养员
leetcode其他文章:
数组篇:
链表篇:
从小白开始刷算法 ListNode 链表篇 leetcode.203
从小白开始刷算法 ListNode 链表篇 leetcode.206
队列篇
从小白开始刷算法 ListNode 链表篇 leetcode.933
栈篇
从小白开始刷算法 Stack 栈篇 leetcode.496
哈希篇
从小白开始刷算法 Hash 哈希篇 leetcode.217
从小白开始刷算法 Hash 哈希篇 leetcode.705
树篇
从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144
从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94
从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94
堆篇
从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215
小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692
双指针篇
二分法篇
滑动窗口篇
递归篇
分治法篇
回溯法篇
dfs篇
bfs篇
并查集篇
dfs篇
难度:简单
题目:
463. 岛屿的周长
给定一个 row x col
的二维网格地图 grid
,其中:grid[i][j] = 1
表示陆地, grid[i][j] = 0
表示水域。
网格中的格子 水平和垂直 方向相连(对角线方向不相连)。整个网格被水完全包围,但其中恰好有一个岛屿(或者说,一个或多个表示陆地的格子相连组成的岛屿)。
岛屿中没有“湖”(“湖” 指水域在岛屿内部且不和岛屿周围的水相连)。格子是边长为 1 的正方形。网格为长方形,且宽度和高度均不超过 100 。计算这个岛屿的周长。
示例 1:
输入:grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出:16
解释:它的周长是上面图片中的 16 个黄色的边
示例 2:
输入:grid = [[1]]
输出:4
示例 3:
输入:grid = [[1,0]]
输出:4
题目来源:力扣(LeetCode)
dfs思路
能否写出:能写出。
时间:20分钟左右
思路:
首先,遍历整个二维网格,找到第一个岛屿的起始位置。
然后,以起始位置为起点,使用深度优先搜索遍历岛屿。遍历过程中,对于每个陆地格子,判断其上下左右四个方向是否是水域格子或者超出边界,计算周长的贡献。
遍历完当前岛屿后,继续寻找下一个未遍历的岛屿,并重复上述步骤,直到所有岛屿都被遍历完。 最终,累加每个岛屿的周长贡献,即可得到岛屿的总周长。
具体的实现步骤如下:
- 定义一个变量perimeter,用于累加每个岛屿的周长贡献。
- 遍历整个二维网格,找到第一个岛屿的起始位置,可以使用两层循环进行遍历。
- 以起始位置为起点,进行深度优先搜索(DFS)遍历岛屿。在DFS过程中,对于每个陆地格子,判断其上下左右四个方向是否是水域格子或者超出边界。
- 如果是水域格子或者超出边界,周长贡献加1。
- 如果是相邻的陆地格子,不进行任何操作。
- 如果是未遍历的陆地格子,进行递归的DFS遍历。
- 在DFS遍历完成后,将该岛屿的周长贡献加入到perimeter中。
- 继续寻找下一个未遍历的岛屿,重复步骤3和步骤4,直到所有岛屿都被遍历完。
- 返回perimeter作为岛屿的总周长。
这样,通过深度优先搜索遍历每个岛屿,并累加周长的贡献,即可得到岛屿的总周长。
// 仅是我的思路代码,leetcode上大神更厉害 class Solution { public int islandPerimeter(int[][] grid) { int perimeter = 0; int rows = grid.length; int cols = grid[0].length; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (grid[i][j] == 1) { //循环计算每一个格子的边数 perimeter += calculatePerimeter(grid, i, j); } } } return perimeter; } private int calculatePerimeter(int[][] grid, int row, int col) { int perimeter = 0; int rows = grid.length; int cols = grid[0].length; // 上方边界或上方没有相邻的陆地 if (row == 0 || grid[row - 1][col] == 0) { perimeter++; } // 下方边界或下方没有相邻的陆地 if (row == rows - 1 || grid[row + 1][col] == 0) { perimeter++; } // 左侧边界或左侧没有相邻的陆地 if (col == 0 || grid[row][col - 1] == 0) { perimeter++; } // 右侧边界或右侧没有相邻的陆地 if (col == cols - 1 || grid[row][col + 1] == 0) { perimeter++; } return perimeter; } }
时间复杂度:O(MN)
- 其中 M 是二维网格的行数,N 是二维网格的列数。因为我们需要遍历整个二维网格中的每个格子。
空间复杂度:O(1)
- 除了用于存储行数、列数和周长的变量外,算法没有使用额外的数据结构或数组,因此空间复杂度为常数级别。