算法最优解 算法最优解
首页
目录
赞助
GitHub (opens new window)
首页
目录
赞助
GitHub (opens new window)
  • 数据结构基础

  • 数组

  • 位运算

  • 动态规划

  • 图

    • 克隆图
    • 课程表
    • 太平洋大西洋水流问题
    • 岛屿的数量
      • 题目描述
      • 知识回顾
      • 思路解析
      • C++代码
      • 复杂度分析
    • 最长连续序列
  • 区间

  • 链表

  • 矩阵

  • 字符串

  • 树

  • 堆

  • 逻辑思维

  • 目录
  • 图
华南溜达虎
2024-07-08
目录

岛屿的数量

题目链接: https://leetcode.cn/problems/number-of-islands/

# LeetCode 200.岛屿的数量

# 题目描述

给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。

岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外,你可以假设该网格的四条边均被水包围。

举个例子:

输入:grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出:3

# 知识回顾

广度优先搜索(BFS) 是一种图形搜索算法,它的基本思想是从一个顶点出发,先访问它的所有邻接顶点,然后再按照同样的方式访问这些邻接顶点的未访问邻接顶点,直到图中所有顶点都被访问。广度优先搜索算法通常使用队列来存储待访问的顶点,并使用一个数组或者集合来记录已访问的顶点。

# 思路解析

先明确怎样才能连成一个岛,水平方向或竖直方向的陆地(‘1’)相连,这样的陆地组成一个岛。如下图区域1和区域2属于不同的两个岛。

本题采用广度优先搜索来解,算法如下:

  1. 采用数组visit来保存grid中的坐标是否被访问过。nums来保存岛屿的数量。
  2. 对grid中所有未被访问过且grid[i][j] == 1的坐标(i, j)进行广搜并计数,++nums,每次搜索都能保证坐标所在的岛屿被遍历一遍。
  3. 返回nums。

广搜都是采用队列来实现的,实现广搜的关键是明确入队的条件,本题的入队条件是根据当前坐标遍历其上下左右四个新坐标,新坐标没有被访问过,而且落在grid中,对应的值为1就把新坐标压入队列。

# C++代码

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int nums = 0;
        int rows = grid.size();
        if (!rows) return nums;
        int cols = grid[0].size();
        vector<vector<bool>> visit(rows, vector<bool>(cols, false));
        //对所有没有被访问过且对应矩阵中的值为1的坐标进行广搜
        for (int row = 0; row < rows; ++row) {
            for(int col = 0; col < cols; ++col) 
                if (grid[row][col] == '1' && !visit[row][col]) {
                    bfs(grid, row, col, visit);
                    ++nums;
                }
        }
        return nums;
    }

    void bfs(vector<vector<char>>& grid, int row, int col, vector<vector<bool>>& visit) {

        queue<pair<int, int>> q;
        visit[row][col] = true;
        q.push({row, col});
        
        while (!q.empty()) {
            pair<int, int> temp = q.front();
            q.pop();
            //保存当前坐标的下、上、右、左四个方向
            vector<vector<int>> directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
            for (int i = 0; i < directions.size(); ++i) {
                int new_row = temp.first + directions[i][0];
                int new_col = temp.second + directions[i][1];
                //新坐标在grid中,并且新坐标对应的值为1,并且新坐标没有被访问过,就把新坐标压入队列并打上已访问标记
                if (new_row >= 0 && new_row < grid.size() && new_col >= 0 && new_col < grid[0].size() && grid[new_row][new_col] == '1' && !visit[new_row][new_col]) {
                    q.push({new_row, new_col});
                    visit[new_row][new_col] = true;
                }
            } 

        }

    }
};

# 复杂度分析

时间复杂度: O(n),n为网格中元素的总数量。

空间复杂度: O(n),n为网格中元素的总数量。

上次更新: 2024/07/08, 20:31:33
太平洋大西洋水流问题
最长连续序列

← 太平洋大西洋水流问题 最长连续序列→

Theme by Vdoing | Copyright © 2024-2024 华南溜达虎 | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式