算法沉淀——多源 BFS（leetcode真题剖析）

news/2024/6/29 12:02:36 标签: 算法, 宽度优先, leetcode

在这里插入图片描述

算法沉淀——多源 BFS（leetcode真题剖析）

  • 01.矩阵
  • 02.飞地的数量
  • 03.地图中的最高点
  • 04.地图分析

多源 BFS 是指从多个源点同时进行广度优先搜索的算法。在传统的 BFS 中，我们通常从一个起始点开始，逐层遍历所有的相邻节点。而在多源 BFS 中，我们可以同时从多个源点开始，从这些源点出发，逐层向外扩展，直到达到目标或者遍历完整个图。

多源 BFS 可以用于解决一些问题，例如：

  1. 多个人同时逃生： 在一个迷宫中，有多个人同时被困在不同的位置，需要找到最短路径逃离迷宫。可以从这些人的位置同时开始 BFS，第一个相遇的点就是大家逃生的最短路径。
  2. 多点到达目标问题： 在一些网络传播或者路由问题中，多个点需要同时到达某个目标点，可以使用多源 BFS 找到最短路径。
  3. 并行计算： 在一些并行计算的场景中，多源 BFS 可以用于并行地计算多个点到其他点的最短路径。

多源 BFS 的实现方式与单源 BFS 类似，只是需要同时从多个源点开始扩展。通常使用队列来进行层次遍历，每一层表示到达目标的步数。

01.矩阵

题目链接：https://leetcode.cn/problems/01-matrix/

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

示例 1：
在这里插入图片描述

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：
在这里插入图片描述

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • mat[i][j] is either 0 or 1.
  • mat 中至少有一个 0

思路

从 0 开始层序遍历，并且记录遍历的层数。当第一次碰到 1 的时候，当前的层数就是这个 1 离 0 的最短距离。这一种方式，在遍历的时候标记一下处理过的 1 ，能够做到只用遍历整个矩阵一次，就能得到最终结果。但是，这里有一个问题， 0 是有很多个的，我们怎么才能保证遇到的 1 距离这一个 0 是最近的呢？ 其实很简单，我们可以先把所有的 0 都放在队列中，把它们当成一个整体，每次把当前队列里面的所有元素向外扩展一次。

代码

class Solution{
    const int dx[4]={0,0,1,-1};
    const int dy[4]={-1,1,0,0};
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m=mat.size(),n=mat[0].size();
        vector<vector<int>> dist(m,vector<int>(n,-1));
        queue<pair<int,int>> q;

        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if(mat[i][j]==0){
                    q.push({i,j});
                    dist[i][j]=0;
                }

        while(!q.empty()){
            auto [a,b]=q.front();
            q.pop();
            for(int i=0;i<4;++i){
                int x=a+dx[i],y=b+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1){
                    dist[x][y]=dist[a][b]+1;
                    q.push({x,y});
                }
            }
        } 
        return dist;
    }
};

02.飞地的数量

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

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

示例 1：
在这里插入图片描述

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：
在这里插入图片描述

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。

提示：

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

思路1

中间的1要达到边界，首先就是要有1在边界并且能够接触到，所以我们可以直接在周围一圈做单源BFS遍历1，将它改为0，再遍历整个数组，剩下的1就是出不去的。

代码1

class Solution {
    const int dx[4]={0,0,1,-1};
    const int dy[4]={-1,1,0,0};
    int m,n;
    queue<pair<int,int>> q;

    void bfs(vector<vector<int>>& grid,int i,int j){
        q.push({i,j});
        grid[i][j]=0;

        while(!q.empty()){
            int sz=q.size();
            while(sz--){
                auto [a,b]=q.front();
                q.pop();

                for(int k=0;k<4;++k){
                    int x=a+dx[k],y=b+dy[k];
                    if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){
                        grid[x][y]=0;
                        q.push({x,y});
                    }
                }
            }
        }
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        m=grid.size(),n=grid[0].size();
        for(int i=0;i<m;++i){
            if(grid[i][0]==1) bfs(grid,i,0);
            if(grid[i][n-1]==1) bfs(grid,i,n-1);
        }
        for(int i=1;i<n-1;++i){
            if(grid[0][i]==1) bfs(grid,0,i);
            if(grid[m-1][i]==1) bfs(grid,m-1,i);
        }

