LeetCode 周赛 344(2023/05/07)手写递归函数的固定套路

leetcode,手写,递归函数,固定,套路 · 浏览次数 : 161

小编点评

**算法 1(DFS)** ```python class Solution: def minIncrements(self, n: int, cost: list[int]) -> int: def dfs(i: int, cost: list[int], path: list[int]): if i == n // 2: # 终止条件 return cost[i - 1] left_sum = dfs(i * 2, cost, path[:i]) right_sum = dfs(i * 2 + 1, cost, path[:i]) return max(left_sum, right_sum) - min(left_sum, right_sum) return dfs(1, cost, []) ``` **算法 2(迭代)** ```python class Solution: def minIncrements(self, n: int, cost: list[int]) -> int: ret = 0 for i in range(n // 2): ret += abs(cost[i * 2 - 1] - cost[i * 2]) return ret ``` **主要区别:** * **算法 1** 使用递归深度优先搜索 (DFS) 来逐步添加路径上的值,并通过 `max()` 和 `min()` 函数实现路径和的调整。 * **算法 2** 使用迭代遍历的方式,从叶节点开始逐层向上添加路径上的值,并通过计算差值来实现路径和的调整。 **优化:** * 两个算法都使用数组 `cost` 记录子树的子路径和。 * 由于输入数据是满二叉树,因此子树的深度不超过 `log(n)`,其中 `n` 是节点总数。 * 两个算法都通过从叶子的上一层开始迭代向上来实现路径和的调整。 * 算法 1 的时间复杂度为 `O(n)`, 其中 `n` 是节点数;算法 2 的时间复杂度为 `O(n)`, 但它使用了迭代,可以比算法 1 更快。

正文

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。

大家好,我是小彭。

今天下午有力扣杯战队赛,不知道官方是不是故意调低早上周赛难度给选手们练练手。


周赛概览

T1. 找出不同元素数目差数组(Easy)

标签:模拟、计数、散列表

T2. 频率跟踪器(Medium)

标签:模拟、计数、散列表、设计

T3. 有相同颜色的相邻元素数目(Medium)

标签:模拟、计数、贪心

T4. 使二叉树所有路径值相等的最小代价(Medium)

标签:二叉树、DFS、贪心


T1. 找出不同元素数目差数组(Easy)

https://leetcode.cn/problems/find-the-distinct-difference-array/

题解(前后缀分解)

  • 问题目标:求每个位置前缀中不同元素个数和后缀不同元素个数的差值;
  • 观察数据:存在重复数;
  • 解决手段:我们可以计算使用两个散列表计算前缀和后缀中不同元素的差值。考虑到前缀和后缀的数值没有依赖关系,只不过后缀是负权,前缀是正权。那么,我们可以在第一次扫描时将后缀的负权值记录到结果数组中,在第二次扫描时将正权值记录到结果数组中,就可以优化一个散列表空间。

写法 1:

class Solution {
    fun distinctDifferenceArray(nums: IntArray): IntArray {
        val n = nums.size
        val ret = IntArray(n)
        val leftCnts = HashMap<Int, Int>()
        val rightCnts = HashMap<Int, Int>()

        for (e in nums) {
            rightCnts[e] = rightCnts.getOrDefault(e, 0) + 1
        }

        for (i in nums.indices) {
            val e = nums[i]
            leftCnts[e] = leftCnts.getOrDefault(e, 0) + 1
            if (rightCnts[e]!! > 1) rightCnts[e] = rightCnts[e]!! - 1 else rightCnts.remove(e)
            ret[i] = leftCnts.size - rightCnts.size
        }
        return ret
    }
}

写法 2:

