周赛 360
T1. 距离原点最远的点（Easy）
- 标签：模拟
T2. 找出美丽数组的最小和（Medium）
- 标签：散列表、贪心、数学
T3. 使子序列的和等于目标的最少操作次数（Hard）
- 标签：位运算、散列表、排序
T4. 在传球游戏中最大化函数值（Hard）
- 标签：树、倍增、动态规划、内向基环树
T1. 距离原点最远的点（Easy）
https://leetcode.cn/problems/furthest-point-from-origin/
题解（模拟）
根据题意 “_” 既可以作为 “L” 也可以作为 “R”。容易想到，为了使得终点距离原点更远，当所有 “_” 仅作为 “L” 或 “R” 对结果的贡献是最优的，此时问题的结果就取决于 “L” 和 “R” 的差绝对值。
class Solution {
fun furthestDistanceFromOrigin(moves: String): Int {
return moves.count{ it == '_' } + abs(moves.count{ it == 'L' } - moves.count{ it == 'R' })
}
}
一次遍历：
class Solution {
fun furthestDistanceFromOrigin(moves: String): Int {
var cntL = 0
var cntR = 0
for (e in moves) {
when (e) {
'L' -> {
cntL ++
cntR --
}
'R' -> {
cntL --
cntR ++
}
else -> {
cntL ++
cntR ++
}
}
}
return max(abs(cntL), abs(cntR))
}
}
复杂度分析：
- 时间复杂度：
线性遍历；
- 空间复杂度：
仅使用常量级别空间。
T2. 找出美丽数组的最小和（Medium）
https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/
这道题与上周周赛 359 T2 2829. k-avoiding 数组的最小总和 相比，除了数据范围之外是完全相同的，有点离谱。
题解一（散列表 + 贪心）
从 开始从小到大枚举，如果当前元素
与已选列表不冲突，则加入结果中。为了验证是否冲突，我们使用散列表在
时间复杂度判断。
class Solution {
fun minimumPossibleSum(n: Int, k: Int): Long {
val set = HashSet<Int>()
var sum = 0L
var cur = 1
repeat(n) {
while (!set.isEmpty() && set.contains(k - cur)) cur++
sum += cur
set.add(cur)
cur++
}
return sum
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
题解二（数学）
这道题还可以继续挖掘数学规律，我们发现当我们从 开始从小到大枚举时，每选择一个数的同时必然会使得另一个数
不可选。例如：
- 选择
，则
不可选；
- 选择
，则
不可选；
- …
- 选择
，则
不可选。
可以发现，最终选择的元素被分为两部分：
- 小于
的部分：选择所有和为
；
- 大于等于
共 n - m 个数。
我们令 ，使用求和公式可以
求出两部分的总和：
- 小于 k 的部分：
- 大于等于 k 的部分：
class Solution {
fun minimumPossibleSum(n: Int, k: Int): Long {
val m = 1L * Math.min(n, k / 2)
return m * (m + 1) / 2 + (n - m) * (2 * k + n - m - 1) / 2
}
}
复杂度分析：
- 时间复杂度：
- 空间复杂度：
T3. 使子序列的和等于目标的最少操作次数（Hard）
https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/
这道题的考点不复杂，难点在模拟问题挺考验编码功底的。
问题分析
-
关键信息：
数组中所有元素都是
-
问题是否有解： 考虑到所有数最终都能拆分成
就一定有解；
# 二进制位
nums: _ _ _ 1 _ _ _ _
target: _ _ _ _ _ 1 _ _
-
子问题： 问题是否有解的判断不仅适用于原问题，对于仅考虑二进制位最低位
到
的子问题亦是如此。
以示例 1 nums = [1,2,8], target = 7 与示例 2 nums = [1,32,1,2], target = 12 为例，我们将统计 中不同
的幂的出现次数：
# 二进制位
nums: _ _ _ _ 1 _ 1 1
target: _ _ _ _ _ 1 1 1
# 二进制位
nums: _ _ 1 _ _ _ 1 2 # 1 出现 2 次
target: _ _ _ _ 1 1 _ _
那么当我们从右向左枚举二进制位 时，如果「
中小于等于
的元素和」
「
中低于等于
位的值」，那么对于仅考虑
位上的子问题是有解的。否则，我们需要找到
中最近大于
的最近数组做拆分：
# 只考虑低 2 位，可以构造
nums: _ _ _ _ 1 _ | 1 1
target: _ _ _ _ _ 1 | 1 1
# 只考虑低 3 位，无法构造，需要找到最近的 “1” 做拆分
nums: _ _ _ _ 1 | _ 1 1
target: _ _ _ _ _ | 1 1 1
# 只考虑低 3 位，无法构造，需要找到最近的 “1” 做拆分
nums: _ _ 1 _ _ | _ 1 2
target: _ _ _ _ 1 | 1 _ _
# 只考虑低 6 位，可以构造
nums: _ _ | 1 _ _ _ 1 2
target: _ _ | _ _ 1 1 _ _
组合以上技巧：
写法一（数组模拟）
思路参考灵神的题解。
- 首先，我们使用长为
的数组，计算出
- 随后，我们从低位到高位枚举二进制位
，在每轮迭代中将
元素累加到
中，此举相当于在求「低
- 最后，我们比较
做拆分；
- 另外，有一个优化点：当我们拆分将
时并不是直接丢弃
等一系列数，可以直接跳到第
位继续枚举。
注意一个容易 WA 的地方，在开头特判的地方，由于元素和可能会溢出 上界，所以我们需要转换为在
上的求和。
class Solution {
fun minOperations(nums: List<Int>, target: Int): Int {
if (nums.fold(0L) { it, acc -> it + acc } < target) return -1
// if (nums.sum() < target) return -1 // 溢出
// 计数
val cnts = IntArray(32)
for (num in nums) {
var i = 0
var x = num
while (x > 1) {
x = x shr 1
i += 1
}
cnts[i]++
}
var ret = 0
var i = 0
var sum = 0L
while(sum < target) {
// 累加低位的 nums
sum += (cnts[i]) shl i
// println("i=$i, sum=$sum")
// 低 i 位掩码
val mask = (1 shl (i + 1)) - 1
// 构造子问题
if (sum < target and mask) {
var j = i + 1
while (cnts[j] == 0) { // 基于开头的特判，此处一定有解
j++
}
// 拆分
ret += j - i
i = j
} else {
i += 1
}
}
return ret
}
}
复杂度分析：
- 时间复杂度：
) 其中
为
为整型大小
- 空间复杂度：
数组空间。
写法二（散列表模拟）
在计数的部分，我们可以使用散列表模拟，复杂度相同。
class Solution {
fun minOperations(nums: List<Int>, target: Int): Int {
if (nums.fold(0L) { it, acc -> it + acc } < target) return -1
// if (nums.sum() < target) return -1 // 溢出
// 计数
val cnts = HashMap<Int, Int>()
for (num in nums) {
cnts[num] = cnts.getOrDefault(num, 0) + 1
}
var ret = 0
var i = 0
var sum = 0L
while(sum < target) {
// 累加低位的 nums
sum += (cnts[1 shl i] ?: 0) shl i
// println("i=$i, sum=$sum")
// 低 i 位掩码
val mask = (1 shl (i + 1)) - 1
// 构造子问题
if (sum < target and mask) {
var j = i + 1
while (!cnts.containsKey(1 shl j)) { // 基于开头的特判，此处一定有解
j++
}
// 拆分
ret += j - i
i = j
} else {
i += 1
}
}
return ret
}
}
复杂度分析：
- 时间复杂度：
其中
- 空间复杂度：
写法三（逆向思维）
思路参考雪景式的题解，前两种写法是在从小到大枚举「选哪个」，我们也可以枚举「不选哪个」。
-
思考 1： 在原问题有解
的情况下，如果从
后，依然满足剩余的元素和
，那么直接将
-
思考 2： 如果从
- 如果
，那么
- 如果
，那么
- 如果
class Solution {
fun minOperations(nums: MutableList<Int>, target: Int): Int {
var sum = nums.fold(0L) { it, acc -> it + acc }
if (sum < target) return -1
// 排序
nums.sortDescending()
// 从大到小枚举
var ret = 0
var left = target
while (sum > left) {
val x = nums.removeFirst()
if (sum - x >= left){
sum -= x
} else if (x <= left) {
sum -= x
left -= x
} else {
ret += 1
nums.add(0, x / 2)
nums.add(0, x / 2)
}
// println("ret=$ret, sum=$sum, left=$left, x=$x, nums=${nums.joinToString()}")
}
return ret
}
}
复杂度分析：
- 时间复杂度：
瓶颈在排序，枚举阶段每个元素最多访问
- 空间复杂度：
排序递归栈空间。
T4. 在传球游戏中最大化函数值（Hard）
https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/
题解（树上倍增）
从近期周赛的趋势看，出题人似乎有意想把 LeetCode 往偏竞赛的题目引导。
这道题如果知道树上倍增算法，其实比第三题还简单一些。
-
问题目标： 找到最佳方案，使得从起点开始传球
-
暴力： 对于暴力的做法，我们可以枚举以每名玩家为起点的方案，并模拟传球过程求出最佳方案。但是这道题的步长
，如果逐级向上传球，那么单次查询的时间复杂度是
。现在，需要思考如何优化模拟
-
倍增思想： 借鉴 1483. 树节点的第 K 个祖先 的解法，我们可以利用倍增算法将线性的操作施加指数级别的贡献：
- 如果可以预处理出每个玩家的多级后驱玩家，那么在查询时可以加速跳转；
- 由于每个数都可以进行二进制拆分为多个
个后驱玩家，那么求解第
class Solution {
fun getMaxFunctionValue(receiver: List<Int>, k: Long): Long {
val n = receiver.size
val m = 64 - k.countLeadingZeroBits()
// 预处理
// dp[i][j] 表示 i 传球 2^j 次后的节点
val dp = Array(n) { IntArray(m) }
// dp[i][j] 表示 i 传球 2^j 次的路径和
val sum = Array(n) { LongArray(m) }
for (i in 0 until n) {
dp[i][0] = receiver[i]
sum[i][0] = receiver[i].toLong()
}
for (j in 1 until m) {
for (i in 0 until n) { // 这道题没有根节点，不需要考虑 child == -1 的情况
val child = dp[i][j - 1]
// 从 i 条 2^{j-1} 次，再跳 2^{j-1}
dp[i][j] = dp[child][j - 1]
sum[i][j] = sum[i][j - 1] + sum[child][j - 1]
}
}
// 枚举方案
var ret = 0L
for (node in 0 until n) {
var i = node
var x = k
var s = node.toLong() // 起点的贡献
while (x != 0L) {
val j = x.countTrailingZeroBits()
s += sum[i][j]
i = dp[i][j]
x = x and (x - 1)
}
ret = max(ret, s)
}
return ret
}
}
复杂度分析：
- 时间复杂度：预处理时间为
，枚举时间为
数组的长度；
- 空间复杂度：预处理空间
另外，这道题还有基于「内向基环树」的 解法。
推荐阅读
LeetCode 上分之旅系列往期回顾：
