从小白开始刷算法 dfs篇 leetcode.938

简介: 从小白开始刷算法 dfs篇 leetcode.938

序言

虽然算法很难,但不应该就放弃。这是一个学习笔记,希望你们喜欢~

先自己尝试写,大概十几分钟仍然写不出来

看思路,再尝试跟着思路写

仍然写不出来,再看视频

b站up视频推荐:爱学习的饲养员

leetcode其他文章:

数组篇:

从小白开始刷算法 数组篇 leetcode.485

从小白开始刷算法 数组篇 leetcode.283

从小白开始刷算法 数组篇 leetcode.27

链表篇:

从小白开始刷算法 ListNode 链表篇 leetcode.203

从小白开始刷算法 ListNode 链表篇 leetcode.206

队列篇

从小白开始刷算法 ListNode 链表篇 leetcode.933

栈篇

从小白开始刷算法 Stack 栈篇 leetcode.20

从小白开始刷算法 Stack 栈篇 leetcode.496

哈希篇

从小白开始刷算法 Hash 哈希篇 leetcode.217

从小白开始刷算法 Hash 哈希篇 leetcode.705

树篇

从小白开始刷算法 Tree 树篇 先序遍历 leetcode.144

从小白开始刷算法 Tree 树篇 中序遍历 leetcode.94

从小白开始刷算法 Tree 树篇 后序遍历 leetcode.94

堆篇

从小白开始刷算法 Heap 堆篇 最大堆排序 leetcode.215

小白开始刷算法 Heap 堆篇 最小堆排序 leetcode.692

双指针篇

从小白开始刷算法 对撞双指针 leetcode.881

从小白开始刷算法 快慢双指针篇 leetcode.141

二分法篇

从小白开始刷算法 二分法篇 leetcode.704

从小白开始刷算法 二分法篇 leetcode.35

从小白开始刷算法 二分法篇 leetcode.162

从小白开始刷算法 二分法篇 leetcode.74

滑动窗口篇

从小白开始刷算法 滑动窗口篇 leetcode.209

从小白开始刷算法 滑动窗口篇 leetcode.1456

递归篇

从小白开始刷算法 递归篇 leetcode.509

从小白开始刷算法 递归篇 leetcode.206

分治法篇

从小白开始刷算法 分治法篇 leetcode.169

从小白开始刷算法 分治法篇 leetcode.53

回溯法篇

从小白开始刷算法 回溯法篇 leetcode.22

从小白开始刷算法 回溯法篇 leetcode.78

dfs篇

从小白开始刷算法 dfs篇 leetcode.938

从小白开始刷算法 dfs篇 leetcode.200

bfs篇

从小白开始刷算法 bfs篇 leetcode.102

并查集篇

从小白开始刷算法 并查集篇 leetcode.200

[从小白开始刷算法 并查集篇 leetcode.547

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分钟左右

思路:

首先,遍历整个二维网格,找到第一个岛屿的起始位置。

然后,以起始位置为起点,使用深度优先搜索遍历岛屿。遍历过程中,对于每个陆地格子,判断其上下左右四个方向是否是水域格子或者超出边界,计算周长的贡献。

遍历完当前岛屿后,继续寻找下一个未遍历的岛屿,并重复上述步骤,直到所有岛屿都被遍历完。 最终,累加每个岛屿的周长贡献,即可得到岛屿的总周长。

具体的实现步骤如下:

  1. 定义一个变量perimeter,用于累加每个岛屿的周长贡献。
  2. 遍历整个二维网格,找到第一个岛屿的起始位置,可以使用两层循环进行遍历。
  3. 以起始位置为起点,进行深度优先搜索(DFS)遍历岛屿。在DFS过程中,对于每个陆地格子,判断其上下左右四个方向是否是水域格子或者超出边界。
  • 如果是水域格子或者超出边界,周长贡献加1。
  • 如果是相邻的陆地格子,不进行任何操作。
  • 如果是未遍历的陆地格子,进行递归的DFS遍历。
  1. 在DFS遍历完成后,将该岛屿的周长贡献加入到perimeter中。
  2. 继续寻找下一个未遍历的岛屿,重复步骤3和步骤4,直到所有岛屿都被遍历完。
  3. 返回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)

  • 除了用于存储行数、列数和周长的变量外,算法没有使用额外的数据结构或数组,因此空间复杂度为常数级别。
相关文章
|
1月前
|
算法 测试技术 定位技术
数据结构与算法——DFS(深度优先搜索)
数据结构与算法——DFS(深度优先搜索)
|
1月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
38 0
|
3月前
|
算法
DFS算法的实现
DFS算法的实现
61 3
|
14天前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
1月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
27 2
|
3月前
|
算法 Java
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
LeetCode经典算法题:矩阵中省份数量经典题目+三角形最大周长java多种解法详解
52 6
|
3月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
50 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:预测赢家+香槟塔java解法
LeetCode经典算法题:预测赢家+香槟塔java解法
61 1
|
3月前
|
存储 算法 Java
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
LeetCode经典算法题:二叉树遍历(递归遍历+迭代遍历+层序遍历)以及线索二叉树java详解
79 0
|
3月前
|
算法 Java
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
LeetCode初级算法题:子数组最大平均数+二叉树的最小深度+最长连续递增序列+柠檬水找零
43 0