class Solution {
    fun distinctDifferenceArray(nums: IntArray): IntArray {
        val n = nums.size
        val ret = IntArray(n)
        val set = HashSet<Int>()

        // 后缀
        for (i in nums.size - 1 downTo 0) {
            ret[i] = -set.size
            set.add(nums[i])
        }

        set.clear()

        // 前缀
        for (i in nums.indices) {
            set.add(nums[i])
            ret[i] += set.size
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 其中 n 为 nums 数组的长度;
  • 空间复杂度:$O(n)$ 散列表空间。

T2. 频率跟踪器(Medium)

https://leetcode.cn/problems/frequency-tracker/

题解(散列表)

简单设计题,使用一个散列表记录数字出现次数,再使用另一个散列表记录出现次数的出现次数:

class FrequencyTracker() {

    // 计数
    private val cnts = HashMap<Int, Int>()

    // 频率计数
    private val freqs = HashMap<Int, Int>()

    fun add(number: Int) {
        // 旧计数
        val oldCnt = cnts.getOrDefault(number, 0)
        // 增加计数
        cnts[number] = oldCnt + 1
        // 减少旧频率计数
        if (freqs.getOrDefault(oldCnt, 0) > 0) // 容错
            freqs[oldCnt] = freqs[oldCnt]!! - 1
        // 增加新频率计数
        freqs[oldCnt + 1] = freqs.getOrDefault(oldCnt + 1, 0) + 1
    }

    fun deleteOne(number: Int) {
        // 未包含
        if (!cnts.contains(number)) return
        // 减少计数
        val oldCnt = cnts[number]!!
        if (0 == oldCnt - 1) cnts.remove(number) else cnts[number] = oldCnt - 1
        // 减少旧频率计数
        freqs[oldCnt] = freqs.getOrDefault(oldCnt, 0) - 1
        // 增加新频率计数
        freqs[oldCnt - 1] = freqs.getOrDefault(oldCnt - 1, 0) + 1
    }

    fun hasFrequency(frequency: Int): Boolean {
        // O(1) 
        return freqs.getOrDefault(frequency, 0) > 0
    }
}

复杂度分析:

  • 时间复杂度:$O(1)$ 每个操作的时间复杂度都是 $O(1)$;
  • 空间复杂度:$O(q)$ 取决于增加的次数 $q$。

T3. 有相同颜色的相邻元素数目(Medium)

https://leetcode.cn/problems/number-of-adjacent-elements-with-the-same-color/description/

题目描述

给你一个下标从 0 开始、长度为 n 的数组 nums 。一开始,所有元素都是 未染色 (值为 0 )的。

给你一个二维整数数组 queries ,其中 queries[i] = [indexi, colori] 。

对于每个操作,你需要将数组 nums 中下标为 indexi 的格子染色为 colori 。

请你返回一个长度与 queries 相等的数组 **answer **,其中 **answer[i]是前 i 个操作 之后 ,相邻元素颜色相同的数目。

更正式的,answer[i] 是执行完前 i 个操作后,0 <= j < n - 1 的下标 j 中,满足 nums[j] == nums[j + 1] 且 nums[j] != 0 的数目。

示例 1:

输入:n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
输出:[0,1,1,0,2]
解释:一开始数组 nums = [0,0,0,0] ,0 表示数组中还没染色的元素。
- 第 1 个操作后,nums = [2,0,0,0] 。相邻元素颜色相同的数目为 0 。
- 第 2 个操作后,nums = [2,2,0,0] 。相邻元素颜色相同的数目为 1 。
- 第 3 个操作后,nums = [2,2,0,1] 。相邻元素颜色相同的数目为 1 。
- 第 4 个操作后,nums = [2,1,0,1] 。相邻元素颜色相同的数目为 0 。
- 第 5 个操作后,nums = [2,1,1,1] 。相邻元素颜色相同的数目为 2 。

示例 2:

输入:n = 1, queries = [[0,100000]]
输出:[0]
解释:一开始数组 nums = [0] ,0 表示数组中还没染色的元素。
- 第 1 个操作后,nums = [100000] 。相邻元素颜色相同的数目为 0 。

提示:

  • 1 <= n <= 105
  • 1 <= queries.length <= 105
  • queries[i].length == 2
  • 0 <= indexi <= n - 1
  • 1 <= colori <= 105

问题结构化

1、概括问题目标

计算每次涂色后相邻颜色的数目个数(与前一个位置颜色相同)。

2、观察问题数据

  • 数据量:查询操作的次数是 10^5,因此每次查询操作的时间复杂度不能高于 O(n)。

3、具体化解决手段

  • 手段 1(暴力枚举):涂色执行一次线性扫描,计算与前一个位置颜色相同的元素个数;
  • 手段 2(枚举优化):由于每次操作最多只会影响 (i - 1, i) 与 (i, i + 1) 两个数对的颜色关系,因此我们没有必要枚举整个数组。

题解一(暴力枚举 · TLE)

class Solution {
    fun colorTheArray(n: Int, queries: Array<IntArray>): IntArray {
        // 只观察 (i - 1, i) 与 (i, i + 1) 两个数对
        if (n <= 0) return intArrayOf(0) // 容错

        val colors = IntArray(n)
        val ret = IntArray(queries.size)

        for (i in queries.indices) {
            val j = queries[i][0]
            val color = queries[i][1]
            if (j < 0 || j >= n) continue // 容错
            colors[j] = color
            for (j in 1 until n) {
                if (0 != colors[j] && colors[j] == colors[j - 1]) ret[i] ++
            }
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n^2)$ 每个操作的时间复杂度都是 O(n);
  • 空间复杂度:$O(n)$ 颜色数组空间。

题解二(枚举优化)

class Solution {
    fun colorTheArray(n: Int, queries: Array<IntArray>): IntArray {
        // 只观察 (i - 1, i) 与 (i, i + 1) 两个数对
        if (n <= 0) return intArrayOf(0) // 容错

        val colors = IntArray(n)
        val ret = IntArray(queries.size)

        // 计数
        var cnt = 0
        for (i in queries.indices) {
            val j = queries[i][0]
            val color = queries[i][1]
            if (j < 0 || j >= n) continue // 容错
            // 消除旧颜色的影响
            if (colors[j] != 0 && j > 0 && colors[j - 1] == colors[j]) cnt--
            // 增加新颜色的影响
            if (colors[j] != 0 && j < n - 1 && colors[j] == colors[j + 1]) cnt--
            if (color != 0) { // 容错
                colors[j] = color
                if (j > 0 && colors[j - 1] == colors[j]) cnt++
                if (j < n - 1 && colors[j] == colors[j + 1]) cnt++
            }
            ret[i] = cnt
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 每个操作的时间复杂度都是 O(1);
  • 空间复杂度:$O(n)$ 颜色数组空间。

相似题目:


T4. 使二叉树所有路径值相等的最小代价(Medium)

https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/

问题描述

给你一个整数 n 表示一棵 满二叉树 里面节点的数目,节点编号从 1 到 n 。根节点编号为 1 ,树中每个非叶子节点 i 都有两个孩子,分别是左孩子 2 * i 和右孩子 2 * i + 1 。

树中每个节点都有一个值,用下标从 0 开始、长度为 n 的整数数组 cost 表示,其中 cost[i] 是第 i + 1 个节点的值。每次操作,你可以将树中 任意 节点的值 增加 1 。你可以执行操作 任意 次。

你的目标是让根到每一个 叶子结点 的路径值相等。请你返回 最少 需要执行增加操作多少次。

注意:

  • 满二叉树 指的是一棵树,它满足树中除了叶子节点外每个节点都恰好有 2 个节点,且所有叶子节点距离根节点距离相同。
  • 路径值 指的是路径上所有节点的值之和。

示例 1:

https://assets.leetcode.com/uploads/2023/04/04/binaryytreeedrawio-4.png

输入:n = 7, cost = [1,5,2,2,3,3,1]
输出:6
解释:我们执行以下的增加操作:
- 将节点 4 的值增加一次。
- 将节点 3 的值增加三次。
- 将节点 7 的值增加两次。
从根到叶子的每一条路径值都为 9 。
总共增加次数为 1 + 3 + 2 = 6 。
这是最小的答案。

示例 2:

https://assets.leetcode.com/uploads/2023/04/04/binaryytreee2drawio.png

输入:n = 3, cost = [5,3,3]
输出:0
解释:两条路径已经有相等的路径值,所以不需要执行任何增加操作。

提示:

  • 3 <= n <= 105
  • n + 1 是 2 的幂
  • cost.length == n
  • 1 <= cost[i] <= 104

问题结构化

1、概括问题目标

计算将所有「根到叶子结点的路径和」调整到相同值的操作次数。

2、分析问题要件

在每一次操作中,可以提高二叉树中某个节点的数值,最终使得该路径和与所有二叉树中其他所有路径和相同。

3、观察问题数据

  • 满二叉树:输入数据是数组物理实现的二叉树,二叉树每个节点的初始值记录在 cost 数组上;
  • 数据量:输入数据量的上界为 10^5,这要求算法的时间复杂度不能高于 O(n^2);
  • 数据大小:二叉树节点的最大值为 10^4,即使将所有节点都调整到 10^4 路径和也不会整型溢出,不需要考虑大数问题。

4、提高抽象程度

  • 最大路径和:由于题目只允许增加节点的值,所以只能让较小路径上的节点值向较大路径上的节点值靠;
  • 公共路径:对于节点「2」的子节点「4」和「5」来说,它们的「父节点和祖先节点走过的路径」必然是公共路径。也就是说,无论从根节点走到节点「2」的路径和是多少,对节点 A 和节点 B 的路径和的影响是相同的。
  • 是否为决策问题:由于每次操作可以调整的选择性很多,因此这是一个决策问题。

5、具体化解决方案

如何解决问题?

结合「公共路径」思考,由于从根节点走到节点「2」的路径和对于两个子节点的影响是相同的,因此对于节点「2」来说,不需要关心父节点的路径和,只需要保证以节点「2」为根节点的子树上所有路径和是相同的。这是一个规模更小的相似子问题,可以用递归解决。

示意图

如何实现递归函数?

  • 思考终止条件:当前节点为叶子节点时,由于没有子路径,所以直接返回;
  • 思考小规模问题:当子节点为叶子节点时,我们只需要保证左右两个叶子节点的值相同(如示例 1 中将节点「4」的值增加到 3)。由于问题的输入数据是满二叉树,所以左右子节点必然同时存在;
  • 思考大规模问题:由于我们保证小规模子树的路径和相同,所以在对比两个子树上的路径和时,只需要调大最小子树的根节点。

至此,我们的递归函数框架确定:

全局变量 int ret
// 返回值:调整后的子树和
fun dfs (i) : Int {
		val sumL = dfs(L)
		val sumR = dfs(R)
		ret += max(sumL, sumR) - min(sumL, sumR) 
		return cost[i] + max(sumL, sumR)
}

6、是否有优化空间

我们使用递归自顶向下地分解子问题,再自底向上地求解原问题。由于这道题的输入是数组形式的满二叉树,对于数组实现的二叉树我们可以直接地从子节点返回到父节点,而不需要借助「递归栈」后进先出的逻辑,可以翻译为迭代来优化空间。

7、答疑

虽然我们保证子树上的子路径是相同的,但是如何保证最终所有子路径都和「最大路径和」相同?

由于我们不断地将左右子树的路径和向较大的路径和对齐,因此最终一定会将所有路径对齐到最大路径和。

为什么算法的操作次数是最少的?

首先,由于左右子树存在「公共路径」,因此必须把左右子树的子路径和调整到相同数值,才能保证最终所有子路径和的长度相同。

其次,当在大规模子树中需要增大路径和时,在父节点操作可以同时作用于左右子路径,因此在父节点操作可以节省操作次数,每个子树只关心影响当前子树问题合法性的因素。

题解一(DFS)

根据「问题结构化」分析的递归伪代码实现:

class Solution {

    private var ret = 0

    fun minIncrements(n: Int, cost: IntArray): Int {
        dfs(n, cost, 1)
        return ret
    }

    // i : base 1
    // cost : base 0
    // return: 调整后的子路径和
    private fun dfs(n: Int, cost: IntArray, i: Int): Int {
        // 终止条件
        if (i > n / 2) return cost[i - 1] // 最后一层是叶子节点
        // 子问题
        val leftSum = dfs(n, cost, i * 2)
        val rightSum = dfs(n, cost, i * 2 + 1)
        // 向较大的子路径对齐
        ret += Math.max(leftSum, rightSum) - Math.min(leftSum, rightSum)
        return cost[i - 1] + Math.max(leftSum, rightSum)
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 其中 n 为 节点数,每个节点最多访问 1 次;
  • 空间复杂度:$O(lgn)$ 递归栈空间,由于输入是满二叉树,所以递归栈深度最大为 lgn。

题解二(迭代)

由于输入数据是满二叉树,而且是以数组的形式提供,因此我们可以跳过递归分解子问题的过程,直接自底向上合并子问题:

class Solution {
    fun minIncrements(n: Int, cost: IntArray): Int {
        var ret = 0
        // 从叶子的上一层开始
        for (i in n / 2 downTo 1) {
            ret += Math.abs(cost[i * 2 - 1] - cost[i * 2])
            // 借助 cost 数组记录子树的子路径和
            cost[i - 1] += Math.max(cost[i * 2 - 1], cost[i * 2])
        }
        return ret
    }
}

复杂度分析:

  • 时间复杂度:$O(n)$ 其中 n 为 节点数,每个节点最多访问 1 次;
  • 空间复杂度:$O(1)$ 仅使用常量级别空间。

往期回顾

与LeetCode 周赛 344(2023/05/07)手写递归函数的固定套路相似的内容:

LeetCode 周赛 344(2023/05/07)手写递归函数的固定套路

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天下午有力扣杯战队赛,不知道官方是不是故意调低早上周赛难度给选手们练练手。 往期周赛回顾:LeetCode 单周赛第 343 场 · 结合「下一个排列」的贪心构造问题 周赛概览 T1.

LeetCode 双周赛 104(2023/05/13)流水的动态规划,铁打的结构化思考

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 往期回顾:LeetCode 单周赛第 344 场 · 手写递归函数的通用套路 T1. 老人的数目(Easy) 标签:模拟、计数 T2. 矩阵中的和(Medium) 标签:模拟、排序 T3. 最大或值(Medi

LeetCode 周赛 332,在套路里摸爬滚打~

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,今天是 3T 选手小彭。 上周是 LeetCode 第 332 场周赛,你参加了吗?算法解题思维需要长时间锻炼,加入我们一起刷题吧~ 小彭的 Android 交流群 02 群已经建立啦,公众号回复 “

LeetCode 周赛 333,你管这叫 Medium 难度?

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周是 LeetCode 第 333 场周赛,你参加了吗?这场周赛质量很高,但难度标得不对,我真的会谢。算法解题思维需要长时间锻炼,加入我们一起刷题吧~ 小彭的 Android 交流群 0

LeetCode 周赛 334,在算法的世界里反复横跳

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天是 LeetCode 第 334 场周赛,你参加了吗?这场周赛考察范围比较基础,整体难度比较平均,第一题难度偏高,第四题需要我们在算法里实现 “反复横跳”,非常有意思。 小彭的 And

LeetCode 周赛 335,纯纯手速场!

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 昨晚是 LeetCode 第 335 场周赛,你参加了吗?这场周赛整体难度不高,有两道模板题,第三题和第四题应该调换一下位置。 小彭的 Android 交流群 02 群来了,公众号回复 “

LeetCode 周赛 336,多少人直接 CV?

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 今天早上是 LeetCode 第 336 场周赛,你参加了吗?这场周赛整体质量比较高,但是最后一题是老题,CV 能过。但是输入数据范围被降低了,这操作也是没谁了。 2587. 统计范围内的

LeetCode 周赛 338,贪心 / 埃氏筛 / 欧氏线性筛 / 前缀和 / 二分查找 / 拓扑排序

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末是 LeetCode 第 338 场周赛,你参加了吗?这场周赛覆盖的知识点很多,第四题称得上是近期几场周赛的天花板。 小彭的技术交流群 02 群来了,公众号回复 “加群” 加入我们~

LeetCode 周赛 340,质数 / 前缀和 / 极大化最小值 / 最短路 / 平衡二叉树

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周跟大家讲到小彭文章风格的问题,和一些朋友聊过以后,至少在算法题解方面确定了小彭的风格。虽然竞赛算法题的文章受众非常小,但却有很多像我一样的初学者,他们有兴趣参加但容易被题目难度和大神选

LeetCode 周赛 341 场,模拟 / 树上差分 / Tarjan 离线 LCA / DFS

本文已收录到 AndroidFamily,技术和职场问题,请关注公众号 [彭旭锐] 提问。 大家好,我是小彭。 上周末有单双周赛,双周赛我们讲过了,单周赛那天早上有事没参加,后面做了虚拟竞赛,然后整个人就不好了。前 3 题非常简单,但第 4 题有点东西啊,差点就放弃了。最后,被折磨了一个下午和一个大