LeetCode 周赛上分之旅 #37 多源 BFS 与连通性问题

⭐️ 本文已收录到 AndroidFamily，技能和职场问题，请关注大众号 [彭旭锐] 和 BaguTree Pro 常识星球提问。

学习数据结构与算法的关键在于把握问题背后的算法思想框架，你的思考越抽象，它能覆盖的问题域就越广，了解难度也更杂乱。在这个专栏里，小彭与你共享每场 LeetCode 周赛的解题陈述，一同体会上分之旅。

本文是 LeetCode 上分之旅系列的第 37 篇文章，往期回忆请移步到文章结尾~

周赛 357

T1. 故障键盘（Easy）

• 标签：模仿、字符串

T2. 判别是否能拆分数组（Medium）

• 标签：思想

T3. 找出最安全途径（Medium）

• 标签：BFS、连通性、分层并查集、极大化极小、二分查找

T4. 子序列最大高雅度（Hard）

• 标签：贪心、排序、堆

T1. 故障键盘（Easy）

https://leetcode.cn/problems/faulty-keyboard/

题解（模仿）

简单模仿题。

• 在遇到 i 字符时对已填入字符进行回转，时刻杂乱度是 O(n^2)；
• 运用行列和标记位可以优化时刻杂乱度，在遇到 i 时修正标记位和写入方向，在最终输出时依据标记位输出，避免中间的回转操作。

class Solution {
public:
    string finalString(string s) {
        vector<char> dst;
        for (auto& c : s) {
            if (c == 'i') {
                reverse(dst.begin(), dst.end());
            } else {
                dst.push_back(c);
            }
        }
        return string(dst.begin(), dst.end());
    }
};

class Solution {
public:
    string finalString(string s) {
        deque<char> dst;
        bool rear = true;
        for (auto& c : s) {
            if (c == 'i') {
                rear = !rear;
            } else {
                if (rear) {
                    dst.push_back(c);
                } else {
                    dst.push_front(c);
                }
            }
        }
        return rear ? string(dst.begin(), dst.end()) : string(dst.rbegin(), dst.rend());
    }
};

杂乱度剖析：

• 时刻杂乱度：$O(n)$ 线性遍历和输出时刻；
• 空间杂乱度：$O(n)$ 暂时字符串空间。

T2. 判别是否能拆分数组（Medium）

https://leetcode.cn/problems/check-if-it-is-possible-to-split-array/

题解（思想题）

思想题，主要标题的两个条件只要满意其间一个即可

• 条件 1：子数组的长度为 1 ⇒ 说明数组长度小于等于 2 的时候，必定可以满意（子数组的长度不大于 1）；
• 条件 2：子数组元素之和大于或等于m ⇒ 需满意子数组 {a1, a2, a3} 与 {a4, a5, a6} 的子数组和均大于等于 m。

结合两个条件，假如咱们能找到两个相邻的元素之和大于等于 m，那么总可以经过消除 1 个元素的方式完成标题要求。

例如在示例 3 [2, 3, 3, 2, 3] 中，咱们以 [3,3] 为起点倒推：

• [3, 3]
• [2, 3, 3] 消除 2
• [2, 3, 3, 2] 消除 2
• [2, 3, 3, 2, 3] 消除 3

class Solution {
public:
    bool canSplitArray(vector<int>& nums, int m) {
        // 2 | 3, 3 | 2 | 3
        // 1, 3, 2, 2, 3
        // 1, 1, 1, 3, 3
        if (nums.size() <= 2) return true;
        for (int i = 1; i < nums.size(); i++) {
            if (nums[i] + nums[i - 1] >= m) return true;
        }
        return false;
    }
};

杂乱度剖析：

• 时刻杂乱度：$O(n)$ 线性遍历时刻；
• 空间杂乱度：$O(1)$ 仅运用常量级别空间。

T3. 找出最安全途径（Medium）

https://leetcode.cn/problems/find-the-safest-path-in-a-grid/

题解一（多源 BFS + 二分答案）

依据标题描绘，每个节点的安全系数定位为该节点到「小偷」节点的最小曼哈顿间隔，而标题要求是寻觅从 [0][0] 到 [n-1][n-1] 的最大安全系数。「使得最小曼哈顿间隔最大」暗示可能是需要运用二分答案的极大化极小问题。

