Leetcode 1631 Path With Minimum Effort (python)

题目

解析

这个题目再Leetcode 的problems里面还没有，只出现在Weekly contest 212的第3题

一开始觉得这个题目是个DP，觉得两遍dp可以做，实际上思路错了，两个方向的dp是不行的。
基本上看到四个方向可走的题目就是用最短路径问题来做，最短路径这边也提供两种做法，一种是Bellman ford，另一种是Dijkstra，关于两种做法的详细解释看这题 Leetcode The Maze I,II

Bellman ford 版本

class Solution:def minimumEffortPath(self, heights: List[List[int]]) -> int:m = len(heights)n = len(heights[0])q = collections.deque()q.append((0,0))distances = [[float('inf')]*n for _ in range(m)]distances[0][0] = 0dirs = [[0,1],[1,0],[0,-1],[-1,0]]while q:i,j = q.popleft()for d in dirs:x = i+d[0]y = j+d[1]if 0<=x<m and 0<=y<n and distances[x][y]>max(distances[i][j],abs(heights[x][y]-heights[i][j])):q.append((x,y))distances[x][y] = max(distances[i][j],abs(heights[x][y]-heights[i][j]))return distances[-1][-1] if distances[-1][-1]!=float('inf') else -1

利用heap的Dijkstra

class Solution:def minimumEffortPath(self, heights: List[List[int]]) -> int:m = len(heights)n = len(heights[0])distances = [[float('inf')]*n for _ in range(m)]distances[0][0] = 0dirs = [[0,1],[1,0],[0,-1],[-1,0]]q = [(0,0,0)]while q:dis,i,j = heapq.heappop(q)if i == -1 and j==-1:return disfor d in dirs:x = i+d[0]y = j+d[1]if 0<=x<m and 0<=y<n and distances[x][y]>max(distances[i][j],abs(heights[x][y]-heights[i][j])):distances[x][y] = max(distances[i][j],abs(heights[x][y]-heights[i][j]))heapq.heappush(q,(distances[x][y],x,y))return distances[-1][-1] if distances[-1][-1]!=float('inf') else -1

这两种解法的区别在于，bellman ford实际上就是暴力访问所有可能路径，所以只能等到所有访问结束才能知道结果；但是Dijkstra每次都是greedy的走当前最优的那一步，所以一旦访问到了目标位置，这时候的结果就是最优的

解法3：二分判定

这边运用到了一种思想，就是将搜索问题转化为一个判定问题。由于我们知道所有的数字的上限，所以可以通过二分搜索来查找这个数字。其实这个问题是求min(max)。对于min(max)或者max(min)的问题，一般都可以转化成二分判定来解决。
具体思路如下：

• 将下边界设为0，上边界设为数字的最大值，进行二分搜索
• 搜索的check function是给定一个数字，是否能从左上角走到右下角并且cost等于这个数字

二分判定+BFS

class Solution:def minimumEffortPath(self, heights: List[List[int]]) -> int:def can_reach(mid):q = collections.deque()visited = [[False]*n for _ in range(m)]q.append((0,0))visited[0][0] = Truedirs = [[0,1],[0,-1],[-1,0],[1,0]]while q:i,j = q.popleft()if i == m-1 and j ==n-1:return Truefor d in dirs:x = i+d[0]y = j+d[1]if 0<=x<m and 0<=y<n and not visited[x][y]:diff = abs(heights[x][y]-heights[i][j])if diff<=mid:q.append((x,y))visited[x][y] = Truereturn Falsem,n = len(heights),len(heights[0])lo,hi = 0,10**6while lo+1<hi:mid = lo+(hi-lo)//2if can_reach(mid):hi = midelse:lo=midif can_reach(lo):return loelse:return hi

二分判定+dfs
这边要尤其注意visited数组每次dfs之前都要初始化

class Solution:def minimumEffortPath(self, heights: List[List[int]]) -> int:def can_reach(i,j,mid,visited):# if i<0 or i>=m or j<0 or j>=m or visited[i][j]:# return if i==m-1 and j==n-1:return Truevisited[i][j] = Truedirs = [[0,1],[0,-1],[-1,0],[1,0]]for d in dirs:x = i + d[0]y = j + d[1]if 0 <= x <m and 0 <= y < n and not visited[x][y] and abs(heights[x][y] - heights[i][j]) <= mid:if can_reach(x,y,mid,visited):return Truereturn Falsem,n = len(heights),len(heights[0])visited = [[False]*n for _ in range(m)]#visited[0][0] = Truelo,hi = 0,10**6while lo+1<hi:mid = lo+(hi-lo)//2#print(mid)visited = [[False]*n for _ in range(m)]if can_reach(0, 0, mid, visited):hi = midelse:lo=midvisited = [[False]*n for _ in range(m)]if can_reach(0,0,lo,visited):return loelse:return hi

follow up

这篇博客里有很多类似的题目，留着以后刷
https://blog.csdn.net/qq_21201267/article/details/109274216

二刷

dijkstra

class Solution {
    
public:int minimumEffortPath(vector<vector<int>>& heights) {
    int m = heights.size();int n = heights[0].size();vector<vector<int>> efforts(m,vector<int>(n,INT_MAX));efforts[0][0] = 0;priority_queue<vector<int>,vector<vector<int>>,greater<vector<int>>> pq;pq.push({
    0,0,0});vector<vector<int>> dirs{
    {
    0,1},{
    0,-1},{
    -1,0},{
    1,0}};while(!pq.empty()){
    vector<int> curr = pq.top();pq.pop();int currEffort = curr[0];int i = curr[1];int j = curr[2];for(auto& d : dirs){
    int x = i + d[0];int y = j + d[1];if(x < 0 || y < 0 || x >= m || y >= n) continue;int currDiff = abs(heights[i][j]-heights[x][y]);if(max(currDiff,currEffort) < efforts[x][y]){
    pq.push({
    max(currDiff,currEffort),x,y});efforts[x][y] = max(currDiff,currEffort);}}}return efforts[m-1][n-1];}
};

时间复杂度：O(elog(v)), e=mn, m和n是heights的维度，v=4e，因为只能往四个方向走
空间复杂度：O(mn)
二分判定：

class Solution {
    
public:bool check(vector<vector<int>>& heights, int m, int n, int thd){
    queue<pair<int,int>> q;vector<vector<int>> visited(m,vector<int>(n,0));q.push(make_pair(0,0));visited[0][0] = 1;vector<vector<int>> dirs{
    {
    0,1},{
    0,-1},{
    1,0},{
    -1,0}};while(!q.empty()){
    pair<int,int> curr = q.front();q.pop();// cout << curr.first << " " << curr.second << endl;if(curr.first == m-1 && curr.second == n-1) return true;for(auto& d : dirs){
    int x = curr.first + d[0];int y = curr.second + d[1];if(x < 0 || y < 0 || x >= m || y >= n || visited[x][y] == 1) continue;if(abs(heights[x][y] - heights[curr.first][curr.second]) <= thd){
    q.push(make_pair(x,y));visited[x][y] = 1;}}}return false;}int minimumEffortPath(vector<vector<int>>& heights) {
    int max_num = 0;int m = heights.size();int n = heights[0].size();for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
    max_num = max(max_num,heights[i][j]);}}int left = 0;int right = max_num;if(check(heights,m,n,left)) return left;while(left + 1 < right){
    int mid = left + (right - left) / 2;if(check(heights,m,n,mid)){
    right = mid;}else{
    left = mid;}}return right;}
};

时间复杂度：O(log(M)mn), M为所有高度中的最大值，每次搜索需要mn
空间复杂度：O(mn)