力扣刷题-图论-岛屿类问题-集合实现（c++实现）

🕗 发布于 2024-07-24 09:08 leetcode 图论 c++ 学习算法

我的老师：力扣链接这道题题解中最高赞的回答nettee，从这篇题解中我学到了dfs框架以及解决思路，并独立完成了该题解里的几道习题
本人刷题的习惯是学会一个板子，然后之后的同类题都机械的用这个板子去做，最好不做创新，或许能给其他朋友提供一些规律性帮助，所以本blog把我各个题目的代码都放上来！

岛屿数量（简单）

这道是母题，放代码（后面的题目我一律按照这个板子去做）

class Solution {
public:
    int num=0;
    int numIslands(vector<vector<char>>& grid) {
        int rn = grid.size();    // 行数
        int cn = grid[0].size(); // 列数
        for (int r = 0; r < rn; r++) {
            for (int c = 0; c < cn; c++) {
                // 先标记
                if (grid[r][c] == '1') {
                    num++;
                }
                dfs(grid, r, c);
            }
        }
        return num;
    }
    void dfs(vector<vector<char>>& grid, int r, int c) {
        if (!inArea(grid, r, c) || grid[r][c] != '1')
            return;
        grid[r][c]='2';
        //四面（上下左右）去dfs
        dfs(grid, r - 1, c );
        dfs(grid, r , c + 1);
        dfs(grid, r + 1, c );
        dfs(grid, r , c - 1);
    }
    bool inArea(vector<vector<char>>& grid, int r, int c) {
        return (0 <= r) && (r < grid.size()) && (0 <= c) &&
               (c < grid[0].size());
    }
};

岛屿周长（简单）

岛屿周长
在这里插入图片描述

很容易分析出来，对岛屿点（1）去上下左右dfs，如果是0或者不在Area内，就可以周长+1，最后累计获得总周长，放代码：

class Solution {
    // 遍历上下左右，如果是陆地就不动，如果是海或者不在area内就+1
    // 总共只有一个岛屿

public:
    int peri = 0;
    int islandPerimeter(vector<vector<int>>& grid) {
        int rn = grid.size();
        int cn = grid[0].size();
        for (int r = 0; r < rn; r++) {
            for (int c = 0; c < cn; c++) {
                // 如果是陆地
                if (grid[r][c] != 1) {
                    continue;
                }
                // 如果是陆地才会
                dfs(grid, r, c);
            }
        }
        return peri;
    }
    void dfs(vector<vector<int>>& grid, int r, int c) {
        // 还要考虑grid==[2]的情况

        if (!inArea(grid, r, c) || grid[r][c] == 0) {
            peri++;
            return;
        }

        if (grid[r][c] == 2) {
            return;
        }

        grid[r][c] = 2;
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
        return;
    }
    bool inArea(vector<vector<int>>& grid, int r, int c) {
        return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
    }
};

岛屿的最大面积（中等）

岛屿的最大面积
这道题的思路也很明显，同理找到所有的岛屿，然后开一个新的变量maxs来存最大岛屿就OK，看代码：

此处dfs有点不同，返回值为int，然后直接把上下左右的dfs写在return里，大家看代码应该很好理解（其实上一题求周长也可以这样做，这里周长一道，面积一道，提供两种方案）

class Solution {
public:
    int maxs = 0;
    int s = 0;

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        // 同理
        int rn = grid.size();
        int cn = grid[0].size();
        for (int r = 0; r < rn; r++) {
            for (int c = 0; c < cn; c++) {
                if (grid[r][c] != 1)
                    continue;
                s = dfs(grid, r, c);
                maxs = s > maxs ? s : maxs;
            }
        }
        return maxs;
    }
    int dfs(vector<vector<int>>& grid, int r, int c) {
        if (!InArea(grid, r, c)) {
            return 0;
        }
        // 如果是海
        if (grid[r][c] != 1) {
            return 0;
        }
        grid[r][c] = 2;
        return 1 + dfs(grid, r - 1, c) + dfs(grid, r + 1, c) +
               dfs(grid, r, c - 1) + dfs(grid, r, c + 1);
    }
    bool InArea(vector<vector<int>>& grid, int r, int c) {
        return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
    }
};

最大人工岛（困难）

最大人工岛

本题我一开始的思路是：遍历每个0点，然后赋值为1，再遍历该情况下的最大岛屿面积（类似上一题思路）；再把该1变回0，看下一个变1的可能点；取所有情况的面积最大值——无奈空间超限！
于是我看了题解，理解了以后又自己写，与官方题解的代码略有不同，更贴近我爱用的板子（与上面几道吻合）
思路：
- 先计算出每一个岛屿的面积（防止之后重复计算）——第一次双重循环
- 第二次双重循环思路同理，把0变成1，看是否能连接一些岛屿
- 已写明注释！
- ps. 这份代码巧用vector< int > d = {0, -1, 0, 1, 0};，大家可以好好看下，和dfs(grid,r-1,s)等上下左右遍历异曲同工，适用于减少递归，代码更清晰