• 多源 BFS 预处理： 先从每个「小偷」节点开始走 BFS 更新相邻节点的最小曼哈顿间隔，单次 BFS 的时刻杂乱度是 O(n^2)，虽然咱们可以用剪枝优化，但全体的时刻杂乱度上界是 O(n^4)。为了优化时刻杂乱度，咱们运用多源 BFS（也可以了解为拓扑排序，每次弹出的节点的曼哈顿间隔最小），全体的时刻仅为 O(n^2)；
• 二分答案： 安全系数与途径可达性存在单调性：
  • 当安全系数越大时，越不简单可达；
  • 当安全系数越小时，越简单可达。
  • 安全系数的下界为 0，上界为 n * 2 – 1，经过二分答案寻觅满意可达性的最大安全系数：

class Solution {
    fun maximumSafenessFactor(grid: List<List<Int>>): Int {
        val INF = Integer.MAX_VALUE
        val directions = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))
        val n = grid.size
        // 特判
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return 0
        // 多源 BFS（拓扑排序）
        val safe = Array(n) { IntArray(n) { -1 }}
        var queue = LinkedList<IntArray>()
        for (r in 0 until n) {
            for (c in 0 until n) {
                if (grid[r][c] == 1) {
                    queue.offer(intArrayOf(r, c))
                    safe[r][c] = 0
                }
            }
        }
        while (!queue.isEmpty()) {
            val temp = LinkedList<IntArray>()
            for (node in queue) {
                for (direction in directions) {
                    val newX = node[0] + direction[0]
                    val newY = node[1] + direction[1]
                    if (newX < 0 || newX >= n || newY < 0 || newY >= n || safe[newX][newY] != -1) continue
                    temp.offer(intArrayOf(newX, newY))
                    safe[newX][newY] = safe[node[0]][node[1]] + 1
                }
            }
            queue = temp
        }
        // for (row in safe) println(row.joinToString())
        // BFS（查看只经过大于等于 limit 的格子，能否抵达结尾）
        fun check(limit: Int) : Boolean {
            val visit = Array(n) { BooleanArray(n) }
            var queue = LinkedList<IntArray>()
            queue.offer(intArrayOf(0, 0))
            visit[0][0] = true
            while (!queue.isEmpty()) {
                val temp = LinkedList<IntArray>()
                for (node in queue) {
                    // 终止条件
                    if (node[0] == n - 1 && node[1] == n - 1) return true
                    for (direction in directions) {
                        val newX = node[0] + direction[0]
                        val newY = node[1] + direction[1]
                        if (newX < 0 || newX >= n || newY < 0 || newY >= n || visit[newX][newY] || safe[newX][newY] < limit) continue
                        temp.offer(intArrayOf(newX, newY))
                        visit[newX][newY] = true
                    }
                }
                queue = temp
            }
            return false
        }
        // 二分查找
        var left = 0
        var right = Math.min(safe[0][0], safe[n - 1][n - 1])
        while (left < right) {
            val mid = (left + right + 1) ushr 1
            if (!check(mid)) {
                right = mid - 1
            } else {
                left = mid
            }
        }
        return left
    }
}

杂乱度剖析：

• 时刻杂乱度：O(n2⋅lgn2)O(n^2lgn^2)O(n2⋅lgn2) 其间 多源 BFS 时刻为 O(n2)O(n^2)O(n2)，单次查看的 BFS 时刻杂乱度为 O(n2)O(n^2)O(n2)，二分的次数为 lgn2lgn^2lgn2，全体时刻杂乱度是 O(n2⋅lgn2)O(n^2lgn^2)O(n2⋅lgn2)；
• 空间杂乱度：O(n2)O(n^2)O(n2) safe 安全系数矩阵空间。

题解二（多源 BFS + 堆）

思路参阅雪景式的题解。

在题解一预处理的基础上，相同走一次 BFS 也可以算出最大安全系数，思路类似于 Dijkstra 最最短路算法中运用当时最短路最短的节点去松懈相邻边，咱们优先让当时曼哈顿间隔最大的节点去松懈相邻节点，以保证每个节点都可以从较大的途径搬运过来。

