共计 7095 个字符,预计需要花费 18 分钟才能阅读完成。
本文已收录到 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(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 单周赛第 343 场 · 联合「下一个排列」的贪婪结构问题
- LeetCode 单周赛第 342 场 · 把问题学简单,再学简略
- LeetCode 双周赛第 102 场· 这次又是最短路。
- LeetCode 双周赛第 101 场 · 是时候做出扭转了!