T1. 統(tǒng)計(jì)對稱整數(shù)的數(shù)目（Easy）
- 標(biāo)簽：模擬
T2. 生成特殊數(shù)字的最少操作（Medium）
- 標(biāo)簽：思維、回溯硼端、雙指針
T3. 統(tǒng)計(jì)趣味子數(shù)組的數(shù)目（Medium）
- 標(biāo)簽：同余定理萧芙、前綴和给梅、散列表
T4. 邊權(quán)重均等查詢（Hard）
- 標(biāo)簽：圖、倍增双揪、LCA动羽、樹上差分
T1. 統(tǒng)計(jì)對稱整數(shù)的數(shù)目（Easy）
https://leetcode.cn/problems/count-symmetric-integers/
題解（模擬）
根據(jù)題意模擬，亦可以使用前綴和預(yù)處理優(yōu)化渔期。
class Solution {
fun countSymmetricIntegers(low: Int, high: Int): Int {
var ret = 0
for (x in low..high) {
val s = "$x"
val n = s.length
if (n % 2 != 0) continue
var diff = 0
for (i in 0 until n / 2) {
diff += s[i] - '0'
diff -= s[n - 1 - i] - '0'
}
if (diff == 0) ret += 1
}
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
單次檢查時(shí)間為
运吓；
- 空間復(fù)雜度：
僅使用常量級別空間渴邦。
T2. 生成特殊數(shù)字的最少操作（Easy）
https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/
題解一（回溯）
思維題，這道卡了多少人拘哨。
-
閱讀理解： 在一次操作中谋梭，您可以選擇
的任意一位數(shù)字并將其刪除，求最少需要多少次操作可以使
的倍數(shù)倦青；
-
規(guī)律： 對于
種情況時(shí)成立，我們嘗試構(gòu)造出尾部符合兩個(gè)數(shù)字能被
可以用回溯解決：
class Solution {
fun minimumOperations(num: String): Int {
val memo = HashMap<String, Int>()
fun count(x: String): Int {
val n = x.length
if (n == 1) return if (x == "0") 0 else 1
if (((x[n - 2] - '0') * 10 + (x[n - 1]- '0')) % 25 == 0) return 0
if(memo.containsKey(x))return memo[x]!!
val builder1 = StringBuilder(x)
builder1.deleteCharAt(n - 1)
val builder2 = StringBuilder(x)
builder2.deleteCharAt(n - 2)
val ret = 1 + min(count(builder1.toString()), count(builder2.toString()))
memo[x]=ret
return ret
}
return count(num)
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
最多有
種子狀態(tài)峭沦，其中
是字符串的平均長度，
是構(gòu)造中間字符串的時(shí)間逃糟；
- 空間復(fù)雜度：
回溯遞歸椇鹩悖空間。
題解二（雙指針）
初步分析：
- 模擬： 事實(shí)上绰咽，問題的方案最多只有 4 種菇肃，回溯的中間過程事實(shí)在嘗試很多無意義的方案。我們直接枚舉這 4 種方案取募，刪除尾部不屬于該方案的字符琐谤。以 25 為例，就是刪除 5 后面的字符以及刪除 2 與 5 中間的字符玩敏；
- 抽象： 本質(zhì)上是一個(gè)最短匹配子序列的問題斗忌，即 「找到 nums 中最靠后的匹配的最短子序列」問題，可以用雙指針模擬旺聚。
具體實(shí)現(xiàn)：
-
雙指針： 我們找到滿足條件的最靠左的下標(biāo) i织阳，并刪除末尾除了目標(biāo)數(shù)字外的整段元素，即
砰粹；
- 特殊情況： 在 4 種構(gòu)造合法的特殊數(shù)字外唧躲，還存在刪除所有非 0 數(shù)字后構(gòu)造出 0 的方案；
- 是否要驗(yàn)證數(shù)據(jù)含有前導(dǎo)零： 對于構(gòu)造「00」的情況碱璃，是否會(huì)存在刪到最后剩下多個(gè) 0 的情況呢弄痹？其實(shí)是不存在的。因?yàn)轭}目說明輸入數(shù)據(jù) num 本身是不包含前導(dǎo)零的厘贼，如果最后剩下多個(gè) 0 界酒，那么在最左邊的 0 左側(cè)一定存在非 0 數(shù)字，否則與題目說明矛盾嘴秸。
class Solution {
fun minimumOperations(num: String): Int {
val n = num.length
var ret = n
for (choice in arrayOf("00", "25", "50", "75")) {
// 雙指針
var j = 1
for (i in n - 1 downTo 0) {
if (choice[j] != num[i]) continue
if (--j == -1) {
ret = min(ret, n - i - 2)
break
}
}
}
// 特殊情況
ret = min(ret, n - num.count { it == '0'})
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
T3. 統(tǒng)計(jì)趣味子數(shù)組的數(shù)目（Medium）
https://leetcode.cn/problems/count-of-interesting-subarrays/
題解（同余 + 前綴和 + 散列表）
初步分析：
- 問題目標(biāo)： 統(tǒng)計(jì)數(shù)組中滿足目標(biāo)條件的子數(shù)組岳掐；
-
目標(biāo)條件： 在子數(shù)組范圍
內(nèi)凭疮，設(shè)
為滿足
的索引
的數(shù)量，并且
串述。大白話就是算一下有多少數(shù)的模是
执解，再判斷個(gè)數(shù)的模是不是也是
-
權(quán)重： 對于滿足
衰腌，否則是
；
分析到這里觅赊，容易想到用前綴和實(shí)現(xiàn)：
-
前綴和： 記錄從起點(diǎn)到
位置的
區(qū)間范圍內(nèi)滿足目標(biāo)的權(quán)重?cái)?shù)右蕊；
-
兩數(shù)之和： 從左到右枚舉
的方案數(shù)記入結(jié)果吮螺；
-
公式轉(zhuǎn)換： 上式帶有取模運(yùn)算饶囚，我們需要轉(zhuǎn)換一下：
- 原式
- 考慮
是正數(shù)數(shù)的的情況，原式等價(jià)于：
- 考慮
- 聯(lián)合正數(shù)和負(fù)數(shù)兩種情況萝风，即我們需要找到前綴和為
的元素；
- 原式
-
修正前綴和定義： 最后紫岩，我們修改前綴和的定義為權(quán)重
规惰。
組合以上技巧：
class Solution {
fun countInterestingSubarrays(nums: List<Int>, m: Int, k: Int): Long {
val n = nums.size
var ret = 0L
val preSum = HashMap<Int, Int>()
preSum[0] = 1 // 注意空數(shù)組的狀態(tài)
var cur = 0
for (i in 0 until n) {
if (nums[i] % m == k) cur ++ // 更新前綴和
val key = cur % m
val target = (key - k + m) % m
ret += preSum.getOrDefault(target, 0) // 記錄方案
preSum[key] = preSum.getOrDefault(key, 0) + 1 // 記錄前綴和
}
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
- 空間復(fù)雜度：
相似題目：
T4. 邊權(quán)重均等查詢（Hard）
https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/
題解（倍增求 LCA、樹上差分）
初步分析：
-
問題目標(biāo)： 給定若干個(gè)查詢
梨与，要求計(jì)算將
的路徑上的每條邊修改為相同權(quán)重的最少操作次數(shù)堕花；
-
問題要件： 對于每個(gè)查詢
粥鞋，以及邊權(quán)重的眾數(shù)的出現(xiàn)次數(shù)
缘挽，而要修改的操作次數(shù)就是
；
-
技巧： 對于 “樹上路徑” 問題有一種經(jīng)典技巧呻粹，我們可以把
的路徑與
的兩條路徑壕曼；
思考實(shí)現(xiàn)：
-
長度： 將問題轉(zhuǎn)換為經(jīng)過
中轉(zhuǎn)的路徑后，路徑長度
等浊；
-
權(quán)重： 同理腮郊，權(quán)重
可以通過
與
累加計(jì)算；
現(xiàn)在的關(guān)鍵問題是筹燕，如何快速地找到 的最近公共祖先 LCA轧飞？
對于單次 LCA 操作來說衅鹿，我們可以走 DFS 實(shí)現(xiàn) 時(shí)間復(fù)雜度的算法，而對于多次 LCA 操作可以使用 倍增算法 預(yù)處理以空間換時(shí)間过咬，單次 LCA 操作的時(shí)間復(fù)雜度進(jìn)位
大渤。
在 LeetCode 有倍增的模板題 1483. 樹節(jié)點(diǎn)的第 K 個(gè)祖先。
在求 LCA 時(shí)掸绞，我們先把 跳到相同高度泵三，再利用倍增算法向上跳
個(gè)父節(jié)點(diǎn)，直到到達(dá)相同節(jié)點(diǎn)即為最近公共祖先衔掸。
class Solution {
fun minOperationsQueries(n: Int, edges: Array<IntArray>, queries: Array<IntArray>): IntArray {
val U = 26
// 建圖
val graph = Array(n) { LinkedList<IntArray>() }
for (edge in edges) {
graph[edge[0]].add(intArrayOf(edge[1], edge[2] - 1))
graph[edge[1]].add(intArrayOf(edge[0], edge[2] - 1))
}
// 預(yù)處理深度烫幕、倍增祖先節(jié)點(diǎn)、倍增路徑信息
val m = 32 - Integer.numberOfLeadingZeros(n - 1)
val depth = IntArray(n)
val parent = Array(n) { IntArray(m) { -1 }} // parent[i][j] 表示 i 的第 2^j 個(gè)父節(jié)點(diǎn)
val cnt = Array(n) { Array(m) { IntArray(U) }} // cnt[i][j] 表示 <i - 2^j> 個(gè)父節(jié)點(diǎn)的路徑信息
fun dfs(i: Int, par: Int) {
for ((to, w) in graph[i]) {
if (to == par) continue // 避免回環(huán)
depth[to] = depth[i] + 1
parent[to][0] = i
cnt[to][0][w] = 1
dfs(to, i)
}
}
dfs(0, -1) // 選擇 0 作為根節(jié)點(diǎn)
// 預(yù)處理倍增
for (j in 1 until m) {
for (i in 0 until n) {
val from = parent[i][j - 1]
if (-1 != from) {
parent[i][j] = parent[from][j - 1]
cnt[i][j] = cnt[i][j - 1].zip(cnt[from][j - 1]) { e1, e2 -> e1 + e2 }.toIntArray()
}
}
}
// 查詢
val q = queries.size
val ret = IntArray(q)
for ((i, query) in queries.withIndex()) {
var (x, y) = query
// 特判
if (x == y || parent[x][0] == y || parent[y][0] == x) {
ret[i] = 0
}
val w = IntArray(U) // 記錄路徑信息
var path = depth[x] + depth[y] // 記錄路徑長度
// 先跳到相同高度
if (depth[y] > depth[x]) {
val temp = x
x = y
y = temp
}
var k = depth[x] - depth[y]
while (k > 0) {
val j = Integer.numberOfTrailingZeros(k) // 二進(jìn)制分解
w.indices.forEach { w[it] += cnt[x][j][it] } // 記錄路徑信息
x = parent[x][j] // 向上跳 2^j 個(gè)父節(jié)點(diǎn)
k = k and (k - 1)
}
// 再使用倍增找 LCA
if (x != y) {
for (j in m - 1 downTo 0) { // 最多跳 m - 1 次
if (parent[x][j] == parent[y][j]) continue // 跳上去相同就不跳
w.indices.forEach { w[it] += cnt[x][j][it] } // 記錄路徑信息
w.indices.forEach { w[it] += cnt[y][j][it] } // 記錄路徑信息
x = parent[x][j]
y = parent[y][j] // 向上跳 2^j 個(gè)父節(jié)點(diǎn)
}
// 最后再跳一次就是 lca
w.indices.forEach { w[it] += cnt[x][0][it] } // 記錄路徑信息
w.indices.forEach { w[it] += cnt[y][0][it] } // 記錄路徑信息
x = parent[x][0]
}
// 減去重鏈長度
ret[i] = path - 2 * depth[x] - w.max()
}
return ret
}
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：
預(yù)處理的時(shí)間復(fù)雜度是
较曼；
- 空間復(fù)雜度：
