LeetCode - 200. 岛屿数量

2024-05-11 17:38
文章标签 leetcode 数量 200 岛屿

本文主要是介绍LeetCode - 200. 岛屿数量,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

描述

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

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

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

 

示例 1:

输入:grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出:1
示例 2:

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

提示:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/number-of-islands/
 

求解

    class UnionFind {public:UnionFind(int n) : count(n) {parent.reserve(count + 1);for (int i = 0; i <= count; ++i) {parent.emplace_back(i);}rank.resize(count + 1, 1);  // 初始每个的层级均为1}bool isConnected(int p, int q) {return find(p) == find(q);}void unionElements(int p, int q) {int proot = find(p);int qroot = find(q);if (proot == qroot) {return;}if (rank[proot] < rank[qroot]) {parent[proot] = qroot;} else if (rank[proot] > rank[qroot]) {parent[qroot] = proot;} else {// rank[proot] == rank[qroot]parent[proot] = qroot;++rank[qroot];  // proot ”挂载“到qroot下面,本来两个层级一致,现在需要增加1}}// 获取连通分量int getCount() {int connectCount = 0;for (int i = 0; i < count; ++i) {if (parent[i] == i) {++connectCount;}}return connectCount;}private:int find(int p) {while (p != parent[p]) {parent[p] = parent[parent[p]]; // 路径压缩优化,请细品p = parent[p];}return p;}private:std::vector<int> parent;int count;std::vector<int> rank;};class Solution {public:// 方法一,深度优先遍历求连通分量int numIslands_1e(vector<vector<char>> &grid) {m = grid.size();n = grid[0].size();int count = 0;visited.assign(m, vector<bool>(n, false));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '0' || visited[i][j]) {continue;}++count;dfs(grid, i, j);}}return count;}// 方法一,广度优先遍历求连通分量int numIslands_2e(vector<vector<char>> &grid) {m = grid.size();n = grid[0].size();int count = 0;std::queue<std::pair<int, int>> q;visited.assign(m, vector<bool>(n, false));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == '0' || visited[i][j]) {continue;}++count;q.emplace(i, j);visited[i][j] = true;while (!q.empty()) {auto[r, c] = q.front();  // c++17新增结构化绑定特性q.pop();for (const auto &p  : directions) {int newR = r + p.first;int newC = c + p.second;if (newR < 0 || newR >= m || newC < 0 || newC >= n) {// 索引超范围,跳过当前循环continue;}// 访问未访问过且为0的节点if (!visited[newR][newC] && grid[newR][newC] == '1') {dfs(grid, newR, newC);}}}}}return count;}// 方法三,并查集求连通分量// 所有的0关联,1各自关联int numIslands(vector<vector<char>> &grid) {m = grid.size();n = grid[0].size();const int gridNum = m * n;// 所有0与该值关联, 该值一定大于所有格子的编号,格子编号[0...gridNum-1]UnionFind uf(gridNum + 1);for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {int id = i * n + j;if (grid[i][j] == '0') {uf.unionElements(id, gridNum);continue;}// grid[i][j] == '1'if (i < m - 1 && grid[i + 1][j] == '1') {// bottomuf.unionElements(id, id + n);}if (j < n - 1 && grid[i][j + 1] == '1') {// rightuf.unionElements(id, id + 1);}}}return uf.getCount() - 1;}private:vector<vector<bool>> visited;const vector<std::pair<int, int>> directions{{1,  0},{0,  1},{-1, 0},{0,  -1}};int m = 0;int n = 0;// 深度遍历网格void dfs(const vector<vector<char>> &grids, int r, int c) {visited[r][c] = true;for (const auto &p  : directions) {int newR = r + p.first;int newC = c + p.second;if (newR < 0 || newR >= m || newC < 0 || newC >= n) {// 索引超范围,跳过当前循环continue;}// 访问未访问过且为0的节点if (!visited[newR][newC] && grids[newR][newC] == '1') {dfs(grids, newR, newC);}}}};

 

这篇关于LeetCode - 200. 岛屿数量的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/980212

相关文章

MySQL精准控制Binlog日志数量的三种方案

《MySQL精准控制Binlog日志数量的三种方案》作为数据库管理员,你是否经常为服务器磁盘爆满而抓狂?Binlog就像数据库的“黑匣子”,默默记录着每一次数据变动,但若放任不管,几天内这些日志文件就... 目录 一招修改配置文件:永久生效的控制术1.定位my.cnf文件2.添加核心参数不重启热更新:高手应

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划