LeetCode 周赛上分之旅 #42 当 LeetCode 考树上倍增,出题的趋势在变化吗

周赛 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))
    }
}

复杂度分析:

  • 时间复杂度:O(n) 线性遍历;
  • 空间复杂度:O(1) 仅使用常量级别空间。

T2. 找出美丽数组的最小和(Medium)

https://leetcode.cn/problems/find-the-minimum-possible-sum-of-a-beautiful-array/

这道题与上周周赛 359 T2 2829. k-avoiding 数组的最小总和 相比,除了数据范围之外是完全相同的,有点离谱。

题解一(散列表 + 贪心)

1 开始从小到大枚举,如果当前元素 cur 与已选列表不冲突,则加入结果中。为了验证是否冲突,我们使用散列表在 O(1) 时间复杂度判断。

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
    }
}

复杂度分析:

  • 时间复杂度:O(n) 线性遍历;
  • 空间复杂度:O(n) 散列表空间。

题解二(数学)

这道题还可以继续挖掘数学规律,我们发现当我们从 1 开始从小到大枚举时,每选择一个数的同时必然会使得另一个数 k - x 不可选。例如:

  • 选择 1,则 k - 1 不可选;
  • 选择 2,则 k - 2 不可选;
  • 选择 k / 2,则 k - k / 2 不可选。

可以发现,最终选择的元素被分为两部分:

  • 小于 k 的部分:选择所有和为 k 的配对中的较小值,即 1、2、3 … k / 2
  • 大于等于 k 的部分:与其他任意正整数相加都不会等于 k,因此大于等于 k 的数必然可以选择,即 k、k + 1、k + 2、…、k + n - m - 1 共 n - m 个数。

我们令 m = min(k / 2, n),使用求和公式可以 O(1) 求出两部分的总和:

  • 小于 k 的部分:m(m + 1)/ 2
  • 大于等于 k 的部分:(n - m) * (2*k + n - m - 1) / 2
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
    }
}

复杂度分析:

  • 时间复杂度:O(1)
  • 空间复杂度:O(1)

T3. 使子序列的和等于目标的最少操作次数(Hard)

https://leetcode.cn/problems/minimum-operations-to-form-subsequence-with-target-sum/

这道题的考点不复杂,难点在模拟问题挺考验编码功底的。

问题分析

  • 关键信息: nums 数组中所有元素都是 2 的幂,元素顺序对结果没有影响;
  • 问题是否有解: 考虑到所有数最终都能拆分成 1,那么只要 nums 数组的和大于等于 target 就一定有解;
# 二进制位
nums:   _ _ _ 1 _ _ _ _
target: _ _ _ _ _ 1 _ _
  • 子问题: 问题是否有解的判断不仅适用于原问题,对于仅考虑二进制位最低位 [0][k] 的子问题亦是如此。

以示例 1 nums = [1,2,8], target = 7 与示例 2 nums = [1,32,1,2], target = 12 为例,我们将统计 nums 中不同 2 的幂的出现次数:

# 二进制位
nums:   _ _ _ _ 1 _ 1 1
target: _ _ _ _ _ 1 1 1

# 二进制位
nums:   _ _ 1 _ _ _ 1 2 # 1 出现 2 次
target: _ _ _ _ 1 1 _ _

那么当我们从右向左枚举二进制位 k 时,如果「nums 中小于等于 2^k 的元素和」≥target 中低于等于 k 位的值」,那么对于仅考虑 [0, k] 位上的子问题是有解的。否则,我们需要找到 nums 中最近大于 2^k 的最近数组做拆分:

# 只考虑低 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 _ _

组合以上技巧:

写法一(数组模拟)

思路参考灵神的题解。

  • 首先,我们使用长为 32 的数组,计算出 nums 数组中每个 2 的幂的出现次数;
  • 随后,我们从低位到高位枚举二进制位 i,在每轮迭代中将 nums 数组中的 2^i 元素累加到 sum 中,此举相当于在求「低 i 位的子问题」可以构造的最大值;
  • 最后,我们比较 sum 是否大于等于 target(只考虑低 i 位),此举相当于在判断「低 i 位的子问题」是否可构造。如果不可构造,我们尝试寻找最近的 2^j 做拆分;
  • 另外,有一个优化点:当我们拆分将 2^j 拆分到 2^i (j > i) 时并不是直接丢弃 2^j,而是会留下 2^{j-1}、2^{j-2}… 2^i 等一系列数,可以直接跳到第 j 位继续枚举。