        int ret=0;
        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if(grid[i][j]==1) ret+=1;

        return ret;
    }
};

思路2

使用多源BFS同时对周边的1进行遍历

代码2

class Solution {
    // 定义四个方向的坐标变化
    const int dx[4] = {0, 0, 1, -1};
    const int dy[4] = {1, -1, 0, 0};

public:
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        // 用于标记是否访问过的二维布尔型数组
        vector<vector<bool>> vis(m, vector<bool>(n));
        // 广度优先搜索的队列
        queue<pair<int, int>> q;

        // 1. 把边上的 1 加入到队列中
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
                    if (grid[i][j] == 1) {
                        q.push({i, j});
                        vis[i][j] = true;
                    }

        // 2. 多源 BFS
        while (!q.empty()) {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; i++) {
                int x = a + dx[i], y = b + dy[i];
                // 如果相邻单元格是陆地且未访问过，加入队列并标记为已访问
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) {
                    vis[x][y] = true;
                    q.push({x, y});
                }
            }
        }

        // 3. 统计结果
        int ret = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                // 统计未被包围的陆地单元格数量
                if (grid[i][j] == 1 && !vis[i][j])
                    ret++;
        return ret;
    }
};

03.地图中的最高点

题目链接：https://leetcode.cn/problems/map-of-highest-peak/

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。

  • 如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。
  • 如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。

你需要按照如下规则给每个单元格安排高度：

  • 每个格子的高度都必须是非负的。
  • 如果一个格子是 水域 ，那么它的高度必须为 0 。
  • 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）

找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。

请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

示例 1：

**在这里插入图片描述
**

输入：isWater = [[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。

示例 2：

**在这里插入图片描述
**

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案。

思路

这一题我们要读懂题意，将原数组画出就不难发现其实和第一题矩阵的解法是一样的，同样都是使用多源BFS来解决这个问题

代码

class Solution {
    const int dx[4] = {0, 0, 1, -1};
    const int dy[4] = {-1, 1, 0, 0};

public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m = isWater.size(), n = isWater[0].size();
        vector<vector<int>> dist(m, vector<int>(n, -1));
        queue<pair<int, int>> q;

        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (isWater[i][j]) {
                    dist[i][j] = 0;
                    q.push({i, j});
                }

        while (!q.empty()) {
            auto [a, b] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int x = a + dx[i], y = b + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) {
                    dist[x][y] = dist[a][b] + 1;
                    q.push({x, y});
                }
            }
        }
        return dist;
    }
};
  1. 创建一个二维矩阵dist，用于存储每个位置到水域的最近距离。初始化所有元素为-1。
  2. 创建一个队列q，用于进行广度优先搜索。将所有水域的位置（isWater[i][j]为1的位置）加入队列，并将其到水域的距离设为0。
  3. 使用BFS遍历队列，不断扩展到达的位置。对于每个位置，检查其四个相邻的位置，如果相邻位置合法且未被访问过，更新其到水域的距离并将该位置加入队列。
  4. 最终，返回计算得到的dist矩阵。

04.地图分析

题目链接：https://leetcode.cn/problems/as-far-from-land-as-possible/

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

示例 1：

**在这里插入图片描述
**

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例 2：

**在这里插入图片描述
**

输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释： 
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

提示：

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] 不是 0 就是 1

思路

我们可以将每个陆地同时向海洋扩张，更新海洋到陆地的距离，最终更新的数组中最大的那个数就是最大距离，问题转化后看似是找最大距离，其实找的是最近距离，和第一题矩阵有异曲同工之妙。

代码

class Solution {
    const int dx[4]={0,0,1,-1};
    const int dy[4]={-1,1,0,0};
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m=grid.size(),n=grid[0].size();
        vector<vector<int>> dist(m,vector<int>(n,-1)); 
        queue<pair<int,int>> q;

        for(int i=0;i<m;++i)
            for(int j=0;j<n;++j)
                if(grid[i][j]){
                    dist[i][j]=0;
                    q.push({i,j});
                }