class Solution {
    fun maximumSafenessFactor(grid: List<List<Int>>): Int {
        ...
        // 类最短路（运用曼哈顿间隔最大的节点去松懈相邻边）
        val heap = PriorityQueue<IntArray>() { e1, e2 ->
            e2[0] - e1[0]
        }
        heap.offer(intArrayOf(safe[0][0], 0, 0))
        val visit = Array(n) { BooleanArray(n) }
        visit[0][0] = true
        while (!heap.isEmpty()) {
            val node = heap.poll()
            if (node[1] == n - 1 && node[2] == n - 1) return node[0]
            for (direction in directions) {
                val newX = node[1] + direction[0]
                val newY = node[2] + direction[1]
                if (newX < 0 || newX >= n || newY < 0 || newY >= n || visit[newX][newY]) continue
                // 松懈相邻边
                heap.offer(intArrayOf(Math.min(node[0], safe[newX][newY]), newX, newY))
                visit[newX][newY] = true
            }
        }
        return 0
    }
}

杂乱度剖析：

• 时刻杂乱度：O(n2⋅lgn2)O(n^2lgn^2)O(n2⋅lgn2) 其间 多源 BFS 时刻为 O(n2)O(n^2)O(n2)，根据堆的 BFS 的时刻杂乱度为 O(n2⋅lgn2)O(n^2lgn^2)O(n2⋅lgn2)；
• 空间杂乱度：O(n2)O(n^2)O(n2) safe 安全系数矩阵空间。

题解三（多源 BFS + 分层并查集）

思路参阅灵神的题解。

其实，求从 [0][0] 到 [n – 1][n – 1] 的最大安全系数，也相当于连通性问题的变形，而连通性问题有并查集的解法。为了求得最大安全系数，咱们运用分层并查集：

• 首先，在预处理阶段求出每个节点的最小曼哈顿间隔，并将节点依照曼哈顿间隔分类；
• 其次，咱们从最大的曼哈顿间隔开始逆序兼并，当 [0][0] 和 [n – 1][n – 1] 连通时回来成果。

class Solution {
    fun maximumSafenessFactor(grid: List<List<Int>>): Int {
        val directions = arrayOf(intArrayOf(0,1), intArrayOf(1,0), intArrayOf(0,-1), intArrayOf(-1,0))
        val n = grid.size
        // 特判
        if (grid[0][0] == 1 || grid[n - 1][n - 1] == 1) return 0
        // 多源 BFS（拓扑排序）
        val safe = Array(n) { IntArray(n) { -1 }}
        // 分层
        val groups = LinkedList<LinkedList<IntArray>>()
        var queue = LinkedList<IntArray>()
        for (r in 0 until n) {
            for (c in 0 until n) {
                if (grid[r][c] == 1) {
                    queue.offer(intArrayOf(r, c))
                    safe[r][c] = 0
                }
            }
        }
        groups.add(queue)
        while (!queue.isEmpty()) {
            val temp = LinkedList<IntArray>()
            for (node in queue) {
                for (direction in directions) {
                    val newX = node[0] + direction[0]
                    val newY = node[1] + direction[1]
                    if (newX < 0 || newX >= n || newY < 0 || newY >= n || safe[newX][newY] != -1) continue
                    temp.offer(intArrayOf(newX, newY))
                    safe[newX][newY] = safe[node[0]][node[1]] + 1
                }
            }
            queue = temp
            if (!queue.isEmpty()) groups.add(queue)
        }
        // for (row in safe) println(row.joinToString())
        // for (row in groups) println(row.joinToString())
        val helper = UnionFind(n)
        // 逆序兼并
        for (i in groups.size - 1 downTo 0) {
            for (node in groups[i]) {
                val x = node[0]
                val y = node[1]
                for (direction in directions) {
                    val newX = x + direction[0]
                    val newY = y  + direction[1]
                    // 兼并曼哈顿间隔大于等于当时层的节点
                    if (newX < 0 || newX >= n || newY < 0 || newY >= n || safe[newX][newY] < i) continue
                    helper.union(x * n + y, newX * n + newY)
                }
            }
            if (helper.find(0) == helper.find(n * n - 1)) return i
        }
        return 0
    }
    class UnionFind(private val n: Int) {
        private val parents = IntArray(n * n) { it }
        private val ranks = IntArray(n * n)
        fun find(x: Int): Int {
            var cur = x
            while (cur != parents[cur]) {
                parents[cur] = parents[parents[cur]]
                cur = parents[cur]
            }
            return cur
        }
        fun union(x: Int, y: Int) {
            val rootX = find(x)
            val rootY = find(y)
            if (ranks[rootX] < ranks[rootY]) {
                parents[rootX] = rootY
            } else if (ranks[rootX] > ranks[rootY]){
                parents[rootY] = rootX
            } else {
                parents[rootY] = rootX
                ranks[rootX]++
            }
        }
    }
}

