leetcode 1631. 最小体力消耗路径 二分+BFS、并查集、Dijkstra算法

本文主要是介绍leetcode 1631. 最小体力消耗路径 二分+BFS、并查集、Dijkstra算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

最小体力消耗路径

在这里插入图片描述
题目与水位上升的泳池中游泳类似

二分查找+BFS

首先,采用二分查找,确定一个体力值,再从左上角,进行BFS,查看能否到达右下角,如果不行,二分查找就往大的数字进行查找,如果可以,还要继续往小的数字进行查找,比如示例1,数字10肯定可以到达右下角,但不是最小的体力。

class Solution {
public:int dx[4] = { 0,0,-1,1 };int dy[4] = { -1,1,0,0 };int m, n;bool bfs(vector<vector<int>>& heights, vector<vector<int>> exist, int sub)//二分+BFS{exist[0][0] = 1;queue<pair<int, int>> q;q.emplace(0, 0);while (!q.empty()){auto [i, j] = q.front();q.pop();for (int k = 0; k < 4; ++k)//上下左右四个方向{int newi = i + dx[k];int newj = j + dy[k];if (newi >= 0 && newi < m && newj >= 0 && newj < n && !exist[newi][newj] && sub >= abs(heights[i][j] - heights[newi][newj])){exist[newi][newj] = 1;if (newi == m - 1 && newj == n - 1)//到达右下角{return true;}q.emplace(newi, newj);}}}return false;}int minimumEffortPath(vector<vector<int>>& heights){m = heights.size(), n = heights[0].size();vector<vector<int>> exist(m, vector<int>(n, 0));int begin = 0, end = 999999;//最大值,由题目给的边界值得出int result = 0;while (begin <= end){int mid = (begin + end) >> 1;if (bfs(heights, exist, mid)){result = mid;end = mid - 1;}else{begin = mid + 1;}}return result;}
};

二分+BFS一样适合于水位上升的题目。

二分+并查集
依然采用二分查找,确定一个值,只不过BFS换成了并查集

并查集:开辟一个数组,存储每个结点的父节点,当二分查找的某一个值,大于某两个点的差值,就将将其中一个点作为另外一个点的父节点,最后,如果可以到达右下角,那么,左上角的父节点就是右下角,此时,二分查找的值就可能是体力最小值。

这里用到了二维转一维

