1.19 力扣中等图论

这篇具有很好参考价值的文章主要介绍了1.19 力扣中等图论。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

思路1:

使用DFS深度搜索,在外层用for循环遍历每个元素,一旦元素为‘1’则进入“新岛屿”,并在该个“新岛屿”做DFS深度搜索,将周围为“1”的都标记成“已经选择过”。最后记录进入“新岛屿的次数即可”

class Solution {
public:
    //判断该坐标是否符合
    bool isValid(vector<vector<char>>& grid,int row,int col)
    {
        if(row<0||col<0||row>=grid.size()||col>=grid[0].size()) return false;
        return true;
    }
    //dfs将一个岛屿都标记为“已经选择过”
    void dfs(vector<vector<char>>& grid,vector<vector<bool>>& valid,int row,int col)
    {
        if(!isValid(grid,row,col)||!valid[row][col]||grid[row][col]=='0') return;
        valid[row][col]=false;
        //对四个方向进行延深
        if(isValid(grid,row+1,col)) dfs(grid,valid,row+1,col);
        if(isValid(grid,row,col+1)) dfs(grid,valid,row,col+1);
        if(isValid(grid,row-1,col)) dfs(grid,valid,row-1,col);
        if(isValid(grid,row,col-1)) dfs(grid,valid,row,col-1);
    }
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0) return 0;
        vector<vector<bool>> valid(grid.size(),vector<bool>(grid[0].size(),true));
        int ret=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(grid[i][j]=='0'||!valid[i][j]) continue;
                //dfs进行染色
                dfs(grid,valid,i,j);
                ret++;
            }
        }
        return ret;
    }
};

思路2:

广度搜索:用类似策略,只是用dfs代替了bfs

class Solution {
public:
    //判断该坐标是否符合
    bool isValid(vector<vector<char>>& grid,int row,int col)
    {
        if(row<0||col<0||row>=grid.size()||col>=grid[0].size()) return false;
        return true;
    }
    //bfs将一个岛屿都标记为“已经选择过”
    void bfs(vector<vector<char>>& grid,vector<vector<bool>>& valid,int row,int col)
    {
        queue<pair<int,int>> q;
        q.push(make_pair(row,col));
        while(!q.empty())
        {
            pair<int,int> temp=q.front();
            q.pop();
            int temp_row=temp.first,temp_col=temp.second;
            //染色
            valid[temp_row][temp_col]=false;
            if(isValid(grid,temp_row+1,temp_col)&&valid[temp_row+1][temp_col]&&grid[temp_row+1][temp_col]=='1') q.push(make_pair(temp_row+1,temp_col));
            if(isValid(grid,temp_row,temp_col+1)&&valid[temp_row][temp_col+1]&&grid[temp_row][temp_col+1]=='1') q.push(make_pair(temp_row,temp_col+1));
            if(isValid(grid,temp_row-1,temp_col)&&valid[temp_row-1][temp_col]&&grid[temp_row-1][temp_col]=='1') q.push(make_pair(temp_row-1,temp_col));
            if(isValid(grid,temp_row,temp_col-1)&&valid[temp_row][temp_col-1]&&grid[temp_row][temp_col-1]=='1') q.push(make_pair(temp_row,temp_col-1));
        }

    }
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0) return 0;
        vector<vector<bool>> valid(grid.size(),vector<bool>(grid[0].size(),true));
        int ret=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(grid[i][j]=='0'||!valid[i][j]) continue;
                //bfs进行染色
                bfs(grid,valid,i,j);
                ret++;
            }
        }
        return ret;
    }
};

但以上代码会超时。。。代码中是从队列中取出节点再标记,改为将节点加入队列就立即标记文章来源地址https://www.toymoban.com/news/detail-807934.html

class Solution {
public:
    //判断该坐标是否符合
    bool isValid(vector<vector<char>>& grid,int row,int col)
    {
        if(row<0||col<0||row>=grid.size()||col>=grid[0].size()) return false;
        return true;
    }
    //bfs将一个岛屿都标记为“已经选择过”
    void bfs(vector<vector<char>>& grid,vector<vector<bool>>& valid,int row,int col)
    {
        queue<pair<int,int>> q;
        q.push(make_pair(row,col));
        //染色
        valid[row][col]=false;
        while(!q.empty())
        {
            pair<int,int> temp=q.front();
            q.pop();
            int temp_row=temp.first,temp_col=temp.second;
            if(isValid(grid,temp_row+1,temp_col)&&valid[temp_row+1][temp_col]&&grid[temp_row+1][temp_col]=='1') 
            {
                q.push(make_pair(temp_row+1,temp_col));
                valid[temp_row+1][temp_col]=false;
            }
            if(isValid(grid,temp_row,temp_col+1)&&valid[temp_row][temp_col+1]&&grid[temp_row][temp_col+1]=='1')
            {
                q.push(make_pair(temp_row,temp_col+1));
                valid[temp_row][temp_col+1]=false;
            } 
            if(isValid(grid,temp_row-1,temp_col)&&valid[temp_row-1][temp_col]&&grid[temp_row-1][temp_col]=='1')
            {
                q.push(make_pair(temp_row-1,temp_col));
                valid[temp_row-1][temp_col]=false;
            } 
            if(isValid(grid,temp_row,temp_col-1)&&valid[temp_row][temp_col-1]&&grid[temp_row][temp_col-1]=='1') 
            {
                q.push(make_pair(temp_row,temp_col-1));
                valid[temp_row][temp_col-1]=false;
            }
        }

    }
    int numIslands(vector<vector<char>>& grid) {
        if(grid.size()==0) return 0;
        vector<vector<bool>> valid(grid.size(),vector<bool>(grid[0].size(),true));
        int ret=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(grid[i][j]=='0'||!valid[i][j]) continue;
                //bfs进行染色
                bfs(grid,valid,i,j);
                ret++;
            }
        }
        return ret;
    }
};

