龙空技术网

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

彭旭锐 40

前言:

现在小伙伴们对“bfs时间复杂度分析”大致比较着重,同学们都想要剖析一些“bfs时间复杂度分析”的相关资讯。那么小编在网络上网罗了一些有关“bfs时间复杂度分析””的相关知识,希望兄弟们能喜欢,小伙伴们快快来了解一下吧!

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

学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。

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

T1. 故障键盘(Easy)

标签:模拟、字符串

T2. 判断是否能拆分数组(Medium)

标签:思维

T3. 找出最安全路径(Medium)

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

T4. 子序列最大优雅度(Hard)

标签:贪心、排序、堆T1. 故障键盘(Easy)

题解(模拟)

简单模拟题。

在遇到 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)

题解(思维题)

思维题,主要题目的两个条件只要满足其中一个即可

条件 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)

题解一(多源 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(n^2·lgn^2) 其中 多源 BFS 时间为 O(n^2),单次检查的 BFS 时间复杂度为 O(n^2),二分的次数为 lgn^2,整体时间复杂度是 O(n^2·lgn^2);空间复杂度:O(n^2) 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(n^2·lgn^2) 其中 多源 BFS 时间为 O(n^2),基于堆的 BFS 的时间复杂度为 O(n^2·lgn^2);空间复杂度:O(n^2) 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(n^2) 其中 多源 BFS 时间为 O(n^2),基于路径压缩和按秩合并的并查集时间复杂度为 O(n^2);空间复杂度:O(n^2) safe 安全系数矩阵空间。T4. 子序列最大优雅度(Hard)

题解(反悔贪心 + 堆)固定一个维度: 题目定义的优雅度 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 交流社群~

标签: #bfs时间复杂度分析