Leetcode1631最小体力消耗路径--三种思路

Love The Way You Lie 2022-10-24 06:05 93阅读 0赞

# Leetcode1634最小体力消耗路径 #

## 思路一、暴力(回溯法) ##

说明:此方法时间复杂度太大,不能通过测试,仅仅作为参考

class Solution {
        
        public int minimumEffortPath(int[][] heights) {
        
        	m=heights.length;
        	n=heights[0].length;
        	visited=new int[m][n];
        	res=Integer.MAX_VALUE;
        	dfs(0,0,heights[0][0],0,heights);
        	return res;
        }
        //回溯法
        void dfs(int x,int y,int lastNum,int curMax,int[][] heights) {
        
        	curMax=Math.max(Math.abs(heights[x][y]-lastNum),curMax);
        	if(x==m-1 && y==n-1) {
        
        		res=Math.min(res, curMax);
        		return;
        	}
        	for(int i=0;i<4;i++) {
        
        		if(x+dfsX[i]>=0 && x+dfsX[i]<m &&y+dfsY[i]>=0 && y+dfsY[i]<n && visited[x+dfsX[i]][y+dfsY[i]]==0) {
        
        				visited[x][y]=1;
        				dfs(x+dfsX[i],y+dfsY[i],heights[x][y],curMax,heights);
        				visited[x][y]=0;
        		}
        	}
        	return;
        }
        
        
        int res;
        int[][] visited;
        int m,n;
        int[] dfsX=new int[] {
        0,1,0,-1};
        int[] dfsY=new int[] {
        1,0,-1,0};
    }

## 思路二、Dijkstra算法 ##

众所周知，网格本身就是一张图,求图中两点间的最短距离dj算法首当其冲,虽然这种算法复杂度比较高，但是其通用性却是显而易见的。  
代码在leetcode中刚好通过测试

class Solution {
        
        public int minimumEffortPath(int[][] heights) {
        
        	//dj算法
        	int m=heights.length;
        	int n=heights[0].length;
        	int[] visited=new int[m*n];
        	int[] weight=new int[m*n];
        	for(int i=1;i<m*n;i++) {
        
        		weight[i]=Integer.MAX_VALUE;
        	}
        	//初始化权值
        	for(int i=1;i<m*n;i++) {
        
        		int minNode=0,min=Integer.MAX_VALUE;
        		//寻找最小边
        		for(int j=0;j<m*n;j++) {
        
        			if(visited[j]==0 && weight[j]<min) {
        
        				min=weight[j];
        				minNode=j;
        			}
        		}
        		if(minNode==m*n-1) break;
        		visited[minNode]=1;
        		//将结点化为2维坐标
        		int x=minNode/n;
        		int y=minNode%n;
        		//更新权值
        		for(int j=0;j<4;j++) {
        
        			int nextX=x+dfsX[j]; int nextY=y+dfsY[j];
        			if(nextX>=0 && nextX<m && nextY>=0 && nextY<n) {
        
        				int index=nextX*n+nextY;
        				if(visited[index]==1) continue;
        				int w=Math.abs(heights[x][y]-heights[nextX][nextY]);
                        w=Math.max(min, w);
        				weight[index]=Math.min(weight[index], w);
        			}
        		}
        	}
        	return weight[m*n-1];
        }
        int[] dfsX=new int[] {
        0,1,0,-1};
        int[] dfsY=new int[] {
        1,0,-1,0};
    }

## 思路三、贪心+并查集 ##

说明:此思路是基于贪心+并查集解决的,想法很巧妙。我们首先将网格抽象成一张图，对于图的边的权值即为两节点间的体力值。我们可以将所有的边存入优先队列中，然会逐渐按权值从小到大合并边所对应的两个结点，直到起点和终点可以恰好连通，则让起点终点恰好连通的边的权即为消耗的最小体力值。  
代码(代码摘录自leetcode官方):

class Solution {
        
        public int minimumEffortPath(int[][] heights) {
        
            int m = heights.length;
            int n = heights[0].length;
            List<int[]> edges = new ArrayList<int[]>();
            for (int i = 0; i < m; ++i) {
        
                for (int j = 0; j < n; ++j) {
        
                    int id = i * n + j;
                    if (i > 0) {
        
                        edges.add(new int[]{
        id - n, id, Math.abs(heights[i][j] - heights[i - 1][j])});
                    }
                    if (j > 0) {
        
                        edges.add(new int[]{
        id - 1, id, Math.abs(heights[i][j] - heights[i][j - 1])});
                    }
                }
            }
            Collections.sort(edges, new Comparator<int[]>() {
        
                public int compare(int[] edge1, int[] edge2) {
        
                    return edge1[2] - edge2[2];
                }
            });
    
            UnionFind uf = new UnionFind(m * n);
            int ans = 0;
            for (int[] edge : edges) {
        
                int x = edge[0], y = edge[1], v = edge[2];
                uf.unite(x, y);
                if (uf.connected(0, m * n - 1)) {
        
                    ans = v;
                    break;
                }
            }
            return ans;
        }
    }
    
    // 并查集模板
    class UnionFind {
        
        int[] parent;
        int[] size;
        int n;
        // 当前连通分量数目
        int setCount;
    
        public UnionFind(int n) {
        
            this.n = n;
            this.setCount = n;
            this.parent = new int[n];
            this.size = new int[n];
            Arrays.fill(size, 1);
            for (int i = 0; i < n; ++i) {
        
                parent[i] = i;
            }
        }
        
        public int findset(int x) {
        
            return parent[x] == x ? x : (parent[x] = findset(parent[x]));
        }
        
        public boolean unite(int x, int y) {
        
            x = findset(x);
            y = findset(y);
            if (x == y) {
        
                return false;
            }
            if (size[x] < size[y]) {
        
                int temp = x;
                x = y;
                y = temp;
            }
            parent[y] = x;
            size[x] += size[y];
            --setCount;
            return true;
        }
        
        public boolean connected(int x, int y) {
        
            x = findset(x);
            y = findset(y);
            return x == y;
        }
    }