到了这里,关于1.19 力扣中等图论的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Go 1.19 排序算法

    插入排序是一种简单直观的排序算法,它的基本思想是将待排序的元素插入到已经排好序的序列中,从而得到一个新的有序序列。插入排序的具体过程如下: 从第一个元素开始,认为它已经是有序的序列。 取出下一个元素,在已经排序的序列中从后向前扫描。 如果已经排序

    2024年02月07日
    浏览(40)
  • 1.12 力扣中等图论

    797. 所有可能的路径 - 力扣(LeetCode) 给你一个有  n  个节点的  有向无环图(DAG) ,请你找出所有从节点  0  到节点  n-1  的路径并输出( 不要求按特定顺序 )   graph[i]  是一个从节点  i  可以访问的所有节点的列表(即从节点  i  到节点  graph[i][j] 存在一条有向边)

    2024年01月22日
    浏览(29)
  • 每日一题 187. 重复的DNA序列(中等)

    由于今天做了周赛,每日一题就简单点直接暴力哈希

    2024年02月05日
    浏览(29)
  • 【图论】Leetcode 200. 岛屿数量【中等】

    给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。 岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。 此外,你可以假设该网格的四条边均被水包围。 示例 1: 输入:grid = [ [“1”,“1”,“1”,“

    2024年04月15日
    浏览(45)
  • 【图论】Leetcode 207. 课程表【中等】

    你这个学期必须选修 numCourses 门课程,记为 0 到 numCourses - 1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出,其中 prerequisites[i] = [ai, bi] ,表示如果要学习课程 ai 则 必须 先学习课程 bi 。 例如,先修课程对 [0, 1] 表示:想要学习课程 0 ,你需要先

    2024年04月14日
    浏览(47)
  • 【图论】Leetcode 994. 腐烂的橘子【中等】

    在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一: 值 0 代表空单元格; 值 1 代表新鲜橘子; 值 2 代表腐烂的橘子。 每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,

    2024年04月15日
    浏览(30)
  • 【图论】Leetcode 208. 实现 Trie (前缀树)【中等】

    Trie (发音类似 “try”)或者说 前缀树 是一种树形数据结构,用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景,例如自动补完和拼写检查。 请你实现 Trie 类: Trie() 初始化前缀树对象。 void insert(String word) 向前缀树中插入字符串 word 。 boolean

    2024年04月16日
    浏览(59)
  • 算法学习——LeetCode力扣图论篇3(127. 单词接龙、463. 岛屿的周长、684. 冗余连接、685. 冗余连接 II)

    127. 单词接龙 - 力扣(LeetCode) 描述 字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord - s1 - s2 - … - sk: 每一对相邻的单词只差一个字母。 对于 1 = i = k 时,每个 si 都在 wordList 中。注意, beginWord 不需要在 wordList 中。 sk == endWord 给你两

    2024年04月09日
    浏览(77)
  • 【每日一题】ABC256F-Rook Score | 思维 | 中等

    从今天开始,随机开始每日一题~ 原题链接 给定一个 1 0 9 × 1 0 9 10^9times 10^9 1 0 9 × 1 0 9 大小的矩阵,给出其中 n n n 个点的权值,第 i i i 个点 ( x i , y i ) (x_i,y_i) ( x i ​ , y i ​ ) 的权值为 w i w_i w i ​ ,剩下的 1 0 18 − n 10^{18}-n 1 0 18 − n 个点的权值为 0 0 0 。 现在让你选择一

    2024年02月11日
    浏览(25)
  • 【每日一题】ARC158B - Sum-Product Ratio | 数学 | 中等

    原题链接 给定一个长度为 n n n 的数组,选择三个下标不同元素 x , y , z x,y,z x , y , z ,问 x + y + z x y z frac{x+y+z}{xyz} x yz x + y + z ​ 的最大值和最小值是多少。 1 ≤ n ≤ 2 ⋅ 1 0 5 1leq nleq 2cdot 10^5 1 ≤ n ≤ 2 ⋅ 1 0 5 − 1 0 6 ≤ x i ≤ 1 0 6 , x i ≠ 0 -10^6leq x_ileq 10^6,x_ineq 0 − 1 0

    2024年02月07日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包