⭐️ 本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 和 BaguTree Pro 知识星球提问。
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
本文是 LeetCode 上分之旅系列的第 44 篇文章,往期回顾请移步到文章末尾~
T1. 统计对称整数的数目(Easy)
- 标签:模拟
T2. 生成特殊数字的最少操作(Medium)
- 标签:思维、回溯、双指针
T3. 统计趣味子数组的数目(Medium)
- 标签:同余定理、前缀和、散列表
T4. 边权重均等查询(Hard)
- 标签:图、倍增、LCA、树上差分
T1. 统计对称整数的数目(Easy)
https://leetcode.cn/problems/count-symmetric-integers/
题解(模拟)
根据题意模拟,亦可以使用前缀和预处理优化。
class Solution {
fun countSymmetricIntegers(low: Int, high: Int): Int {
var ret = 0
for (x in low..high) {
val s = "$x"
val n = s.length
if (n % 2 != 0) continue
var diff = 0
for (i in 0 until n / 2) {
diff += s[i] - '0'
diff -= s[n - 1 - i] - '0'
}
if (diff == 0) ret += 1
}
return ret
}
}
复杂度分析:
- 时间复杂度:$O((high-low)lg^{high})$ 单次检查时间为 $O(lg^{high})$;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
T2. 生成特殊数字的最少操作(Easy)
https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/
题解一(回溯)
思维题,这道卡了多少人。
- 阅读理解: 在一次操作中,您可以选择 $num$ 的任意一位数字并将其删除,求最少需要多少次操作可以使 $num$ 变成 $25$ 的倍数;
- 规律: 对于 $25$ 的倍数,当且仅当结尾为「00、25、50、75」这 $4$ 种情况时成立,我们尝试构造出尾部符合两个数字能被 $25$ 整除的情况。
可以用回溯解决:
class Solution {
fun minimumOperations(num: String): Int {
val memo = HashMap()
fun count(x: String): Int {
val n = x.length
if (n == 1) return if (x == "0") 0 else 1
if (((x[n - 2] - '0') * 10 + (x[n - 1]- '0')) % 25 == 0) return 0
if(memo.containsKey(x))return memo[x]!!
val builder1 = StringBuilder(x)
builder1.deleteCharAt(n - 1)
val builder2 = StringBuilder(x)
builder2.deleteCharAt(n - 2)
val ret = 1 + min(count(builder1.toString()), count(builder2.toString()))
memo[x]=ret
return ret
}
return count(num)
}
}
复杂度分析:
- 时间复杂度:$O(n^2m)$ 最多有 $n^2$ 种子状态,其中 $m$ 是字符串的平均长度,$O(m)$ 是构造中间字符串的时间;
- 空间复杂度:$O(n)$ 回溯递归栈空间。
题解二(双指针)
初步分析:
- 模拟: 事实上,问题的方案最多只有 4 种,回溯的中间过程事实在尝试很多无意义的方案。我们直接枚举这 4 种方案,删除尾部不属于该方案的字符。以 25 为例,就是删除 5 后面的字符以及删除 2 与 5 中间的字符;
- 抽象: 本质上是一个最短匹配子序列的问题,即 「找到 nums 中最靠后的匹配的最短子序列」问题,可以用双指针模拟。
具体实现:
- 双指针: 我们找到满足条件的最靠左的下标 i,并删除末尾除了目标数字外的整段元素,即 $ret = n – i – 2$;
- 特殊情况: 在 4 种构造合法的特殊数字外,还存在删除所有非 0 数字后构造出 0 的方案;
- 是否要验证数据含有前导零: 对于构造「00」的情况,是否会存在删到最后剩下多个 0 的情况呢?其实是不存在的。因为题目说明输入数据 num 本身是不包含前导零的,如果最后剩下多个 0 ,那么在最左边的 0 左侧一定存在非 0 数字,否则与题目说明矛盾。
class Solution {
fun minimumOperations(num: String): Int {
val n = num.length
var ret = n
for (choice in arrayOf("00", "25", "50", "75")) {
// 双指针
var j = 1
for (i in n - 1 downTo 0) {
if (choice[j] != num[i]) continue
if (--j == -1) {
ret = min(ret, n - i - 2)
break
}
}
}
// 特殊情况
ret = min(ret, n - num.count { it == '0'})
return ret
}
}
复杂度分析:
- 时间复杂度:$O(n)$ 4 种方案和特殊方案均是线性遍历;
- 空间复杂度:$O(1)$ 仅使用常量级别空间。
T3. 统计趣味子数组的数目(Medium)
https://leetcode.cn/problems/count-of-interesting-subarrays/
题解(同余 + 前缀和 + 散列表)
初步分析:
- 问题目标: 统计数组中满足目标条件的子数组;
- 目标条件: 在子数组范围 $[l, r]$ 内,设 $cnt$ 为满足 $nums[i] % m == k$ 的索引 $i$ 的数量,并且 $cnt % m == k$。大白话就是算一下有多少数的模是 $k$,再判断个数的模是不是也是 $k$;
- 权重: 对于满足 $nums[i] % m == k$ 的元素,它对结果的贡献是 $1$,否则是 $0$;
分析到这里,容易想到用前缀和实现:
- 前缀和: 记录从起点到 $[i]$ 位置的 $[0, i]$ 区间范围内满足目标的权重数;
- 两数之和: 从左到右枚举 $[i]$,并寻找已经遍历的位置中满足 $(preSum[i] – preSum[j]) % m == k$ 的方案数记入结果;
-
公式转换: 上式带有取模运算,我们需要转换一下:
- 原式 $(preSum[i] – preSum[j]) % m == k$
- 考虑 $preSum[i] % m – preSum[j] % m$ 是正数数的的情况,原式等价于:$preSum[i] % m – preSum[j] % m == k$
- 考虑 $preSum[i] % m – preSum[j] % m$ 是负数的的情况,我们在等式左边增加补数:$(preSum[i] % m – preSum[j] % m + m) %m == k$
- 联合正数和负数两种情况,即我们需要找到前缀和为 $(preSum[i] % m – k + m) % m$ 的元素;
- 修正前缀和定义: 最后,我们修改前缀和的定义为权重 $% m$。
组合以上技巧:
class Solution {
fun countInterestingSubarrays(nums: List, m: Int, k: Int): Long {
val n = nums.size
var ret = 0L
val preSum = HashMap()
preSum[0] = 1 // 注意空数组的状态
var cur = 0
for (i in 0 until n) {
if (nums[i] % m == k) cur ++ // 更新前缀和
val key = cur % m
val target = (key - k + m) % m
ret += preSum.getOrDefault(target, 0) // 记录方案
preSum[key] = preSum.getOrDefault(key, 0) + 1 // 记录前缀和
}
return ret
}
}
复杂度分析:
- 时间复杂度:$O(n)$ 线性遍历,单次查询时间为 $O(1)$;
- 空间复杂度:$O(m)$ 散列表空间。
相似题目:
- 560. 和为 K 的子数组
- 974. 和可被 K 整除的子数组
- 523. 连续的子数组和
- 525. 连续数组
T4. 边权重均等查询(Hard)
https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/
题解(倍增求 LCA、树上差分)
初步分析:
- 问题目标: 给定若干个查询 $[x, y]$,要求计算将 $$ 的路径上的每条边修改为相同权重的最少操作次数;
- 问题要件: 对于每个查询 $[x, y]$,我们需要计算 $$ 的路径长度 $l$,以及边权重的众数的出现次数 $c$,而要修改的操作次数就是 $l – c$;
- 技巧: 对于 “树上路径” 问题有一种经典技巧,我们可以把 $$ 的路径转换为从 $$ 的路径与 $$ 的两条路径;
思考实现:
- 长度: 将问题转换为经过 $lca$ 中转的路径后,路径长度 $l$ 可以用深度来计算:$l = depth[x] + depth[y] – 2 * depth[lca]$;
- 权重: 同理,权重 $w[x,y]$ 可以通过 $w[x, lca]$ 与 $w[lca, y]$ 累加计算;
现在的关键问题是,如何快速地找到 $$ 的最近公共祖先 LCA?
对于单次 LCA 操作来说,我们可以走 DFS 实现 $O(n)$ 时间复杂度的算法,而对于多次 LCA 操作可以使用 倍增算法 预处理以空间换时间,单次 LCA 操作的时间复杂度进位 $O(lgn)$。
在 LeetCode 有倍增的模板题 1483.树节点的第 K 个祖先。
在求 LCA 时,我们先把 $$ 跳到相同高度,再利用倍增算法向上跳 $2^j$ 个父节点,直到到达相同节点即为最近公共祖先。
class Solution {
fun minOperationsQueries(n: Int, edges: Array, queries: Array): IntArray {
val U = 26
// 建图
val graph = Array(n) { LinkedList() }
for (edge in edges) {
graph[edge[0]].add(intArrayOf(edge[1], edge[2] - 1))
graph[edge[1]].add(intArrayOf(edge[0], edge[2] - 1))
}
// 预处理深度、倍增祖先节点、倍增路径信息
val m = 32 - Integer.numberOfLeadingZeros(n - 1)
val depth = IntArray(n)
val parent = Array(n) { IntArray(m) { -1 }} // parent[i][j] 表示 i 的第 2^j 个父节点
val cnt = Array(n) { Array(m) { IntArray(U) }} // cnt[i][j] 表示 个父节点的路径信息
fun dfs(i: Int, par: Int) {
for ((to, w) in graph[i]) {
if (to == par) continue // 避免回环
depth[to] = depth[i] + 1
parent[to][0] = i
cnt[to][0][w]服务器托管网 = 1
dfs(to, i)
}
}
dfs(0, -1) // 选择 0 作为根节点
// 预处理倍增
for (j in 1 until m) {
for (i in 0 until n) {
val from = parent[i][j - 1]
if (-1 != from) {
parent[i][j] = parent[from][j - 1]
cnt[i][j] = cnt[i][j - 1].zip(cnt[from][j - 1]) { e1, e2 -> e1 + e2 }.toIntArray()
}
}
}
// 查询
val q = queries.size
val ret = IntArray(q)
服务器托管网 for ((i, query) in queries.withIndex()) {
var (x, y) = query
// 特判
if (x == y || parent[x][0] == y || parent[y][0] == x) {
ret[i] = 0
}
val w = IntArray(U) // 记录路径信息
var path = depth[x] + depth[y] // 记录路径长度
// 先跳到相同高度
if (depth[y] > depth[x]) {
val temp = x
x = y
y = temp
}
var k = depth[x] - depth[y]
while (k > 0) {
val j = Integer.numberOfTrailingZeros(k) // 二进制分解
w.indices.forEach { w[it] += cnt[x][j][it] } // 记录路径信息
x = parent[x][j] // 向上跳 2^j 个父节点
k = k and (k - 1)
}
// 再使用倍增找 LCA
if (x != y) {
for (j in m - 1 downTo 0) { // 最多跳 m - 1 次
if (parent[x][j] == parent[y][j]) continue // 跳上去相同就不跳
w.indices.forEach { w[it] += cnt[x][j][it] } // 记录路径信息
w.indices.forEach { w[it] += cnt[y][j][it] } // 记录路径信息
x = parent[x][j]
y = parent[y][j] // 向上跳 2^j 个父节点
}
// 最后再跳一次就是 lca
w.indices.forEach { w[it] += cnt[x][0][it] } // 记录路径信息
w.indices.forEach { w[it] += cnt[y][0][it] } // 记录路径信息
x = parent[x][0]
}
// 减去重链长度
ret[i] = path - 2 * depth[x] - w.max()
}
return ret
}
}
复杂度分析:
- 时间复杂度:$O(nlgnU)$ 预处理的时间复杂度是 $O(nlgnU)$,单次查询的时间是 $O(lgnU)$;
- 空间复杂度:$O(nlgnU)$ 预处理倍增信息空间。
推荐阅读
LeetCode 上分之旅系列往期回顾:
- LeetCode 单周赛第 360 场 当 LeetCode 考树上倍增,出题的趋势在变化吗
- LeetCode 单周赛第 359 场 结合离散化的线性 DP 问题
- LeetCode 双周赛第 112 场 计算机科学本质上是数学吗?
- LeetCode 双周赛第 111 场 按部就班地解决动态规划问题
⭐️ 永远相信美好的事情即将发生,欢迎加入小彭的 Android 交流社群~
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net