class Solution {
public:
    int t = 0;
    vector<int> square;//存储每一个岛屿的面积
    vector<int> d = {0, -1, 0, 1, 0};
    int zero=0;//是否有0可以变1，如果没有的话就说明给的vector是全1，直接返回总面积！）
    int largestIsland(vector<vector<int>>& grid) {
        int n = grid.size();
        // 先计算每个岛屿的面积吧
        vector<vector<int>> used(n,vector<int>(n));
       square.resize(n * n + 2, 0);//这行相当于是一个经验吧，
       //否则报错（看我上一篇博客）
        int r = 0, c = 0, x1 = 0, y1 = 0, s = 0, maxs = 0;
        for (r = 0; r < n; r++) {
            for (c = 0; c < n; c++) {
                // 如果就是大陆
                if (grid[r][c] == 1) {
                    t++;//注意，这里我本来想让t从0开始的，后来发现不行，
                    //因为如果没有标记的岛屿也是0，之后用t来索引的时候会出错
                    square[t] = dfs(grid, r, c, t, used);
                    //这里得到岛屿面积
                }
            }
        }
        unordered_set<int> connected;
        // 现在完成面积的计算
        for (r = 0; r < n; r++) {
            for (c = 0; c < n; c++) {
                if (grid[r][c] == 0) {
                //说明该vector并非全1
                    zero=1;
                    //面积
                    s = 1;
                    connected.clear();
                    // 尝试变成1，看着附近的area
                    for (int i = 0; i < 4; i++) {
                        x1 = r + d[i];
                        y1 = c + d[i + 1];
                        if (InArea(grid,x1,y1)&&used[x1][y1] != 0 &&
                            connected.count(used[x1][y1]) == 0) {
                            // s面积加上来
                            s += square[used[x1][y1]];
                            connected.insert(used[x1][y1]);
                        }
                    }
                    // 该情况的面积计算完毕
                    maxs = max(s, maxs);
                }
            }
        }
        //如果是全1的话就直接返回square[1]
        return zero==0?square[1]:maxs;
    }
//dfs功效纯粹为了计算每个岛屿的面积！
    int dfs(vector<vector<int>>& grid, int r, int c, int t,
            vector<vector<int>>& used) {
        if (!InArea(grid, r, c) || used[r][c] != 0 || grid[r][c] != 1)
            return 0;
        used[r][c] = t;
        int x1, y1, s = 1;
        // 已经遍历过就标记为2
        grid[r][c] = 2;
        for (int i = 0; i < 4; i++) {
            x1 = r + d[i], y1 = c + d[i + 1];
            s += dfs(grid, x1, y1, t, used);
        }

        return s;
    }

    bool InArea(vector<vector<int>>& grid, int r, int c) {
        return 0 <= r && r < grid.size() && 0 <= c && c < grid[0].size();
    }
};

原文地址：https://blog.csdn.net/Winnie12138_/article/details/140631268

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：利用OSMnx求路网最短路径并可视化（二）
下一篇：vue3 vxe-table 点击行，不显示选中状态，加上设置isCurrent: true就可以设置选中行的状态。

MYSQL常用基本操作总结
SQL查询中各个关键字的执行先后顺序： from > on> join > where > group by > with > having >select
阅读更多2024-09-19
JAVA并发编程系列之Semaphore信号量剖析
候选人，心中万马奔腾！！！吐了一口82年老血，当场砸电脑回家！原因是：腾讯T2面试，现场限时3分钟+限最多20行代码，模拟地铁口安检进站。其中安检入口10个，当前排队人数是100个，每个人安检进站耗时
阅读更多2024-09-19
24年蓝桥杯及攻防世界赛题-MISC-2
24年蓝桥杯及攻防世界赛题-MISC-2
阅读更多2024-09-19
干货-并发编程提高——重谈 RUNNABLE-上篇（十四）
直接看它的 Javadoc 中的说明：一个在 JVM 中执行的线程处于这一状态中。（A threadexecuting而传统的进（线）程状态一般划分如下：注：这里的进程指早期的单线程进程，这里所谓进程
阅读更多2024-09-19
phpstudy 建站使用 php8版本打开 phpMyAdmin后台出现网页提示致命错误：（phpMyAdmin这是版本问题导致的）
将网站根目录phpMyAdmin4.8.5里面的文件换成官网下载的5.2.1版本即可。重启网站，打开phpMyAdmin后台即可（若打不开更改 mysql密码即可）解决方法：官网下载phpmyadm
阅读更多2024-09-19
零工市场小程序：保障灵活就业
截止2024年高校毕业生达到1179万，在今年的经济情况下，就业市场就面临着比较大的压力，许多毕业生面临一时之间难以找到合适的工作的问题，那么求职者就会需要一份临时的工作来得到报酬，面对传统的找零工方
阅读更多2024-09-19
Linux中权限和指令
mv指令是move的缩写，用来，经常用来备份文件或目录。
阅读更多2024-09-19
Redis 底层揭秘：事务与 Lua 脚本的工作原理
定义Lua 是一种轻量级的脚本语言，它可以在 Redis 中被执行，用于实现复杂的逻辑操作。优势与事务相比，Lua 脚本具有更高的性能和更好的灵活性。Lua 脚本可以在 Redis 服务器端一次性执行
阅读更多2024-09-19
Vue3使用shapefile读取矢量数据，以数组形式返回坐标点
【代码】Vue3使用shapefile读取矢量数据，以数组形式返回坐标点。
阅读更多2024-09-19
WEB 编程：使用富文本编辑器 Quill 配合 WebBroker 后端
评估了好几个，最后选择这个开源的。把前端代码，存储为一个单独的文本文件，方便随便哪个页面需要的时候可以使用。相当于封装为一个独立的对象，方便代码重用。
阅读更多2024-09-19

力扣刷题-图论-岛屿类问题-集合实现（c++实现）

岛屿数量（简单）

岛屿周长（简单）

岛屿的最大面积（中等）

最大人工岛（困难）

相关文章