注意一个容易 WA 的地方,在开头特判的地方,由于元素和可能会溢出 Int 上界,所以我们需要转换为在 Long 上的求和。

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
    }
}

复杂度分析:

  • 时间复杂度:O(n·U + U) 其中 nnums 数组的长度,U 为整型大小 32
  • 空间复杂度:O(U) 数组空间。

写法二(散列表模拟)

在计数的部分,我们可以使用散列表模拟,复杂度相同。

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
    }
}

复杂度分析:

  • 时间复杂度:O(n + U) 其中 nnums 数组的长度,U 为整型大小 32
  • 空间复杂度:O(U) 散列表空间。

写法三(逆向思维)

思路参考雪景式的题解,前两种写法是在从小到大枚举「选哪个」,我们也可以枚举「不选哪个」。

  • 思考 1: 在原问题有解(sum > target)的情况下,如果从 sum 中剔除最大的元素 x 后,依然满足剩余的元素和 sum’ > target,那么直接将 x 去掉,这是因为一定存在比 x 操作次数更小的方案能够构造 target(元素越大拆分次数越多)。
  • 思考 2: 如果从 sum 中剔除最大的元素 x 后不能构造,说明 x 是一定要选择或者拆分,此时考虑 xtarget 的影响:
    • 如果 x > target,那么 x 需要先拆分
    • 如果 x ≤ target,那么 x 可以被选择并抵消 target
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
    }
}

复杂度分析:

  • 时间复杂度:O(nlgn + n + U) 瓶颈在排序,枚举阶段每个元素最多访问 1 次,拆分次数最多为 U
  • 空间复杂度:O(lgn) 排序递归栈空间。

T4. 在传球游戏中最大化函数值(Hard)

https://leetcode.cn/problems/maximize-value-of-function-in-a-ball-passing-game/

题解(树上倍增)

从近期周赛的趋势看,出题人似乎有意想把 LeetCode 往偏竞赛的题目引导。

这道题如果知道树上倍增算法,其实比第三题还简单一些。

  • 问题目标: 找到最佳方案,使得从起点开始传球 k 次的路径和最大化;
  • 暴力: 对于暴力的做法,我们可以枚举以每名玩家为起点的方案,并模拟传球过程求出最佳方案。但是这道题的步长 k 的上界非常大 10^{10},如果逐级向上传球,那么单次查询的时间复杂度是 O(k)。现在,需要思考如何优化模拟 k 次传球的效率;
  • 倍增思想: 借鉴 1483. 树节点的第 K 个祖先 的解法,我们可以利用倍增算法将线性的操作施加指数级别的贡献:
    • 如果可以预处理出每个玩家的多级后驱玩家,那么在查询时可以加速跳转;
    • 由于每个数都可以进行二进制拆分为多个 2 的幂的和,如果预处理出第 2^0、2^1、2^2、2^3、...、2^i 个后驱玩家,那么求解第 k 次传球时可以转化为多次 2^i 个后驱玩家跳转操作,大幅减少操作次数。
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
    }
}

复杂度分析:

  • 时间复杂度:预处理时间为 O(nlgk),枚举时间为 O(nlgk),其中 nreceivers 数组的长度;
  • 空间复杂度:预处理空间 O(nlgk)

另外,这道题还有基于「内向基环树」的 O(n) 解法。


推荐阅读

LeetCode 上分之旅系列往期回顾:

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,271评论 5 476
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,275评论 2 380
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,151评论 0 336
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,550评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,553评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,559评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,924评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,580评论 0 257
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,826评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,578评论 2 320
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,661评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,363评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,940评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,926评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,156评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 42,872评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,391评论 2 342

推荐阅读更多精彩内容