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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig