大家好液斜，我是小彭累贤。
今天下午有力扣杯戰(zhàn)隊(duì)賽，不知道官方是不是故意調(diào)低早上周賽難度給選手們練練手少漆。
周賽概覽
T1. 找出不同元素?cái)?shù)目差數(shù)組（Easy）
標(biāo)簽：模擬臼膏、計(jì)數(shù)、散列表
T2. 頻率跟蹤器（Medium）
標(biāo)簽：模擬示损、計(jì)數(shù)渗磅、散列表、設(shè)計(jì)
T3. 有相同顏色的相鄰元素?cái)?shù)目（Medium）
標(biāo)簽：模擬检访、計(jì)數(shù)始鱼、貪心
T4. 使二叉樹(shù)所有路徑值相等的最小代價(jià)（Medium）
標(biāo)簽：二叉樹(shù)、DFS脆贵、貪心
T1. 找出不同元素?cái)?shù)目差數(shù)組（Easy）
https://leetcode.cn/problems/find-the-distinct-difference-array/
題解（前后綴分解）
- 問(wèn)題目標(biāo)：求每個(gè)位置前綴中不同元素個(gè)數(shù)和后綴不同元素個(gè)數(shù)的差值医清；
- 觀察數(shù)據(jù)：存在重復(fù)數(shù)；
- 解決手段：我們可以計(jì)算使用兩個(gè)散列表計(jì)算前綴和后綴中不同元素的差值卖氨』崂樱考慮到前綴和后綴的數(shù)值沒(méi)有依賴關(guān)系，只不過(guò)后綴是負(fù)權(quán)筒捺，前綴是正權(quán)柏腻。那么，我們可以在第一次掃描時(shí)將后綴的負(fù)權(quán)值記錄到結(jié)果數(shù)組中系吭，在第二次掃描時(shí)將正權(quán)值記錄到結(jié)果數(shù)組中五嫂，就可以優(yōu)化一個(gè)散列表空間。
寫(xiě)法 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
}
}
寫(xiě)法 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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
其中 n 為 nums 數(shù)組的長(zhǎng)度村斟；
- 空間復(fù)雜度：
T2. 頻率跟蹤器（Medium）
https://leetcode.cn/problems/frequency-tracker/
題解（散列表）
簡(jiǎn)單設(shè)計(jì)題，使用一個(gè)散列表記錄數(shù)字出現(xiàn)次數(shù)蟆盹，再使用另一個(gè)散列表記錄出現(xiàn)次數(shù)的出現(xiàn)次數(shù)：
class FrequencyTracker() {
// 計(jì)數(shù)
private val cnts = HashMap<Int, Int>()
// 頻率計(jì)數(shù)
private val freqs = HashMap<Int, Int>()
fun add(number: Int) {
// 舊計(jì)數(shù)
val oldCnt = cnts.getOrDefault(number, 0)
// 增加計(jì)數(shù)
cnts[number] = oldCnt + 1
// 減少舊頻率計(jì)數(shù)
if (freqs.getOrDefault(oldCnt, 0) > 0) // 容錯(cuò)
freqs[oldCnt] = freqs[oldCnt]!! - 1
// 增加新頻率計(jì)數(shù)
freqs[oldCnt + 1] = freqs.getOrDefault(oldCnt + 1, 0) + 1
}
fun deleteOne(number: Int) {
// 未包含
if (!cnts.contains(number)) return
// 減少計(jì)數(shù)
val oldCnt = cnts[number]!!
if (0 == oldCnt - 1) cnts.remove(number) else cnts[number] = oldCnt - 1
// 減少舊頻率計(jì)數(shù)
freqs[oldCnt] = freqs.getOrDefault(oldCnt, 0) - 1
// 增加新頻率計(jì)數(shù)
freqs[oldCnt - 1] = freqs.getOrDefault(oldCnt - 1, 0) + 1
}
fun hasFrequency(frequency: Int): Boolean {
// O(1)
return freqs.getOrDefault(frequency, 0) > 0
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
每個(gè)操作的時(shí)間復(fù)雜度都是
- 空間復(fù)雜度：
取決于增加的次數(shù)
。
T3. 有相同顏色的相鄰元素?cái)?shù)目（Medium）
https://leetcode.cn/problems/number-of-adjacent-elements-with-the-same-color/description/
題目描述
給你一個(gè)下標(biāo)從 0 開(kāi)始逾滥、長(zhǎng)度為 n 的數(shù)組 nums 峰档。一開(kāi)始，所有元素都是 未染色 （值為 0 ）的寨昙。
給你一個(gè)二維整數(shù)數(shù)組 queries 讥巡，其中 queries[i] = [indexi, colori] 。
對(duì)于每個(gè)操作舔哪，你需要將數(shù)組 nums 中下標(biāo)為 indexi 的格子染色為 colori 欢顷。
請(qǐng)你返回一個(gè)長(zhǎng)度與 queries 相等的數(shù)組 **answer **，其中 **answer[i]是前 i 個(gè)操作 之后 捉蚤，相鄰元素顏色相同的數(shù)目抬驴。
更正式的，answer[i] 是執(zhí)行完前 i 個(gè)操作后缆巧，0 <= j < n - 1 的下標(biāo) j 中布持，滿足 nums[j] == nums[j + 1] 且 nums[j] != 0 的數(shù)目。
示例 1：
輸入：n = 4, queries = [[0,2],[1,2],[3,1],[1,1],[2,1]]
輸出：[0,1,1,0,2]
解釋?zhuān)阂婚_(kāi)始數(shù)組 nums = [0,0,0,0] 陕悬，0 表示數(shù)組中還沒(méi)染色的元素题暖。
- 第 1 個(gè)操作后，nums = [2,0,0,0] 捉超。相鄰元素顏色相同的數(shù)目為 0 胧卤。
- 第 2 個(gè)操作后，nums = [2,2,0,0] 狂秦。相鄰元素顏色相同的數(shù)目為 1 灌侣。
- 第 3 個(gè)操作后，nums = [2,2,0,1] 裂问。相鄰元素顏色相同的數(shù)目為 1 侧啼。
- 第 4 個(gè)操作后，nums = [2,1,0,1] 堪簿。相鄰元素顏色相同的數(shù)目為 0 痊乾。
- 第 5 個(gè)操作后，nums = [2,1,1,1] 椭更。相鄰元素顏色相同的數(shù)目為 2 哪审。
示例 2：
輸入：n = 1, queries = [[0,100000]]
輸出：[0]
解釋?zhuān)阂婚_(kāi)始數(shù)組 nums = [0] ，0 表示數(shù)組中還沒(méi)染色的元素虑瀑。
- 第 1 個(gè)操作后湿滓，nums = [100000] 滴须。相鄰元素顏色相同的數(shù)目為 0 。
提示：
1 <= n <= 1051 <= queries.length <= 105queries[i].length == 20 <= indexi <= n - 11 <= colori <= 105
問(wèn)題結(jié)構(gòu)化
1叽奥、概括問(wèn)題目標(biāo)
計(jì)算每次涂色后相鄰顏色的數(shù)目個(gè)數(shù)（與前一個(gè)位置顏色相同）扔水。
2、觀察問(wèn)題數(shù)據(jù)
- 數(shù)據(jù)量：查詢操作的次數(shù)是 10^5朝氓，因此每次查詢操作的時(shí)間復(fù)雜度不能高于 O(n)魔市。
3、具體化解決手段
- 手段 1（暴力枚舉）：涂色執(zhí)行一次線性掃描赵哲，計(jì)算與前一個(gè)位置顏色相同的元素個(gè)數(shù)待德；
- 手段 2（枚舉優(yōu)化）：由于每次操作最多只會(huì)影響 (i - 1, i) 與 (i, i + 1) 兩個(gè)數(shù)對(duì)的顏色關(guān)系，因此我們沒(méi)有必要枚舉整個(gè)數(shù)組枫夺。
題解一（暴力枚舉 · TLE）
class Solution {
fun colorTheArray(n: Int, queries: Array<IntArray>): IntArray {
// 只觀察 (i - 1, i) 與 (i, i + 1) 兩個(gè)數(shù)對(duì)
if (n <= 0) return intArrayOf(0) // 容錯(cuò)
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 // 容錯(cuò)
colors[j] = color
for (j in 1 until n) {
if (0 != colors[j] && colors[j] == colors[j - 1]) ret[i] ++
}
}
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
每個(gè)操作的時(shí)間復(fù)雜度都是 O(n)将宪；
- 空間復(fù)雜度：
題解二（枚舉優(yōu)化）
class Solution {
fun colorTheArray(n: Int, queries: Array<IntArray>): IntArray {
// 只觀察 (i - 1, i) 與 (i, i + 1) 兩個(gè)數(shù)對(duì)
if (n <= 0) return intArrayOf(0) // 容錯(cuò)
val colors = IntArray(n)
val ret = IntArray(queries.size)
// 計(jì)數(shù)
var cnt = 0
for (i in queries.indices) {
val j = queries[i][0]
val color = queries[i][1]
if (j < 0 || j >= n) continue // 容錯(cuò)
// 消除舊顏色的影響
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) { // 容錯(cuò)
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
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
相似題目：
T4. 使二叉樹(shù)所有路徑值相等的最小代價(jià)（Medium）
https://leetcode.cn/problems/make-costs-of-paths-equal-in-a-binary-tree/
問(wèn)題描述
給你一個(gè)整數(shù) n 表示一棵 滿二叉樹(shù) 里面節(jié)點(diǎn)的數(shù)目，節(jié)點(diǎn)編號(hào)從 1 到 n 毙死。根節(jié)點(diǎn)編號(hào)為 1 燎潮，樹(shù)中每個(gè)非葉子節(jié)點(diǎn) i 都有兩個(gè)孩子，分別是左孩子 2 * i 和右孩子 2 * i + 1 扼倘。
樹(shù)中每個(gè)節(jié)點(diǎn)都有一個(gè)值确封，用下標(biāo)從 0 開(kāi)始、長(zhǎng)度為 n 的整數(shù)數(shù)組 cost 表示再菊，其中 cost[i] 是第 i + 1 個(gè)節(jié)點(diǎn)的值爪喘。每次操作，你可以將樹(shù)中 任意 節(jié)點(diǎn)的值 增加 1 纠拔。你可以執(zhí)行操作 任意 次秉剑。
你的目標(biāo)是讓根到每一個(gè) 葉子結(jié)點(diǎn) 的路徑值相等。請(qǐng)你返回 最少 需要執(zhí)行增加操作多少次稠诲。
注意：
- 滿二叉樹(shù) 指的是一棵樹(shù)侦鹏，它滿足樹(shù)中除了葉子節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)都恰好有 2 個(gè)節(jié)點(diǎn)，且所有葉子節(jié)點(diǎn)距離根節(jié)點(diǎn)距離相同臀叙。
- 路徑值 指的是路徑上所有節(jié)點(diǎn)的值之和略水。
示例 1：
輸入：n = 7, cost = [1,5,2,2,3,3,1]
輸出：6
解釋?zhuān)何覀儓?zhí)行以下的增加操作：
- 將節(jié)點(diǎn) 4 的值增加一次。
- 將節(jié)點(diǎn) 3 的值增加三次劝萤。
- 將節(jié)點(diǎn) 7 的值增加兩次渊涝。
從根到葉子的每一條路徑值都為 9 。
總共增加次數(shù)為 1 + 3 + 2 = 6 。
這是最小的答案跨释。
示例 2：
輸入：n = 3, cost = [5,3,3]
輸出：0
解釋?zhuān)簝蓷l路徑已經(jīng)有相等的路徑值胸私，所以不需要執(zhí)行任何增加操作。
提示：
3 <= n <= 105-
n + 1是2的冪 cost.length == n1 <= cost[i] <= 104
問(wèn)題結(jié)構(gòu)化
1鳖谈、概括問(wèn)題目標(biāo)
計(jì)算將所有「根到葉子結(jié)點(diǎn)的路徑和」調(diào)整到相同值的操作次數(shù)盖文。
2、分析問(wèn)題要件
在每一次操作中蚯姆，可以提高二叉樹(shù)中某個(gè)節(jié)點(diǎn)的數(shù)值，最終使得該路徑和與所有二叉樹(shù)中其他所有路徑和相同洒敏。
3龄恋、觀察問(wèn)題數(shù)據(jù)
- 滿二叉樹(shù)：輸入數(shù)據(jù)是數(shù)組物理實(shí)現(xiàn)的二叉樹(shù)，二叉樹(shù)每個(gè)節(jié)點(diǎn)的初始值記錄在 cost 數(shù)組上凶伙；
- 數(shù)據(jù)量：輸入數(shù)據(jù)量的上界為 10^5郭毕，這要求算法的時(shí)間復(fù)雜度不能高于 O(n^2)；
- 數(shù)據(jù)大泻佟：二叉樹(shù)節(jié)點(diǎn)的最大值為 10^4显押，即使將所有節(jié)點(diǎn)都調(diào)整到 10^4 路徑和也不會(huì)整型溢出，不需要考慮大數(shù)問(wèn)題傻挂。
4乘碑、提高抽象程度
- 最大路徑和：由于題目只允許增加節(jié)點(diǎn)的值，所以只能讓較小路徑上的節(jié)點(diǎn)值向較大路徑上的節(jié)點(diǎn)值靠金拒；
- 公共路徑：對(duì)于節(jié)點(diǎn)「2」的子節(jié)點(diǎn)「4」和「5」來(lái)說(shuō)兽肤，它們的「父節(jié)點(diǎn)和祖先節(jié)點(diǎn)走過(guò)的路徑」必然是公共路徑。也就是說(shuō)绪抛，無(wú)論從根節(jié)點(diǎn)走到節(jié)點(diǎn)「2」的路徑和是多少资铡，對(duì)節(jié)點(diǎn) A 和節(jié)點(diǎn) B 的路徑和的影響是相同的。
- 是否為決策問(wèn)題：由于每次操作可以調(diào)整的選擇性很多幢码，因此這是一個(gè)決策問(wèn)題笤休。
5、具體化解決方案
如何解決問(wèn)題症副？
結(jié)合「公共路徑」思考店雅，由于從根節(jié)點(diǎn)走到節(jié)點(diǎn)「2」的路徑和對(duì)于兩個(gè)子節(jié)點(diǎn)的影響是相同的，因此對(duì)于節(jié)點(diǎn)「2」來(lái)說(shuō)贞铣，不需要關(guān)心父節(jié)點(diǎn)的路徑和底洗，只需要保證以節(jié)點(diǎn)「2」為根節(jié)點(diǎn)的子樹(shù)上所有路徑和是相同的。這是一個(gè)規(guī)模更小的相似子問(wèn)題咕娄，可以用遞歸解決亥揖。
示意圖
如何實(shí)現(xiàn)遞歸函數(shù)？
- 思考終止條件：當(dāng)前節(jié)點(diǎn)為葉子節(jié)點(diǎn)時(shí)，由于沒(méi)有子路徑费变，所以直接返回摧扇；
- 思考小規(guī)模問(wèn)題：當(dāng)子節(jié)點(diǎn)為葉子節(jié)點(diǎn)時(shí)，我們只需要保證左右兩個(gè)葉子節(jié)點(diǎn)的值相同（如示例 1 中將節(jié)點(diǎn)「4」的值增加到 3）挚歧。由于問(wèn)題的輸入數(shù)據(jù)是滿二叉樹(shù)扛稽，所以左右子節(jié)點(diǎn)必然同時(shí)存在；
- 思考大規(guī)模問(wèn)題：由于我們保證小規(guī)模子樹(shù)的路徑和相同滑负，所以在對(duì)比兩個(gè)子樹(shù)上的路徑和時(shí)在张，只需要調(diào)大最小子樹(shù)的根節(jié)點(diǎn)。
至此矮慕，我們的遞歸函數(shù)框架確定：
全局變量 int ret
// 返回值：調(diào)整后的子樹(shù)和
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帮匾、是否有優(yōu)化空間
我們使用遞歸自頂向下地分解子問(wèn)題，再自底向上地求解原問(wèn)題痴鳄。由于這道題的輸入是數(shù)組形式的滿二叉樹(shù)瘟斜，對(duì)于數(shù)組實(shí)現(xiàn)的二叉樹(shù)我們可以直接地從子節(jié)點(diǎn)返回到父節(jié)點(diǎn)，而不需要借助「遞歸椈狙埃」后進(jìn)先出的邏輯螺句，可以翻譯為迭代來(lái)優(yōu)化空間。
7橡类、答疑
雖然我們保證子樹(shù)上的子路徑是相同的蛇尚，但是如何保證最終所有子路徑都和「最大路徑和」相同？
由于我們不斷地將左右子樹(shù)的路徑和向較大的路徑和對(duì)齊顾画，因此最終一定會(huì)將所有路徑對(duì)齊到最大路徑和佣蓉。
為什么算法的操作次數(shù)是最少的？
首先亲雪，由于左右子樹(shù)存在「公共路徑」勇凭，因此必須把左右子樹(shù)的子路徑和調(diào)整到相同數(shù)值，才能保證最終所有子路徑和的長(zhǎng)度相同。
其次，當(dāng)在大規(guī)模子樹(shù)中需要增大路徑和時(shí)瑟幕，在父節(jié)點(diǎn)操作可以同時(shí)作用于左右子路徑嫂伞，因此在父節(jié)點(diǎn)操作可以節(jié)省操作次數(shù)，每個(gè)子樹(shù)只關(guān)心影響當(dāng)前子樹(shù)問(wèn)題合法性的因素。
題解一（DFS）
根據(jù)「問(wèn)題結(jié)構(gòu)化」分析的遞歸偽代碼實(shí)現(xiàn)：
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: 調(diào)整后的子路徑和
private fun dfs(n: Int, cost: IntArray, i: Int): Int {
// 終止條件
if (i > n / 2) return cost[i - 1] // 最后一層是葉子節(jié)點(diǎn)
// 子問(wèn)題
val leftSum = dfs(n, cost, i * 2)
val rightSum = dfs(n, cost, i * 2 + 1)
// 向較大的子路徑對(duì)齊
ret += Math.max(leftSum, rightSum) - Math.min(leftSum, rightSum)
return cost[i - 1] + Math.max(leftSum, rightSum)
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
遞歸椪合牛空間，由于輸入是滿二叉樹(shù)撩幽，所以遞歸棧深度最大為 lgn库继。
題解二（迭代）
由于輸入數(shù)據(jù)是滿二叉樹(shù)箩艺，而且是以數(shù)組的形式提供，因此我們可以跳過(guò)遞歸分解子問(wèn)題的過(guò)程宪萄，直接自底向上合并子問(wèn)題：
class Solution {
fun minIncrements(n: Int, cost: IntArray): Int {
var ret = 0
// 從葉子的上一層開(kāi)始
for (i in n / 2 downTo 1) {
ret += Math.abs(cost[i * 2 - 1] - cost[i * 2])
// 借助 cost 數(shù)組記錄子樹(shù)的子路徑和
cost[i - 1] += Math.max(cost[i * 2 - 1], cost[i * 2])
}
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
往期回顧
