关于后端:934-最短的桥-并查集-双向-BFS-运用题

47次阅读

共计 5049 个字符，预计需要花费 13 分钟才能阅读完成。

题目形容

这是 LeetCode 上的 934. 最短的桥 ，难度为 中等。

Tag :「并查集」、「双向 BFS」

给你一个大小为 n x n 的二元矩阵 grid，其中 1 示意海洋，0 示意水域。

岛 是由四面相连的 1 造成的一个最大组，即不会与非组内的任何其余 1 相连。grid 中 恰好存在两座岛。

你能够将任意数量的 0 变为 1，以使两座岛连接起来，变成 一座岛。

返回必须翻转的 0 的最小数目。

示例 1：

输出：grid = [[0,1],[1,0]]

输入：1

示例 2：

输出：grid = [[0,1,0],[0,0,0],[0,0,1]]

输入：2

示例 3：

输出：grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]

输入：1

提醒：

  • $n = grid.length = grid[i].length$
  • $2 <= n <= 100$
  • grid[i][j] 为 0 或 1
  • grid 中恰有两个岛

并查集 + 双向 BFS

应用「并查集」将两个岛标记进去，而后将两个岛的点别离入队，再使用「双向 BFS」来找最短通路。

为了不便，咱们将 grid 记为 g。

对于所有满足 $g[i][j] = 1$ 的节点与其四联通的方向，值同为 $1$ 的节点进行并查集连通性保护。

随后建设两个队列 d1 和 d2 别离存储两个岛的节点（以二元组 $(x, y)$ 的形式出入队），并应用两个哈希表 m1 和 m2 来记录从两岛屿登程达到该节点所耗费的步数（以节点的一维编号为 key，以耗费步数为 value）。

最初是应用「双向 BFS」来求解使两岛屿联通的最小通路：每次从队列中较少的进行拓展，只有尚未被解决过的节点（没有被以后哈希表所记录）才进行入队并更新耗费步数，当拓展节点在另外一个队列对应的哈希表表中呈现过，阐明找到了最短通路。

Java 代码：

class Solution {
    static int N = 10010;
    static int[] p = new int[N];
    static int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
    int n;
    int getIdx(int x, int y) {return x * n + y;}
    int find(int x) {if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }
    void union(int x, int y) {p[find(x)] = p[find(y)];
    }
    public int shortestBridge(int[][] g) {
        n = g.length;
        for (int i = 0; i <= n * n; i++) p[i] = i;
        for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (g[i][j] == 0) continue;
                for (int[] di : dirs) {int x = i + di[0], y = j + di[1];
                    if (x < 0 || x >= n || y < 0 || y >= n) continue;
                    if (g[x][y] == 0) continue;
                    union(getIdx(i, j), getIdx(x, y));
                }
            }
        }
        int a = -1, b = -1;
        Deque<int[]> d1 = new ArrayDeque<>(), d2 = new ArrayDeque<>();
        Map<Integer, Integer> m1 = new HashMap<>(), m2 = new HashMap<>();
        for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (g[i][j] == 0) continue;
                int idx = getIdx(i, j), root = find(idx);
                if (a == -1) a = root;    
                else if (a != root && b == -1) b = root;
                if (root == a) {d1.addLast(new int[]{i, j});
                    m1.put(idx, 0);
                } else if (root == b) {d2.addLast(new int[]{i, j});
                    m2.put(idx, 0);
                }
            }
        }
        while (!d1.isEmpty() && !d2.isEmpty()) {
            int t = -1;
            if (d1.size() < d2.size()) t = update(d1, m1, m2);
            else t = update(d2, m2, m1);
            if (t != -1) return t - 1;
        }
        return -1; // never
    }
    int update(Deque<int[]> d, Map<Integer, Integer> m1, Map<Integer, Integer> m2) {int sz = d.size();
        while (sz-- > 0) {int[] info = d.pollFirst();
            int x = info[0], y = info[1], idx = getIdx(x, y), step = m1.get(idx);
            for (int[] di : dirs) {int nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny);
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
                if (m1.containsKey(nidx)) continue;
                if (m2.containsKey(nidx)) return step + 1 + m2.get(nidx);
                d.addLast(new int[]{nx, ny});
                m1.put(nidx, step + 1);
            }
        }
        return -1;
    }
}

TypeScript 代码：

