LeetCode 周赛 344（2023/05/07）手写递归函数的通用套路-六虎

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

大家好，我是小彭。

今天下午有力扣杯战队赛，不知道官方是不是成心调低早上星期赛难度给选手们练练手。

往期周赛回忆：LeetCode 单周赛第 343 场结合「下一个摆放」的贪心构造问题

周赛概览

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)$ 色彩数组空间。

类似标题：

567.字符串的摆放

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：

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

示例 2：

输入：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 (l g n)$ 递归栈空间，因为输入是满二叉树，所以递归栈深度最大为 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 单周赛第 343 场结合「下一个摆放」的贪心构造问题
LeetCode 单周赛第 342 场把问题学复杂，再学简略
LeetCode 双周赛第 102 场这次又是最短路。
LeetCode 双周赛第 101 场是时分做出改变了！

LeetCode 周赛 344（2023/05/07）手写递归函数的通用套路

周赛概览

T1. 找出不同元素数目差数组（Easy）

题解（前后缀分解）

T2. 频率跟踪器（Medium）

题解（散列表）

T3. 有相同色彩的相邻元素数目（Medium）

标题描绘

问题结构化

题解一（暴力枚举 TLE）

题解二（枚举优化）

T4. 使二叉树一切途径值持平的最小价值（Medium）

问题描绘

问题结构化

题解一（DFS）

题解二（迭代）

相关文章

Golang 命令模式讲解和代码示例

准确预测极端降水，哥伦比亚大学推出升级版神经网络 Org-NN

我竟然突然焦虑，并且迷茫了

学习能力必然是职场的核心能力

作者信息