        int ret=-1;
        while(!q.empty()){
            auto [a,b] = q.front();
            q.pop();
            for(int i=0;i<4;i++){
                int x=a+dx[i],y=b+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&dist[x][y]==-1){
                    dist[x][y]=dist[a][b]+1;
                    q.push({x,y});
                    ret=max(ret,dist[x][y]);
                }
            }
        }
        return ret;
    }
};

http://www.niftyadmin.cn/n/5382614.html

相关文章

【机器学习笔记】13 降维

【机器学习笔记】13 降维

降维概述 维数灾难 维数灾难(Curse of Dimensionality)&#xff1a;通常是指在涉及到向量的计算的问题中&#xff0c;随着维数的增加&#xff0c;计算量呈指数倍增长的一种现象。在很多机器学习问题中&#xff0c;训练集中的每条数据经常伴随着上千、甚至上万个特征。要处理这…
阅读更多...
Android S - 添加按键，上报键值为0

Android S - 添加按键，上报键值为0

仅作记录 展锐8581模块 device/sprd/mpool/module/keylayout/gpio-keys.kl#仿照下面的形式&#xff0c;新增一行 key 68 F10 WAKE key 114 VOLUME_DOWN WAKE key 115 VOLUME_UP WAKE key 116 POWER WAKE key 212 CAM…
阅读更多...
爬虫知识--01

爬虫知识--01

爬虫介绍 # 爬虫的概念&#xff1a; 通过编程技术(python:request,selenium)&#xff0c;获取互联网中的数据(app&#xff0c;小程序&#xff0c;网站)&#xff0c;数据清洗(xpaht&#xff0c;lxml)后存到库中(mysql&#xff0c;redis&#xff0c;文件&#xff0c;excel&#x…
阅读更多...
Rabbitmq入门与应用(二)-RabbitMQ工作模型

Rabbitmq入门与应用(二)-RabbitMQ工作模型

RabbitMQ工作模型 RabbitMQ Tutorials — RabbitMQ Broker RabbitMQ服务。 Connection 生产者或是服务者都需要与Broker建立的TCP连接。 Channel 保持的TCP长连接里面去创建和释放Channel&#xff0c;从而减少资源的消耗。其中Channel是相互隔离的&#xff0c;不能共享。 Queu…
阅读更多...
面试系列之《Spark》（持续更新...）

面试系列之《Spark》（持续更新...）

1.job&stage&task如何划分&#xff1f; job&#xff1a;应用程序中每遇到一个action算子就会划分为一个job。 stage&#xff1a;一个job任务中从后往前划分&#xff0c;分区间每产生了shuffle也就是宽依赖则划分为一个stage&#xff0c;stage这体现了spark的pipeline思…
阅读更多...
【Linux系统化学习】深入理解文件系统(Ext2文件系统)

【Linux系统化学习】深入理解文件系统(Ext2文件系统)

目录 前言 磁盘的物理结构 物理结构 磁头和盘片工作解析图 盘面区域划分图&#xff08;俯视盘面图&#xff09; 扇区的寻址、定位&#xff08;CHS定位&#xff09; 磁盘存储的逻辑抽象结构 LBA定址 文件系统 磁盘分区 EXT2文件系统 组块中的信息介绍 查看inode编号…
阅读更多...
rocketMQ-Dashboard安装与部署

rocketMQ-Dashboard安装与部署

1、下载最新版本rocketMQ-Dashboard 下载地址&#xff1a;https://github.com/apache/rocketmq-dashboard 2、下载后解压&#xff0c;并用idea打开 3、修改配置 ①、修改端口及rocketmq服务的ip&#xff1a;port ②、修改访问账号、密码 3、然后启动访问&#xff1a; 4、mav…
阅读更多...
iOS 使用Image I/O 实现超大图片降采样

iOS 使用Image I/O 实现超大图片降采样

一个图片解码成未压缩的位图的时候&#xff0c;占用的内存和图片的文件大小没有关系&#xff0c;和图片的尺寸大小有关系&#xff0c;尺寸越大&#xff0c;所需要的像素点越多&#xff0c;所以超大图片&#xff0c;我们需要进行优化处理 这里直接上降采样代码 给UIImage 添加…
阅读更多...
最新文章

Copyright @ 2022~2023