杂乱度剖析：

• 时刻杂乱度：O(n2)O(n^2)O(n2) 其间 多源 BFS 时刻为 O(n2)O(n^2)O(n2)，根据途径紧缩和按秩兼并的并查集时刻杂乱度为 O(n2)O(n^2)O(n2)；
• 空间杂乱度：O(n2)O(n^2)O(n2) safe 安全系数矩阵空间。

T4. 子序列最大高雅度（Hard）

https://leetcode.cn/problems/maximum-elegance-of-a-k-length-subsequence/

题解（反悔贪心 + 堆）

• 固定一个维度： 标题定义的高雅度 total_profit + distinct_categories^2 存在两个维度的变量，咱们考虑固定其间一个维度来简化问题评论：
  • 对所有节点依照赢利从大到小逆序摆放，并挑选前 k 个节点，此刻的 total_profit 是最大的；
  • 在此基础上，咱们持续遍历剩余的 n – k 个节点，并考虑替换前 k 个节点中的某个节点，因为已经挑选的节点 total_profit 是最大的，因此需要让替换后的类目数变多。
• 分类评论（替换哪个）：
  • 1、假如某个已选节点与第 i 个节点的类目相同，那么替换后不会让类目数变大，不行能让高雅度变大；
  • 2、假如某个已选节点与第 i 个节点的类目不同，但只出现一次，那么替换出不会让类目变大，不行能让高雅度变大。否则，假如出现多次，替换后类目数变大，有可能让高雅度变大；
  • 3、为了让高雅度尽可能大，咱们期望替换后的 total_profit 的减少数尽可能小，一起数目类别应该增大，否则无法获得更大的高雅度。为了让替换后的 total_profit 的减少数尽可能小，咱们应该替换已选列表中赢利最小一起重复的节点。
• 怎样高效替换：
  • 运用堆维护赢利最小一起重复的元素，因为咱们是从大到小线性枚举的，因此直接运用线性表模仿堆的才能；
  • 新替换进去的不会被替换出去（想想为什么）。

class Solution {
    fun findMaximumElegance(items: Array<IntArray>, k: Int): Long {
        Arrays.sort(items) { e1, e2 ->
            e2[0] - e1[0]
        }
        var ret = 0L
        var totalProfit = 0L
        // duplicate：小顶堆
        val duplicate = LinkedList<Int>()
        // categorySet：类目表
        val categorySet = HashSet<Int>()
        for ((i, item) in items.withIndex()) {
            val profit = item[0]
            val category = item[1]
            if (i < k) {
                totalProfit += item[0]
                // 记录重复节点
                if (categorySet.contains(category)) {
                    duplicate.add(profit)
                }
                categorySet.add(category)
            } else if (!duplicate.isEmpty() && !categorySet.contains(category)){
                // 替换
                totalProfit += profit - duplicate.pollLast()
                categorySet.add(category)
            } else {
                // 不会让类目数量变大
            }
            // println(duplicate.joinToString())
            ret = Math.max(ret, totalProfit + 1L * categorySet.size * categorySet.size)
        }
        return ret
    }
}

杂乱度剖析：

• 时刻杂乱度：$O(nlgn)$ 瓶颈在排序；
• 空间杂乱度：$O(n)$ 堆空间。

推荐阅览

LeetCode 上分之旅系列往期回忆：

• LeetCode 单周赛第 356 场 KMP 字符串匹配殊途同归
• LeetCode 单周赛第 355 场 两题坐牢，菜鸡现出原形
• LeetCode 双周赛第 109 场 按部就班地解决动态规划问题
• LeetCode 双周赛第 107 场 很有意思的 T2 题

⭐️ 永远相信夸姣的事情行将产生，欢迎加入小彭的 Android 交流社群~