LeetCode 周赛上分之旅 # 37 多源 BFS 与连通性
2023-08-06 本文已影响0人
彭旭锐
周赛 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());
}
};
复杂度分析：
- 时间复杂度：
线性遍历和输出时间；
- 空间复杂度：
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;
}
};
复杂度分析：
- 时间复杂度：
- 空间复杂度：
仅使用常量级别空间。
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
}
}
复杂度分析：
- 时间复杂度：
其中 多源 BFS 时间为
，单次检查的 BFS 时间复杂度为
，整体时间复杂度是
- 空间复杂度：
题解二（多源 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
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
题解三（多源 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]++
}
}
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
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
}
}
复杂度分析：
- 时间复杂度：
瓶颈在排序；
- 空间复杂度：
推荐阅读
LeetCode 上分之旅系列往期回顾：
