成都网站建设 川icp备,17做网店网站,广州建网站比较有名的公司,大学生跨境电商策划书范文文章目录1. 题目2. 解题1. 题目
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights #xff0c;其中 heights[row][col] 表示格子 (row, col) 的高度。 一开始你在最左上角的格子 (0, 0) #xff0c;且你希望去最右下角的格子 (rows-1, columns-1) …
文章目录1. 题目2. 解题1. 题目
你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights 其中 heights[row][col] 表示格子 (row, col) 的高度。 一开始你在最左上角的格子 (0, 0) 且你希望去最右下角的格子 (rows-1, columns-1) 注意下标从 0 开始编号。 你每次可以往 上下左右 四个方向之一移动你想要找到耗费 体力 最小的一条路径。
一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。
请你返回从左上角走到右下角的最小 体力消耗值 。
示例 1
输入heights [[1,2,2],[3,8,2],[5,3,5]]
输出2
解释路径 [1,3,5,3,5] 连续格子的差值绝对值最大为 2 。
这条路径比路径 [1,2,2,2,5] 更优因为另一条路劲差值最大值为 3 。示例 2
输入heights [[1,2,3],[3,8,4],[5,3,5]]
输出1
解释路径 [1,2,3,4,5] 的相邻格子差值绝对值最大为 1 比路径 [1,3,5,3,5] 更优。示例 3
输入heights [[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]]
输出0
解释上图所示路径不需要消耗任何体力。提示
rows heights.length
columns heights[i].length
1 rows, columns 100
1 heights[i][j] 10^6来源力扣LeetCode 链接https://leetcode-cn.com/problems/path-with-minimum-effort 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 1102. 得分最高的路径优先队列BFS/极大极小化 二分查找 LeetCode 410. 分割数组的最大值极小极大化 二分查找 LeetCode 774. 最小化去加油站的最大距离极小极大化 二分查找 LeetCode 875. 爱吃香蕉的珂珂二分查找 LeetCode LCP 12. 小张刷题计划二分查找 LeetCode 1011. 在 D 天内送达包裹的能力二分查找 LeetCode 1062. 最长重复子串二分查找 LeetCode 5438. 制作 m 束花所需的最少天数二分查找 LeetCode 5489. 两球之间的磁力极小极大化 二分查找
套路二分模板题
class Solution {int m, n;vectorvectorint dir {{1,0},{0,1},{0,-1},{-1,0}};
public:int minimumEffortPath(vectorvectorint heights) {m heights.size(), n heights[0].size();int l 0, r 1e6, mid, ans 0;while(l r){mid l ((r-l)1);vectorvectorbool vis(m, vectorbool(n,false));if(dfs(heights, vis, 0, 0, mid))//有一条路径相邻的数字差都小于mid{r mid-1;ans mid;}elsel mid1;}return ans;}bool dfs(vectorvectorint heights, vectorvectorbool vis, int x, int y, int d){if(x m-1 y n-1)return true;vis[x][y] true;int i, j, k;for(k 0; k 4; k){i x dir[k][0];j y dir[k][1];if(i0 im j0 jn !vis[i][j] abs(heights[x][y]-heights[i][j]) d){if(dfs(heights, vis, i, j, d))return true;}}return false;}
};440 ms 24 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
