算法-并查集/堆/Dijkstra迪杰斯特拉-水位上升的泳池中游泳

今天药忘吃喽~ 2022-10-25 12:56 119阅读 0赞

# 算法-并查集/堆/Dijkstra迪杰斯特拉-水位上升的泳池中游泳 #

# 1 题目概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/swim-in-rising-water/

## 1.2 题目描述 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]

# 2 并查集 #

## 2.1 思路 ##

注意，平台数字是连续的，且从0到n*n-1。则可利用这一特点，从高度1的节点开始，不断和周边比他高度小的节点进行并查集合并。每次遍历后，判断0和n*n-1所属并查集是否为同一个祖先，如果是代表已经符合要求，返回遍历的轮数即可（轮数从1开始）。

## 2.2 代码 ##

class Solution { 
        public int swimInWater(int[][] grid) { 
            int n = grid.length;
    
            // 并查集
            // 每个坐标，按行号*行数n + 列数 得到一个唯一坐标数，[0, n*n)
            int[] f = new int[n * n];
            for (int i = 0; i < n * n; i++) { 
                // 并查集初始值为本身
                f[i] = i;
            }
    
            // 每个平台高度对应的坐标，x和y
            int[][] idx = new int[n * n][2]; 
            for (int i = 0; i < n; i++) { 
                for (int j = 0; j < n; j++) { 
                    idx[grid[i][j]][0] = i;
                    idx[grid[i][j]][1] = j;
                }
            }
    
            // 四个方向，上下左右
            int[][] directions = { { 0, 1}, { 0, -1}, { 1, 0}, { -1, 0}};
    
            // 从高度1到n*n遍历
            for (int threshold = 1; threshold < n * n; threshold++) { 
                int i = idx[threshold][0], j = idx[threshold][1];
                // 遍历四个方向
                for (int[] direction : directions) { 
                    int ni = i + direction[0], nj = j + direction[1];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n && grid[ni][nj] <= threshold) { 
                        // 当邻居坐标合法，且邻居平台高度小于当前凭条高度
                        // 就合并两个高度，即淹没了这两个平台
                        merge(f, i * n + j, ni * n + nj);
                    }
                }
                // 当0号和最后一个平台坐标的祖先相同，说明已经可达
                // 返回当前高度即可
                if (search(f, 0) == search(f, n * n - 1)) { 
                    return threshold;
                }
            }
            return -1; 
        }
    
        public int search(int[] f, int x) { 
            if (f[x] == x) { 
                // 如果祖先就是自己，则说明x就是该并查集祖先，直接返回
                return x;
            }
            // 否则继续查找f[x]的祖先，且把该祖先赋值给f[x]，压缩路径空间
            return f[x] = search(f, f[x]);
        }
    
        public void merge(int[] f, int x, int y) { 
            // 合并两个并查集
            // 查找他们的祖先
            int fx = search(f, x), fy = search(f, y);
            // 将一个并查集的祖先的祖先设为另一个并查集祖先，即完成合并
            f[fx] = fy;
        }
    }

## 2.3 时间复杂度 ##

![在这里插入图片描述][20210131200744257.png]

## 2.4 空间复杂度 ##

`O(N^2)`

# 3 堆 #

## 3.1 思路 ##

从0节点开始，每次将紧邻的4个节点放入堆。堆按高度越小越优先。

每次从堆中取出高度最小的，更新结果值，并继续上述过程。

当访问到n-1, n-1坐标时，结束。

## 3.2 代码 ##

class Solution { 
        public int swimInWater(int[][] grid) { 
            int n = grid.length;
            // 优先级队列，高度小的优先
            PriorityQueue<Entry> pq = new PriorityQueue<Entry>(new Comparator<Entry>() { 
                public int compare(Entry entry1, Entry entry2) { 
                    return entry1.height - entry2.height;
                }
            });
            // 初始将0号位置放入队列
            pq.offer(new Entry(0, 0, grid[0][0]));
    
            // 记录已经访问过的位置
            boolean[][] visited = new boolean[n][n];
    
            // 每次寻找的四个方向
            int[][] directions = { { 0, 1}, { 0, -1}, { 1, 0}, { -1, 0}};
    
            // 结果
            int result = 0;
           
            while (!pq.isEmpty()) { 
                Entry x = pq.poll();
                if (visited[x.i][x.j]) { 
                    // 已访问的节点跳过
                    continue;
                }
                // 标记当前节点已访问
                visited[x.i][x.j] = true;
    
                // 访问一次就更新一次结果高度
                // 这里必须取最大值，而不是直接去x.height
                // 因为我们是从原点开始访问的，但周边的点可能都比当前点小
                result = Math.max(result, x.height);
                
                // 当已经到达目标尾节点，结束遍历
                if (x.i == n - 1 && x.j == n - 1) { 
                    break;
                }
    
                // 遍历四个方向，将他们放入优先级队列，下次遍历时按高度更小优先的原则进行访问
                for (int[] direction : directions) { 
                    int ni = x.i + direction[0], nj = x.j + direction[1];
                    if (ni >= 0 && ni < n && nj >= 0 && nj < n) { 
                        if (!visited[ni][nj]) { 
                            pq.offer(new Entry(ni, nj, grid[ni][nj]));
                        }
                    }
                }
            }
            return result;
        }
    }
    
    // 优先队列中的数据结构
    // i,j 代表坐标，
    // height 代表水位。
    class Entry { 
        int i;
        int j;
        int height;
    
        public Entry(int i, int j, int height) { 
            this.i = i;
            this.j = j;
            this.height = height;
        }
    };

## 3.3 时间复杂度 ##

![在这里插入图片描述][20210131214823761.png]  
![在这里插入图片描述][20210131214840581.png]

## 3.4 空间复杂度 ##

`O(N^2)`

# 4 Dijkstra迪杰斯特拉 #

## 4.1 思路 ##

*  [代码][Link 1]
 *  [Dijkstra算法][Dijkstra]

## 4.2 代码 ##

## 4.3 时间复杂度 ##

## 4.4 空间复杂度 ##

# 参考文档 #

*  [ 水位上升的泳池中游泳][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JhaWNob3VmZWk5MA_size_16_color_FFFFFF_t_70]: /images/20221024/2b4aaceb30334833a343f647e406fc0d.png
[20210131200744257.png]: /images/20221024/06c9cc37c91e4287b5c41fcdef6ce953.png
[20210131214823761.png]: /images/20221024/0886514841ef4098907a81a449c7adb8.png
[20210131214840581.png]: /images/20221024/0851b73fc157408881f2a97d7f267ede.png
[Link 1]: https://leetcode-cn.com/problems/swim-in-rising-water/solution/shui-wei-shang-sheng-de-yong-chi-zhong-y-862o/
[Dijkstra]: https://blog.csdn.net/yalishadaa/article/details/55827681