let n: number
const p = new Array<number>(10010).fill(0)
const dirs = [[0,1],[0,-1],[1,0],[-1,0]]
function shortestBridge(g: number[][]): number {function getIdx(x: number, y: number): number {return x * n + y}
    function find(x: number): number {if (p[x] != x) p[x] = find(p[x])
        return p[x]
    }
    function union(x: number, y: number): void {p[find(x)] = p[find(y)]
    }
    function update(d: Array<Array<number>>, m1: Map<number, number>, m2: Map<number, number>): number {
        let sz = d.length
        while (sz-- > 0) {const info = d.shift()
            const x = info[0], y = info[1], idx = getIdx(x, y), step = m1.get(idx)
            for (const di of dirs) {const nx = x + di[0], ny = y + di[1], nidx = getIdx(nx, ny)
                if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue
                if (m1.has(nidx)) continue
                if (m2.has(nidx)) return step + 1 + m2.get(nidx)
                d.push([nx, ny])
                m1.set(nidx, step + 1)
            }
        }
        return -1
    }
    n = g.length
    for (let i = 0; i < n * n; i++) p[i] = i
    for (let i = 0; i < n; i++) {for (let j = 0; j < n; j++) {if (g[i][j] == 0) continue
            for (const di of dirs) {const x = i + di[0], y = j + di[1]
                if (x < 0 || x >= n || y < 0 || y >= n) continue
                if (g[x][y] == 0) continue
                union(getIdx(i, j), getIdx(x, y))
            }
        }
    }
    let a = -1, b = -1
    const d1 = new Array<number[]>(), d2 = new Array<number[]>()
    const m1 = new Map<number, number>(), m2 = new Map<number, number>()
    for (let i = 0; i < n; i++) {for (let j = 0; j < n; j++) {if (g[i][j] == 0) continue
            const idx = getIdx(i, j), root = find(idx)
            if (a == -1) a = root
            else if (a != root && b == -1) b = root
            if (a == root) {d1.push([i, j])
                m1.set(idx, 0)
            } else if (b == root) {d2.push([i, j])
                m2.set(idx, 0)
            }
        }
    }
    while (d1.length != 0 && d2.length != 0) {
        let t = -1
        if (d1.length < d2.length) t = update(d1, m1, m2)
        else t = update(d2, m2, m1)
        if (t != -1) return t - 1
    }
    return -1
}

Python 代码：

import queue

class Solution:
    def shortestBridge(self, g: List[List[int]]) -> int:
        def getIdx(x, y):
            return x * n + y

        def find(x):
            if p[x] != x:
                p[x] = find(p[x])
            return p[x]

        def union(x, y):
            p[find(x)] = p[find(y)]

        def update(d, cur, other):
            sz = d.qsize()
            while sz != 0:
                x, y = d.get()
                idx, step = getIdx(x, y), cur.get(getIdx(x, y))
                for di in dirs:
                    nx, ny = x + di[0], y + di[1]
                    nidx = getIdx(nx, ny)
                    if nx < 0 or nx >= n or ny < 0 or ny >= n:
                        continue
                    if nidx in cur:
                        continue
                    if nidx in other:
                        return step + 1 + other.get(nidx)
                    d.put([nx, ny])
                    cur[nidx] = step + 1
                sz -= 1
            return -1

        n = len(g)
        p = [i for i in range(n * n + 10)]
        dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
        for i in range(n):
            for j in range(n):
                if g[i][j] == 0:
                    continue
                for di in dirs:
                    x, y = i + di[0], j + di[1]
                    if x < 0 or x >= n or y < 0 or y >= n:
                        continue
                    if g[x][y] == 0:
                        continue
                    union(getIdx(i, j), getIdx(x, y))
        a, b = -1, -1
        d1, d2 = queue.Queue(), queue.Queue()
        m1, m2 = {}, {}
        for i in range(n):
            for j in range(n):
                if g[i][j] == 0:
                    continue
                idx, root = getIdx(i, j), find(getIdx(i, j))
                if a == -1:
                    a = root
                elif a != root and b == -1:
                    b = root
                if a == root:
                    d1.put([i, j])
                    m1[idx] = 0
                elif b == root:
                    d2.put([i, j])
                    m2[idx] = 0
        while not d1.empty() and not d2.empty():
            t = -1
            if d1.qsize() < d2.qsize():
                t = update(d1, m1, m2)
            else:
                t = update(d2, m2, m1)
            if t != -1:
                return t - 1
        return -1
  • 工夫复杂度：$O(n^2)$
  • 空间复杂度：$O(n^2)$

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.934 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

正文完
后端
发表至： 后端
2022-10-25
 0
关于后端:3分钟创建Serverless-Job-定时获取新闻热搜
关于后端:CPT206
关于后端:面试题精讲Java-和-C-的区别
关于后端:更新版PHP家教系统源码请家教网站源码亲测源码自适应手机端