//并查集
class DSU
{
public:DSU(int n):parent(vector<int>(n, 0)){for (int i = 0; i < n; ++i)//父节点先初始化为自己{parent[i] = i;}}int Find(int pos){if (parent[pos] != pos)parent[pos] = Find(parent[pos]);//赋值为祖宗结点,减少搜索次数//return Find(parent[pos])parent[pos]为父节点return parent[pos];}void Union(int i, int j){parent[Find(i)] = Find(j);}bool check(int i, int j){return Find(i) == Find(j);}
private:vector<int> parent;
};class Solution {
public:int minimumEffortPath(vector<vector<int>>& heights){int m = heights.size(), n = heights[0].size();int result = 0;int begin = 0, end = 999999;//这里每次都得重新连接一遍,所以用二分,跟水池上升的游泳的题目相比while (begin <= end){int mid = (begin + end) >> 1;DSU dsu(m * n);//二维转一维for (int i = 0; i < m; ++i){for (int j = 0; j < n; ++j){if (i + 1 < m && abs(heights[i + 1][j] - heights[i][j]) <= mid)//下标方格可以到达{dsu.Union(i * n + j, (i + 1) * n + j);}if (j + 1 < n && abs(heights[i][j + 1] - heights[i][j]) <= mid)//右边方格可以到达{dsu.Union(i * n + j, i * n + j + 1);}}}if (dsu.check(0, m * n - 1)){result = mid;end = mid - 1;}else{begin = mid + 1;}}return result;}
};

在这里插入图片描述
相比水位上升的题目的并查集,这里的并查集并没有那么有趣,因为水位上升的题目的是采用从0遍历到最大值而不是二分查找,再对某一个值进行并查集。因为,由于水位上升的题目的数据是不重复的,所以可以采用哈希表记录每个值的位置,从0到最大值,只要在某个值,左上角和左下角已经连通,就是答案。比如示例一,分别使用哈希表的记录每个数字的位置,遍历水位,当水位为0时,没有可以连接的,但是水位为1时,可以连接0-》1,水位为2时,连接0-》2,水位为3时,连接1-》3,2-》3。如果这里采用二分的话,假如结果是10时,全部都被连通了,要往下查找更小的值的话,就要重新开辟parent数组。

如果,在最小体力消耗路径的题目依然采用遍历,而不是二分查找的话,虽然还是一个parent数组,当体力来到2,体力1可以连接的点已经连接好了,但是你还是避免不了两层循环遍历heights,查看哪里还可以连接,而不是像上面题目那样,直接哈希表确认2的位置,进行上下左右判断是否可以连接。

Dijkstra算法

开辟一个数组,记录源顶点(左上角)到达某一个点的最小体力
当来到一个新的顶点,消耗的体力比记载的小,就要存储起来,并且以这一个点为新起点,更新上下左右的体力值

//Dijkstra算法
class Solution {
public:int minimumEffortPath(vector<vector<int>>& heights){int m = heights.size(), n = heights[0].size();int INF = INT_MAX / 2;vector<int> dist(m * n, INF);//记录从源顶点,到达某个顶点的最小体力消耗dist[0] = 0;//顶点为0queue<tuple<int, int, int>> q;q.emplace(0, 0, 0);//分别表示最小体力差值,坐标while (!q.empty()){auto [physical, i, j] = q.front();q.pop();if (dist[i * n + j] < physical)//已经被处理过里,并且可以用更少的体力到达该位置continue;if (j + 1 < n){int nextPhysical = max(physical, abs(heights[i][j] - heights[i][j + 1]));//到达左边的方格需要的体力if (nextPhysical < dist[i * n + j + 1]){dist[i * n + j + 1] = nextPhysical;q.emplace(nextPhysical, i, j + 1);}}if (i + 1 < m){int nextPhysical = max(physical, abs(heights[i][j] - heights[i + 1][j]));//到达下边的方格需要的体力if (nextPhysical < dist[(i + 1) * n + j]){dist[(i + 1) * n + j] = nextPhysical;q.emplace(nextPhysical, i + 1, j);}}if (i - 1 >= 0){int nextPhysical = max(physical, abs(heights[i][j] - heights[i - 1][j]));//到达上边方格需要的体力if (nextPhysical < dist[(i - 1) * n + j]){dist[(i - 1) * n + j] = nextPhysical;q.emplace(nextPhysical, i - 1, j);}}if (j - 1 >= 0){int nextPhysical = max(physical, abs(heights[i][j] - heights[i][j - 1]));//到达左边方格需要的体力if (nextPhysical < dist[i * n + j - 1]){dist[i * n + j - 1] = nextPhysical;q.emplace(nextPhysical, i, j - 1);}}}return dist[m * n - 1];}
};

这篇关于leetcode 1631. 最小体力消耗路径 二分+BFS、并查集、Dijkstra算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

Linux修改pip和conda缓存路径的几种方法

《Linux修改pip和conda缓存路径的几种方法》在Python生态中,pip和conda是两种常见的软件包管理工具,它们在安装、更新和卸载软件包时都会使用缓存来提高效率,适当地修改它们的缓存路径... 目录一、pip 和 conda 的缓存机制1. pip 的缓存机制默认缓存路径2. conda 的缓

Windows系统下如何查找JDK的安装路径

《Windows系统下如何查找JDK的安装路径》:本文主要介绍Windows系统下如何查找JDK的安装路径,文中介绍了三种方法,分别是通过命令行检查、使用verbose选项查找jre目录、以及查看... 目录一、确认是否安装了JDK二、查找路径三、另外一种方式如果很久之前安装了JDK,或者在别人的电脑上,想

Python中Windows和macOS文件路径格式不一致的解决方法

《Python中Windows和macOS文件路径格式不一致的解决方法》在Python中,Windows和macOS的文件路径字符串格式不一致主要体现在路径分隔符上,这种差异可能导致跨平台代码在处理文... 目录方法 1:使用 os.path 模块方法 2:使用 pathlib 模块(推荐)方法 3:统一使

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

MySQL9.0默认路径安装下重置root密码

《MySQL9.0默认路径安装下重置root密码》本文主要介绍了MySQL9.0默认路径安装下重置root密码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们... 目录问题描述环境描述解决方法正常模式下修改密码报错原因问题描述mysqlChina编程采用默认安装路径,

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1