C++实现LeetCode(200.岛屿的数量)

2024-08-01 00:17:25

[LeetCode] 200. Number of Islands 岛屿的数量

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

这道求岛屿数量的题的本质是求矩阵中连续区域的个数，很容易想到需要用深度优先搜索 DFS 来解，我们需要建立一个 visited 数组用来记录某个位置是否被访问过，对于一个为 ‘1' 且未被访问过的位置，递归进入其上下左右位置上为 ‘1' 的数，将其 visited 对应值赋为 true，继续进入其所有相连的邻位置，这样可以将这个连通区域所有的数找出来，并将其对应的 visited 中的值赋 true，找完相邻区域后，将结果 res 自增1，然后再继续找下一个为 ‘1' 且未被访问过的位置，以此类推直至遍历完整个原数组即可得到最终结果，代码如下：

解法一：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                helper(grid, visited, i, j);
                ++res;
            }
        }
        return res;
    }
    void helper(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] == '0' || visited[x][y]) return;
        visited[x][y] = true;
        helper(grid, visited, x - 1, y);
        helper(grid, visited, x + 1, y);
        helper(grid, visited, x, y - 1);
        helper(grid, visited, x, y + 1);
    }
};

当然，这种类似迷宫遍历的题目 DFS 和 BFS 两对好基友肯定是形影不离的，那么 BFS 搞起。其实也很简单，就是在遍历到 ‘1' 的时候，且该位置没有被访问过，那么就调用一个 BFS 即可，借助队列 queue 来实现，现将当前位置加入队列，然后进行 while 循环，将队首元素提取出来，并遍历其周围四个位置，若没有越界的话，就将 visited 中该邻居位置标记为 true，并将其加入队列中等待下次遍历即可，参见代码如下：

解法二：

class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        if (grid.empty() || grid[0].empty()) return 0;
        int m = grid.size(), n = grid[0].size(), res = 0;
        vector<vector<bool>> visited(m, vector<bool>(n));
        vector<int> dirX{-1, 0, 1, 0}, dirY{0, 1, 0, -1};
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0' || visited[i][j]) continue;
                ++res;
                queue<int> q{{i * n + j}};
                while (!q.empty()) {
                    int t = q.front(); q.pop();
                    for (int k = 0; k < 4; ++k) {
                        int x = t / n + dirX[k], y = t % n + dirY[k];
                        if (x < 0 || x >= m || y < 0 || y >= n || grid[x][y] == '0' || visited[x][y]) continue;
                        visited[x][y] = true;
                        q.push(x * n + y);
                    }
                }
            }
        }
        return res;
    }
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/200

类似题目：

Number of Islands II

Surrounded Regions

Walls and Gates

Number of Connected Components in an Undirected Graph

Number of Distinct Islands

Max Area of Island

参考资料：

https://leetcode.com/problems/number-of-islands/

https://leetcode.com/problems/number-of-islands/discuss/56589/C%2B%2B-BFSDFS

https://leetcode.com/problems/number-of-islands/discuss/56359/Very-concise-Java-AC-solution

到此这篇关于C++实现LeetCode(200.岛屿的数量)的文章就介绍到这了,更多相关C++实现岛屿的数量内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

C++实现LeetCode(122.买股票的最佳时间之二)

[LeetCode] 122.Best Time to Buy and Sell Stock II 买股票的最佳时间之二 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie
C++实现LeetCode(130.包围区域)

[LeetCode] 130. Surrounded Regions 包围区域 Given a 2D board containing 'X' and 'O'(the letter O), capture all regions surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region. Example: X X X X X O O X X X O X X O
C++实现LeetCode(126.词语阶梯之二)

[LeetCode] 126. Word Ladder II 词语阶梯之二 Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that: Only one letter can be changed at a time Each transformed
C++实现LeetCode(123.买股票的最佳时间之三)

[LeetCode] 123.Best Time to Buy and Sell Stock III 买股票的最佳时间之三 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find the maximum profit. You may complete at most two transactions. Note: You
C++实现LeetCode(128.求最长连续序列)

[LeetCode] 128.Longest Consecutive Sequence 求最长连续序列 Given an unsorted array of integers, find the length of the longest consecutive elements sequence. Your algorithm should run in O(n) complexity. Example: Input: [100, 4, 200, 1, 3, 2] Output: 4 Expl
C++实现LeetCode(124.求二叉树的最大路径和)

[LeetCode] 124. Binary Tree Maximum Path Sum 求二叉树的最大路径和 Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child conn
C++实现LeetCode(127.词语阶梯)

[LeetCode] 127.Word Ladder 词语阶梯 Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that: Only one letter can be changed at a time. Each transforme
C++实现LeetCode(129.求根到叶节点数字之和)

[LeetCode] 129. Sum Root to Leaf Numbers 求根到叶节点数字之和 Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number. An example is the root-to-leaf path 1->2->3 which represents the number 123. Find the total sum
C++实现LeetCode(121.买卖股票的最佳时间)

[LeetCode] 121.Best Time to Buy and Sell Stock 买卖股票的最佳时间 Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the sto
C++实现LeetCode(200.岛屿的数量)

[LeetCode] 200. Number of Islands 岛屿的数量 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four
C++或Go求矩阵里的岛屿的数量详解

