LeetCode 周赛上分之旅 #45 精妙的 O(lgn) 扫描算法与树上 DP 问题
LeetCode 周赛上分之旅 #45 精妙的 O(lgn) 扫描算法与树上 DP 问题
⭐️ 本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。 学习数据结构与算法的关键在于掌握问题背后的算法思维框架，你的思考越抽象，它能覆盖的问题域就越广，理解难度也更复杂。在这个专栏里，小彭与你分享每场 LeetCode 周赛的解题报告，一起体会上分之旅。 本文是 LeetCode 上分之旅系列的第 45 篇文章，往期回顾请移步到文章末尾~
T1. 使数组成为递增数组的最少右移次数（Easy）
https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/description/
题解一（暴力枚举）
简单模拟题。
由于题目数据量非常小，可以把数组复制一份拼接在尾部，再枚举从位置
开始长为
的连续循环子数组是否连续，是则返回
：
class Solution {
fun minimumRightShifts(nums: MutableList<Int>): Int {
val n = nums.size
nums.addAll(nums)
for (i in 0 until n) {
if ((i + 1 ..< i + n).all { nums[it] > nums[it - 1]}) return (n - i) % n
}
return -1
}
}
class Solution:
def minimumRightShifts(self, nums: List[int]) -> int:
n = len(nums)
nums += nums
for i in range(0, n):
if all(nums[j] > nums[j - 1] for j in range(i + 1, i + n)):
return (n - i) % n
return -1
复杂度分析：
- 时间复杂度：
双重循环；
- 空间复杂度：
循环数组空间。
题解二（线性遍历）
更优的写法，我们找到第一个逆序位置，再检查该位置后续位置是否全部为升序，且满足
：
class Solution {
fun minimumRightShifts(nums: List<Int>): Int {
val n = nums.size
for (i in 1 until n) {
// 第一段
if (nums[i] >= nums[i - 1]) continue
// 第二段
if (nums[n - 1] > nums[0]) return -1
for (j in i until n - 1) {
if (nums[j] > nums[j + 1]) return -1
}
return n - i
}
return 0
}
}
复杂度分析：
- 时间复杂度：
指针和
指针总计最多移动
次；
- 空间复杂度：
仅使用常量级别空间。
T2. 删除数对后的最小数组长度（Medium）
https://leetcode.cn/problems/minimum-array-length-after-pair-removals/
题解一（二分答案）
问题存在单调性：
- 当操作次数
可以满足时，操作次数
一定能满足；
- 当操作次数
不可满足时，操作次数
一定不能满足。
那么，原问题相当于求解满足目标的最大操作次数。
现在需要考虑的问题是：如何验证操作次数
是否可以完成？
一些错误的思路：
- 尝试 1 - 贪心双指针：
优先使用最小值，
优先使用最大值，错误用例：
；
- 尝试 2 - 贪心：
优先使用最小值，
使用大于
的最小值，错误用例：
；
- 尝试 3 - 贪心： 从后往前遍历，
优先使用较大值，
使用大于
的最小值，错误用例：
。
开始转换思路：
能否将数组拆分为两部分，作为 nums[i] 的分为一组，作为
的分为一组。 例如，在用例
和
和
中，将数组的前部分作为
而后半部分作为
时，可以得到最优解，至此发现贪心规律。
设数组的长度为
，最大匹配对数为
：
- 结论 1： 使用数组的左半部分作为
且使用数组的右半部分作为
总能取到最优解。反之，如果使用右半部分的某个数
作为
，相当于占用了一个较大的数，不利于后续
寻找配对；
- 结论 2： 当固定
时，
越小越好，否则会占用一个较大的位置，不利于后续
寻找配对。因此最优解一定是使用左半部分的最小值与右半部分的最小值配对。
总结：如果存在
对匹配，那么一定可以让最小的
个数和最大的
个数匹配。
基于以上分析，可以写出二分答案：
class Solution {
fun minLengthAfterRemovals(nums: List<Int>): Int {
val n = nums.size
var left = 0
var right = n / 2
while (left < right) {
val k = (left + right + 1) ushr 1
if ((0 ..< k).all { nums[it] < nums[n - k + it] }) {
left = k
} else {
right = k - 1
}
}
return n - 2 * left
}
}
复杂度分析：
- 时间复杂度：
二分答案次数最大为
次，单次检验的时间复杂度是
；
- 空间复杂度：
仅使用常量级别空间。
题解二（双指针）
基于题解一的分析，以及删除操作的上界
，我们可以仅使用数组的后半部分与前半部分作比较，具体算法：
- i 指针指向索引
- j 指针指向索引
- 向右枚举
指针，如果
、
指针指向的位置能够匹配，则向右移动
指针；
- 最后
指针移动的次数就等于删除操作次数。
class Solution {
fun minLengthAfterRemovals(nums: List<Int>): Int {
val n = nums.size
var i = 0
for (j in (n + 1) / 2 until n) {
if (nums[i] < nums[j]) i++
}
return n - 2 * i
}
}
复杂度分析：
- 时间复杂度：
线性遍历；
- 空间复杂度：
仅使用常量级别空间。
题解三（众数）
由于题目的操作只要满足
，即两个数不相等即可，那么问题的解最终仅取决于数组中的众数的出现次数：
- 如果众数的出现次数比其他元素少，那么所有元素都能删除，问题的结果就看数组总长度是奇数还是偶数；
- 否则，剩下的元素就是众数：
最后，由于数组是非递减的，因此可以在
空间求出众数的出现次数：
class Solution {
fun minLengthAfterRemovals(nums: List<Int>): Int {
val n = nums.size
var s = 1
var cur = 1
for (i in 1 until n) {
if (nums[i] == nums[i - 1]) {
s = max(s, ++ cur)
} else {
cur = 1
}
}
if (s <= n - s) {
return n % 2
} else {
return s - (n - s)
}
}
}
复杂度分析：
- 时间复杂度：
线性遍历；
- 空间复杂度：
仅使用常量级别空间。
题解四（找规律 + 二分查找）
继续挖掘数据规律：
等价于众数的出现次数超过数组长度的一半，由于数组是有序的，那么一定有数组的中间位置就是众数，我们可以用二分查找找出众数在数组中出现位置的边界，从而计算出众数的出现次数。
由此，我们甚至不需要线性扫描都能计算出众数以及众数的出现次数，Nice！
当然，最后计算出来的出现次数有可能没有超过数组长度的一半。
class Solution {
fun minLengthAfterRemovals(nums: List<Int>): Int {
val n = nums.size
val x = nums[n / 2]
val s = lowerBound(nums, x + 1) - lowerBound(nums, x)
return max(2 * s - n, n % 2)
}
fun lowerBound(nums: List<Int>, target: Int): Int {
var left = 0
var right = nums.size - 1
while (left < right) {
val mid = (left + right + 1) ushr 1
if (nums[mid] >= target) {
right = mid - 1
} else {
left = mid
}
}
return if (nums[left] == target) left else left + 1
}
}
复杂度分析：
- 时间复杂度：
单次二分查找的时间复杂度是
；
- 空间复杂度：
仅使用常量级别空间。
相似题目：
- 2576. 求出最多标记下标
T3. 统计距离为 k 的点对（Medium）
https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/
题解（散列表）
- 问题目标： 求
的方案数；
- 技巧： 对于存在多个变量的问题，可以考虑先固定其中一个变量；
容易想到两数之和的问题模板，唯一需要思考的问题是如何设计散列表的存取方式：
对于满足
的方案，我们抽象为两部分
，其中，
的取值范围为
，而
，即总共有
种方案。本题的
数据范围很小，所以我们可以写出时间复杂度
的算法。
class Solution {
fun countPairs(coordinates: List<List<Int>>, k: Int): Int {
var ret = 0
// <x, <y, cnt>>
val map = HashMap<Int, HashMap<Int, Int>>()
for ((x2, y2) in coordinates) {
// 记录方案
for (i in 0 .. k) {
if (!map.containsKey(i xor x2)) continue
ret += map[i xor x2]!!.getOrDefault((k - i) xor y2, 0)
}
// 累计次数
map.getOrPut(x2) { HashMap<Int, Int>() }[y2] = map[x2]!!.getOrDefault(y2, 0) + 1
}
return ret
}
}
Python 计数器支持复合数据类型的建，可以写出非常简洁的代码：
class Solution:
def countPairs(self, coordinates: List[List[int]], k: int) -> int:
c = Counter()
ret = 0
for x2, y2 in coordinates:
# 记录方案
for i in range(k + 1):
ret += c[(i ^ x2, (k - i) ^ y2)]
# 累计次数
c[(x2, y2)] += 1
return ret
复杂度分析：
- 时间复杂度：
线性枚举，每个元素枚举
种方案；
- 空间复杂度：
散列表空间。
T4. 可以到达每一个节点的最少边反转次数（Hard）
https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/
问题分析
初步分析：
- 问题目标： 求出以每个节点为根节点时，从根节点到其他节点的反转操作次数，此题属于换根 DP 问题
思考实现：
- 暴力： 以节点
为根节点走一次 BFS/DFS，就可以在
时间内求出每个节点的解，整体的时间复杂度是
思考优化：
- 重叠子问题： 相邻边连接的节点间存在重叠子问题，当我们从根节点
移动到其子节点
时，我们可以利用已有信息在
时间算出
为根节点时的解。
具体实现：
- 1、随机选择一个点为根节点
，在一次 DFS 中根节点
的反转操作次数：
- 2、
的状态转移：
- 如果
是正向边，则反转次数
；
- 如果
是反向边，则反转次数
（从
到
不用反转）；
- 3、由于题目是有向图，我们可以转换为无向图，再利用标记位
和
表示边的方向，
为正向边，
为反向边。
题解（换根 DP）
class Solution {
fun minEdgeReversals(n: Int, edges: Array<IntArray>): IntArray {
val dp = IntArray(n)
val graph = Array(n) { LinkedList<IntArray>() }
// 建图
for ((from, to) in edges) {
graph[from].add(intArrayOf(to, 1))
graph[to].add(intArrayOf(from, -1))
}
// 以 0 为根节点
fun dfs(i: Int, fa: Int) {
for ((to, gain) in graph[i]) {
if (to == fa) continue
if (gain == -1) dp[0] ++
dfs(to, i)
}
}
fun dp(i: Int, fa: Int) {
for ((to, gain) in graph[i]) {
if (to == fa) continue
// 状态转移
dp[to] = dp[i] + gain
dp(to, i)
}
}
dfs(0, -1)
dp(0, -1)
return dp
}
}
复杂度分析：
- 时间复杂度：
DFS 和换根 DP 都是
；
- 空间复杂度：