⭐️ 本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
本文是 LeetCode 上分之旅系列的第 45 篇文章,往期回顾请移步到文章末尾~
LeetCode 双周赛 113 概览
T1. 使数组成为递增数组的最少右移次数(Easy)
- 标签:模拟、暴力、线性遍历
T2. 删除数对后的最小数组长度(Medium)
- 标签:二分答案、双指针、找众数、
T3. 统计距离为 k 的点对(Medium)
- 标签:枚举、散列表
T4. 可以到达每一个节点的最少边反转次数(Hard)
- 标签:树上 DP
T1. 使数组成为递增数组的最少右移次数(Easy)
https://leetcode.cn/problems/minimum-right-shifts-to-sort-the-array/description/
题解一(暴力枚举)
简单模拟题。
由于题目数据量非常小,可以把数组复制一份拼接在尾部,再枚举从位置 $i$ 开始长为 $n$ 的连续循环子数组是否连续,是则返回 $(n – i)%n$:
class Solution {
fun minimumRightShifts(nums: MutableList): Int {
val n = nums.size
nums.addAll(nums)
for (i in 0 until n) {
if ((i + 1 .. 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
复杂度分析:
- 时间复杂度:$O(n^2)$ 双重循环;
- 空间复杂度:$O(n)$ 循环数组空间。
题解二(线性遍历)
更优的写法,我们找到第一个逆序位置,再检查该位置后续位置是否全部为升序,且满足 $nums[n – 1]
class Solution {
fun minimumRightShifts(nums: List): 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
}
}
复杂度分析:
- 时间复杂度:$O(n)$ $i$ 指针和 $j$ 指针总计最多移动 $n$ 次;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
T2. 删除数对后的最小数组长度(Medium)
https://leetcode.cn/problems/minimum-array-length-after-pair-removals/
题解一(二分答案)
问题存在单调性:
- 当操作次数 $k$ 可以满足时,操作次数 $k – 1$ 一定能满足;
- 当操作次数 $k$ 不可满足时,操作次数 $k + 1$ 一定不能满足。
那么,原问题相当于求解满足目标的最大操作次数。
现在需要考虑的问题是:如何验证操作次数 $k$ 是否可以完成?
一些错误的思路:
- 尝试 1 – 贪心双指针: $nums[i]$ 优先使用最小值,$nums[j]$ 优先使用最大值,错误用例:$[1 2 3 6]$;
- 尝试 2 – 贪心: $nums[i]$ 优先使用最小值,$nums[j]$ 使用大于 $nums[i]$ 的最小值,错误用例:$[1 2 4 6]$;
- 尝试 3 – 贪心: 从后往前遍历,$nums[i]$ 优先使用较大值,$nums[j]$ 使用大于 $nums[i]$ 的最小值,错误用例:$[2 3 4 8]$。
开始转换思路:
能否将数组拆分为两部分,作为 nums[i] 的分为一组,作为 $nums[j]$ 的分为一组。 例如,在用例 $[1 2 | 3 6]$ 和 $[1 2 | 4 6]$ 和 $[2 3 | 4 8]$ 中,将数组的前部分作为 $nums[i]$ 而后半部分作为 $nums[j]$ 时,可以得到最优解,至此发现贪心规律。
设数组的长度为 $n$,最大匹配对数为 $k$:
- 结论 1: 使用数组的左半部分作为 $nums[i]$ 且使用数组的右半部分作为 $nums[j]$ 总能取到最优解。反之,如果使用右半部分的某个数 $nums[t]$ 作为 $nums[i]$,相当于占用了一个较大的数,不利于后续 $nums[i]$ 寻找配对;
- 结论 2: 当固定 $nums[i]$ 时,$nums[j]$ 越小越好,否则会占用一个较大的位置,不利于后续 $nums[i]$ 寻找配对。因此最优解一定是使用左半部分的最小值与右半部分的最小值配对。
总结:如果存在$k$对匹配,那么一定可以让最小的$k$个数和最大的$k$ 个数匹配。
基于以上分析,可以写出二分答案:
class Solution {
fun minLengthAfterRemovals(nums: List): Int {
val n = nums.size
var left = 0
var right = n / 2
while (left
复杂度分析:
- 时间复杂度:$O(nlgn)$ 二分答案次数最大为 $lgn$ 次,单次检验的时间复杂度是 $O(n)$;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
题解二(双指针)
基于题解一的分析,以及删除操作的上界 $n / 2$,我们可以仅使用数组的后半部分与前半部分作比较,具体算法:
- i 指针指向索引 $0$
- j 指针指向索引 $(n + 1) / 2$
- 向右枚举 $j$ 指针,如果 $i$、$j$ 指针指向的位置能够匹配,则向右移动 $i$ 指针;
- 最后 $i$ 指针移动的次数就等于删除操作次数。
class Solution {
fun minLengthAfterRemovals(nums: List): Int {
val n = nums.size
var i = 0
for (j in (n + 1) / 2 until n) {
if (nums[i]
复杂度分析:
- 时间复杂度:$O(n)$ 线性遍历;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
题解三(众数)
由于题目的操作只要满足 $nums[i]
- 如果众数的出现次数比其他元素少,那么所有元素都能删除,问题的结果就看数组总长度是奇数还是偶数;
- 否则,剩下的元素就是众数:$s – (n – s)$
最后,由于数组是非递减的,因此可以在 $O(1)$ 空间求出众数的出现次数:
class Solution {
fun minLengthAfterRemovals(nums: List): 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
复杂度分析:
- 时间复杂度:$O(n)$ 线性遍历;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
题解四(找规律 + 二分查找)
继续挖掘数据规律:
$s
由此,我们甚至不需要线性扫描都能计算出众数以及众数的出现次数,Nice!
当然,最后计算出来的出现次数有可能没有超过数组长度的一半。
class Solution {
fun minLengthAfterRemovals(nums: List): 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, target: Int): Int {
var left = 0
var right = nums.size - 1
while (left = target) {
right = mid - 1
} else {
left = mid
}
}
return if (nums[left] == target) left else left + 1
}
}
复杂度分析:
- 时间复杂度:$O(lgn)$ 单次二分查找的时间复杂度是 $O(lgn)$;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
相似题目:
- 2576. 求出最多标记下标
T3. 统计距离为 k 的点对(Medium)
https://leetcode.cn/problems/count-pairs-of-points-with-distance-k/
题解(散列表)
- 问题目标: 求 $(x1 xor x2) + (y1 xor y2) == k$ 的方案数;
- 技巧: 对于存在多个变量的问题,可以考虑先固定其中一个变量;
容易想到两数之和的问题模板,唯一需要思考的问题是如何设计散列表的存取方式:
对于满足 $(x1 xor x2) + (y1 xor y2) == k$ 的方案,我们抽象为两部分 $i + j = k$,其中,$i = (x1 xor x2)$ 的取值范围为 $[0, k]$,而 $j = k – i$,即总共有 $k + 1$ 种方案。本题的 $k$ 数据范围很小,所以我们可以写出时间复杂度 $O(nk)$ 的算法。
class Solution {
fun countPairs(coordinates: List>, k: Int): Int {
var ret = 0
// >
val map = HashMap>()
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() }[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
复杂度分析:
- 时间复杂度:$O(nk)$ 线性枚举,每个元素枚举 $k$ 种方案;
- 空间复杂度:$O(n)$ 散列表空间。
T4. 可以到达每一个节点的最少边反转次数(Hard)
https://leetcode.cn/problems/minimum-edge-reversals-so-every-node-is-reachable/
问题分析
初步分析:
- 问题目标: 求出以每个节点为根节点时,从根节点到其他节点的反转操作次数,此题属于换根 DP 问题
思考实现:
- 暴力: 以节点 $i$ 为根节点走一次 BFS/DFS,就可以在 $O(n)$ 时间内求出每个节点的解,整体的时间复杂度是 $O(n^2)$
思考优化:
- 重叠子问题: 相邻边连接的节点间存在重叠子问题,当我们从根节点 $u$ 移动到其子节点 $v$ 时,我们可以利用已有信息在 $O(1)$ 时间算出 $v$ 为根节点时的解。
具体实现:
- 1、随机选择一个点为根节点 $u$,在一次 DFS 中根节点 $u$ 的反转操作次数:
- 2、$u → v$ 的状态转移:
- 如果 $u → v$ 是正向边,则反转次数 $+ 1$;
- 如果 $u → v$ 是反向边,则反转次数 $- 1$(从 $v$ 到 $u$ 不用反转);
- 3、由于题目是有向图,我们可以转换为无向图,再利用标记位 $1$ 和 $-1$ 表示边的方向,$1$ 为正向边,$-1$ 为反向边。
题解(换根 DP)
class Solution {
fun minEdgeReversals(n: Int, edges: Array): IntArray {
val dp = IntArray(n)
val graph = Array(n) { LinkedList() }
// 建图
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
}
}
复杂度分析:
- 时间复杂度:$O(n)$ DFS 和换根 DP 都是 $O(n)$;
- 空间复杂度:$O(n)$ 递归栈空间与 DP 数组空间。
推荐阅读
LeetCode 上分之旅系列往期回顾:
- LeetCode 单周赛第 361 场 同余前缀和问题与经典倍增 LCA 算法
- LeetCode 单周赛第 360 场 当 LeetCode 考树上倍增,出题的趋势在变化吗
- LeetCode 双周赛第 112 场 计算机科学本质上是数学吗?
- LeetCode 双周赛第 111 场 按部就班地解决动态规划问题
⭐️ 永远相信美好的事情即将发生,欢迎加入小彭的 Android 交流社群~
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net