仅供自己学习
题目:
ou are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.
A route's effort is the maximum absolute difference in heights between two consecutive cells of the route.
Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
Example 1:
1 2 2
3 8 2
5 3 5
Input: heights = [[1,2,2],[3,8,2],[5,3,5]]
Output: 2
Explanation: The route of [1,3,5,3,5] has a maximum absolute difference of 2 in consecutive cells.
This is better than the route of [1,2,2,2,5], where the maximum absolute difference is 3.
思路:
可以把该数据转化为图,将每个height视为一个结点,标号为i*n+j ,i 为第几行,n为总列数,j为第几列,m为总行数,然后结点之间连线权重设为两点height之差的绝对值,则可规约为求最短路径的问题。考虑用并查集和Kruskal算法进行。
并查集用于判断两节点是否联通,Kruskal是用来求MST,每一步添加没有加入进树里的最小路径进来,而这最小路径设为height之差,因为Kruskal会对权值升序排序,所以每次取得的最小路径都是不减的,所以当我们每次取最小路径的同时更新最小体力消耗的值,当左上和右下连通后,体力消耗保证最小,并且最小体力消耗值满足是整条路最大height差的定义,即是在整条路中权重最大的,也就是height差在整条路最大的。
代码:
class Djset { public: vector<int> parent; // 记录节点的根 vector<int> rank; // 记录根节点的深度(用于优化) Djset(int n): parent(vector<int>(n)), rank(vector<int>(n)) { for (int i = 0; i < n; i++) { parent[i] = i; } } int find(int x) { // 压缩方式:直接指向根节点 if (x != parent[x]) { parent[x] = find(parent[x]); } return parent[x]; } void merge(int x, int y) { int rootx = find(x); int rooty = find(y); if (rootx != rooty) { // 按秩合并 if (rank[rootx] < rank[rooty]) { swap(rootx, rooty); } parent[rooty] = rootx; if (rank[rootx] == rank[rooty]) rank[rootx] += 1; } } bool isSame(int x, int y) { return find(x) == find(y); } }; //直接调用查并集的模板 struct Edge { int start; // 起点 int end; // 终点 int len; // 权值 }; class Solution { public: int minimumEffortPath(vector<vector<int>>& heights) { int m = heights.size(); int n = heights[0].size(); int Min= 0; vector<Edge> edges; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i + 1 < m) edges.push_back({i * n + j, (i + 1) * n + j, abs(heights[i + 1][j] - heights[i][j])}); if (j + 1 < n) edges.push_back({i * n + j, i * n + j + 1, abs(heights[i][j + 1] - heights[i][j])}); } } //转化为图 sort(edges.begin(), edges.end(), [](auto& a, auto& b){ return a.len < b.len; }); //lambda函数,对图边权进行升序排序 Djset ds(m * n); for (auto& a:edges) { Min= a.len; ds.merge(a.start, a.end); //每次加进来边则设置为同一个leader if (ds.isSame(0, m * n - 1)) break; //如果左上和右下leader相同即相连通,结束 } return minCost; } };