手工做衣服网站,营销网站建设公司排名,网站备案号有效期,网站推广公司兴田德润官网多少#x1f525;博客主页#xff1a; A_SHOWY#x1f3a5;系列专栏#xff1a;力扣刷题总结录 数据结构 云计算 数字图像处理
1631. 最小体力消耗路径https://leetcode.cn/problems/path-with-minimum-effort/这道题目的核心思路是#xff1a;使用了二分查找和BFS 博客主页 A_SHOWY系列专栏力扣刷题总结录 数据结构 云计算 数字图像处理
1631. 最小体力消耗路径https://leetcode.cn/problems/path-with-minimum-effort/这道题目的核心思路是使用了二分查找和BFS 深度优先遍历结合的方式来解决路径搜索问题在每一次二分查找中通过 BFS 来检查是否存在满足条件的路径并不断调整查找的范围直到找到满足条件的最小值为止
第一步 static constexpr int dirs[4][2] {{-1,0},{1,0},{0,1},{0,-1}};
static:关键字用于声明类的静态成员变量或函数,constexpr关键字用于声明常量表达式,连起来用于声明静态常量成员变量
dirs用于表示四个方向的偏移量。这个数组是一个2维数组包含了4个方向的偏移值。
{ -1, 0 } 表示向左移动一个单位在二维平面上x轴减少1y轴不变。 { 1, 0 } 表示向右移动一个单位在二维平面上x轴增加1y轴不变。 { 0, -1 } 表示向上移动一个单位在二维平面上y轴减少1x轴不变。 { 0, 1 } 表示向下移动一个单位在二维平面上y轴增加1x轴不变。
第二步 queuepairint,int q;//定义一个队列存储BFS中待访问的结点坐标q.emplace(0,0);//创建一个数组记录已经访问过的结点vectorint seen(m*n);seen[0] 1;
1.声明了一个队列 q这个队列用于在 BFS 中存储待访问的节点坐标。这里使用了 pairint, int表示一个二维平面上的点的坐标pair 类型中的两个整数分别表示 x 和 y 坐标。
2.将起始节点的坐标 (0, 0) 放入队列 q 中。在 BFS 中通常从起始节点开始遍历或搜索。
3.创建了一个大小为 m * n 的 seen 数组用于标记已经访问过的节点。这个数组在 BFS 中用于避免重复访问节点存储方式是m*x y
4.将起始节点 (0, 0) 所代表的索引位置假设是二维平面中的第一个节点标记为已访问即将 seen 数组中对应的位置值设为 1
int m heights.size();//行数
int n heights[0].size();//列数
表示行数和列数
第三步 while(!q.empty()){//BFSauto[x,y] q.front();q.pop();for(int i 0;i 4; i){int nx x dirs[i][0];int ny y dirs[i][1];//计算当前节点 (x, y) 的第 i 个方向上相邻节点的坐标if(nx 0 nx m ny 0 ny n !seen[nx * n ny] abs(heights[x][y]-heights[nx][ny]) mid){q.emplace(nx,ny);//如果相邻节点满足条件将其坐标 (nx, ny) 加入队列 q表示将要访问这个节点。seen[nx * n ny] 1;//同时标记这个相邻节点为已访问在 seen 数组中将其对应位置的值设为 1避免重复访问} } 当队列 q 不为空时执行意味着还有待访问的节点从队列 q 中取出队首元素当前节点的坐标并将其分别赋值给变量 x 和 y。然后将该节点从队列中移出。计算当前节点 (x, y) 的第 i 个方向上相邻节点的坐标。如果相邻节点满足条件将其坐标 (nx, ny) 加入队列 q表示将要访问这个节点。同时标记这个相邻节点为已访问在 seen 数组中将其对应位置的值设为 1避免重复访问。
abs() 是 C 中的一个函数用于计算数值的绝对值。
第四步 if(seen[m * n -1]){//最后一个进入到数组中了已经被访问ans mid;right mid -1;}else{left mid 1;}
二分法部分当 if(seen[m * n -1])表示最后一个进入到数组中了已经被访问
所以总体代码实现为
class Solution {
private:static constexpr int dirs[4][2] {{-1,0},{1,0},{0,1},{0,-1}};
public:int minimumEffortPath(vectorvectorint heights) {int left 0; int right 999999;//十的六次方-1int ans 0;while(left right){int m heights.size();//行数int n heights[0].size();//列数int mid left ((right - left)/2);queuepairint,int q;//定义一个队列存储BFS中待访问的结点坐标q.emplace(0,0);//创建一个数组记录已经访问过的结点vectorint seen(m*n);seen[0] 1;while(!q.empty()){//BFSauto[x,y] q.front();q.pop();for(int i 0;i 4; i){int nx x dirs[i][0];int ny y dirs[i][1];if(nx 0 nx m ny 0 ny n !seen[nx * n ny] abs(heights[x][y]-heights[nx][ny]) mid){q.emplace(nx,ny);seen[nx * n ny] 1;} }}if(seen[m * n -1]){//最后一个进入到数组中了已经被访问ans mid;right mid -1;}else{left mid 1;}}return ans;}
};
有一个注意的点注意看heights大小的最大值为10的六次方所以我们right初始值为10的六次方-1.