目录 1.C++实现 2.go语言实现参考文献总结给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量. 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成.此外,你可以假设该网格的四条边均被水包围. 示例 1: 输入: grid = [ ["1","1","1","1","0"], ["1","1",
C++递归算法处理岛屿问题详解

目录岛屿问题定义例题一-岛屿的数量例题二-岛屿的周长岛屿问题定义岛屿问题是指用二维数组进行模拟, 1的位置表示陆地, 0的位置表示海洋.岛屿是指被水(0)包围的陆地(1) 如下图所示: 岛屿问题是一道典型的递归问题(一位大佬曾说将岛屿问题看成是4叉树,我觉得这个比喻非常好), 对每个陆地位置, 我们需要递归地检测它的上下左右位置是不是陆地. 下面我们来写一下对岛屿问题的递归模板: public void dfs(char[][] grid, int m, int n){ // 位置越
最短时间学会基于C++实现DFS深度优先搜索

目录前言 1.迷宫找出口,区分dfs,bfs: 一.DFS经典放牌可能组合二.leetcode 员工的重要性三.leetcode 图像渲染四.leetcode 被围绕的区域五.岛屿数量六. 小练习:岛屿的最大面积总结前言同学们肯定或多或少的听到过别人提起过DFS,BFS,却一直都不太了解是什么,其实两个各为搜索算法,常见使用深度优先搜索(DFS) 以及广度优先搜索(BFS) ,今天我们就来讲讲什么是深度优先搜索,深度优先就是撞到了南墙才知道回头,才会往上一层返回. 1.迷宫
python+pyqt5实现KFC点餐收银系统

本文实例为大家分享了python实现KFC点餐收银系统的具体代码,供大家参考,具体内容如下这个kfc收银系统我实现了的以下功能: 1.正常餐品结算和找零. 2.基本套餐结算和找零. 3.使用优惠劵购买餐品结算和找零. 4.可在一定时间段参与店内活动 5.模拟打印小票的功能(写到文件中). 工程文件: 肯德基.py文件实现各功能.kfctip.txt文件用于打印小票.picture文件里存放界面所需的图片.其他四个文件为各界面布局. 主界面: 正常餐品点餐界面: 套餐点餐界面: 活动套餐点餐界面
14 个Python小游戏源码分享

目录 1.吃金币 2.打乒乓 3.滑雪 4.并夕夕版飞机大战 5.打地鼠 6.小恐龙 7.消消乐 8.俄罗斯方块 9.贪吃蛇 10.24点小游戏 11.平衡木 12.外星人入侵 13.贪心鸟 14.井字棋888'' 1.吃金币源码分享: import os import cfg import sys import pygame import random from modules import * '''游戏初始化''' def initGame(): # 初始化pygame, 设置展示窗口
Python实现爬取腾讯招聘网岗位信息

目录介绍效果展示实现思路源码展示介绍开发环境 Windows 10 python3.6 开发工具 pycharm 库 numpy.matplotlib.time.xlutils.copy.os.xlwt, xlrd, random 效果展示代码运行展示实现思路 1.打开腾讯招聘的网址右击检查进行抓包,进入网址的时候发现有异步渲染,我们要的数据为异步加载 2.构造起始地址: start_url = ‘https://careers.tencent.com/tencentcareer
13个有趣又好玩的Python游戏代码分享

目录 1.吃金币 2.打乒乓 3.滑雪 4.并夕夕版飞机大战 5.打地鼠 6.小恐龙 7.消消乐 8.俄罗斯方块 9.贪吃蛇 10.24点小游戏 11.平衡木 12.外星人入侵 13.井字棋888 经常听到有朋友说,学习编程是一件非常枯燥无味的事情.其实,大家有没有认真想过,可能是我们的学习方法不对? 比方说,你有没有想过,可以通过打游戏来学编程? 今天我想跟大家分享几个Python小游戏,教你如何通过边打游戏边学编程! 1.吃金币源码分享: import os import cfg impo
Python实现外星人去哪了小游戏详细代码

1 为什么找不见外星人为什么我们见不到外星人? 曾经在物理学上有一个著名人物叫费米,大家知道费米是在物理学上发现中子轰击的人,有一个著名的费米悖论,就是费米追问为什么外星人还见不到? 费米的这个追问包含的意思是这样的,地球上产生人类,从几率上讲,绝不可能人类独在. 因为人类只不过是一个自然界的造物,只要自然条件达到这个状态,生命就会进入这个状态.大阳系只是一个小小的星系,仅银河系就有两千到四千亿颗恒星. 2 关于宇宙天文学家今天发现大约有5%的恒星有行星.大家算一下,拿两千亿算,5%的恒星
C++回溯算法深度优先搜索举例分析

目录扑克牌全排列员工的重要性图像渲染被围绕的区域岛屿数量电话号码的字母组合组合总数活字印书 N皇后扑克牌全排列假如有编号为1~ 3的3张扑克牌和编号为1~3的3个盒子,现在需要将3张牌分别放到3个盒子中去,且每个盒子只能放一张牌,一共有多少种不同的放法. 解题思路:假定按照牌面值从小到大依次尝试,即将1号牌放入第一个盒子中.按此顺序继续向后走,放完第三个盒子时,手中的牌也已经用完,再继续往后则到了盒子的尽头.此时一种放法已经完成了,即这条路走到了尽头,需要折返,重新回到上一个

C++实现LeetCode(200.岛屿的数量)

[LeetCode] 200. Number of Islands 岛屿的数量

相关推荐

随机推荐