LeetCode 周賽上分之旅 #44 同餘字首和問題與經典倍增 LCA 演演算法

⭐️ 本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 和 BaguTree Pro 知識星球提問。

學習資料結構與演演算法的關鍵在於掌握問題背後的演演算法思維框架，你的思考越抽象，它能覆蓋的問題域就越廣，理解難度也更復雜。在這個專欄裡，小彭與你分享每場 LeetCode 周賽的解題報告，一起體會上分之旅。

本文是 LeetCode 上分之旅系列的第 44 篇文章，往期回顧請移步到文章末尾~

T1. 統計對稱整數的數目（Easy）

• 標籤：模擬

T2. 生成特殊數位的最少操作（Medium）

• 標籤：思維、回溯、雙指標

T3. 統計趣味子陣列的數目（Medium）

• 標籤：同餘定理、字首和、雜湊表

T4. 邊權重均等查詢（Hard）

• 標籤：圖、倍增、LCA、樹上差分

---

T1. 統計對稱整數的數目（Easy）

https://leetcode.cn/problems/count-symmetric-integers/

題解（模擬）

根據題意模擬，亦可以使用字首和預處理優化。

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
    }
}

複雜度分析：

• 時間複雜度：$O((high-low)lg^{high})$ 單次檢查時間為 $O(lg^{high})$；
• 空間複雜度：$O(1)$ 僅使用常數級別空間。

---

T2. 生成特殊數位的最少操作（Easy）

https://leetcode.cn/problems/minimum-operations-to-make-a-special-number/

題解一（回溯）

思維題，這道卡了多少人。

• 閱讀理解： 在一次操作中，您可以選擇 $num$ 的任意一位數位並將其刪除，求最少需要多少次操作可以使 $num$ 變成 $25$ 的倍數；
• 規律： 對於 $25$ 的倍數，當且僅當結尾為「00、25、50、75」這 $4$ 種情況時成立，我們嘗試構造出尾部符合兩個數位能被 $25$ 整除的情況。

可以用回溯解決：

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)
    }
}

複雜度分析：

• 時間複雜度：$O(n^2·m)$ 最多有 $n^2$ 種子狀態，其中 $m$ 是字串的平均長度，$O(m)$ 是構造中間字串的時間；
• 空間複雜度：$O(n)$ 回溯遞迴棧空間。

題解二（雙指標）

初步分析：

• 模擬： 事實上，問題的方案最多隻有 4 種，回溯的中間過程事實在嘗試很多無意義的方案。我們直接列舉這 4 種方案，刪除尾部不屬於該方案的字元。以 25 為例，就是刪除 5 後面的字元以及刪除 2 與 5 中間的字元；
• 抽象： 本質上是一個最短匹配子序列的問題，即 「找到 nums 中最靠後的匹配的最短子序列」問題，可以用雙指標模擬。

具體實現：

• 雙指標： 我們找到滿足條件的最靠左的下標 i，並刪除末尾除了目標數位外的整段元素，即 $ret = n - i - 2$；
• 特殊情況： 在 4 種構造合法的特殊數位外，還存在刪除所有非 0 數位後構造出 0 的方案；
• 是否要驗證資料含有前導零： 對於構造「00」的情況，是否會存在刪到最後剩下多個 0 的情況呢？其實是不存在的。因為題目說明輸入資料 num 本身是不包含前導零的，如果最後剩下多個 0 ，那麼在最左邊的 0 左側一定存在非 0 數位，否則與題目說明矛盾。

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
    }
}

複雜度分析：

• 時間複雜度：$O(n)$ 4 種方案和特殊方案均是線性遍歷；
• 空間複雜度：$O(1)$ 僅使用常數級別空間。

---

T3. 統計趣味子陣列的數目（Medium）

https://leetcode.cn/problems/count-of-interesting-subarrays/

題解（同餘 + 字首和 + 雜湊表）

初步分析：

• 問題目標： 統計陣列中滿足目標條件的子陣列；
• 目標條件： 在子陣列範圍 $[l, r]$ 內，設 $cnt$ 為滿足 $nums[i] % m == k$ 的索引 $i$ 的數量，並且 $cnt % m == k$。大白話就是算一下有多少數的模是 $k$，再判斷個數的模是不是也是 $k$；
• 權重： 對於滿足 $nums[i] % m == k$ 的元素，它對結果的貢獻是 $1$，否則是 $0$；

分析到這裡，容易想到用字首和實現：

• 字首和： 記錄從起點到 $[i]$ 位置的 $[0, i]$ 區間範圍內滿足目標的權重數；
• 兩數之和： 從左到右列舉 $[i]$，並尋找已經遍歷的位置中滿足 $(preSum[i] - preSum[j]) % m == k$ 的方案數記入結果；
• 公式轉換： 上式帶有取模運算，我們需要轉換一下：
  • 原式 $(preSum[i] - preSum[j]) % m == k$
  • 考慮 $preSum[i] % m - preSum[j] % m$ 是正數數的的情況，原式等價於：$preSum[i] % m - preSum[j] % m == k$
  • 考慮 $preSum[i] % m - preSum[j] % m$ 是負數的的情況，我們在等式左邊增加補數：$(preSum[i] % m - preSum[j] % m + m) %m == k$
  • 聯合正數和負數兩種情況，即我們需要找到字首和為 $(preSum[i] % m - k + m) % m$ 的元素；
• 修正字首和定義： 最後，我們修改字首和的定義為權重 $% m$。

組合以上技巧：

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 // 注意空陣列的狀態
        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
    }
}

複雜度分析：

• 時間複雜度：$O(n)$ 線性遍歷，單次查詢時間為 $O(1)$；
• 空間複雜度：$O(m)$ 雜湊表空間。

相似題目：

• 560. 和為 K 的子陣列
• 974. 和可被 K 整除的子陣列
• 523. 連續的子陣列和
• 525. 連續陣列

---

T4. 邊權重均等查詢（Hard）

https://leetcode.cn/problems/minimum-edge-weight-equilibrium-queries-in-a-tree/

題解（倍增求 LCA、樹上差分）

初步分析：

• 問題目標： 給定若干個查詢 $[x, y]$，要求計算將 $<x, y>$ 的路徑上的每條邊修改為相同權重的最少操作次數；
• 問題要件： 對於每個查詢 $[x, y]$，我們需要計算 $<x, y>$ 的路徑長度 $l$，以及邊權重的眾數的出現次數 $c$，而要修改的操作次數就是 $l - c$；
• 技巧： 對於 「樹上路徑」 問題有一種經典技巧，我們可以把 $<x, y>$ 的路徑轉換為從 $<x, lca>$ 的路徑與 $<lca, y>$ 的兩條路徑；

思考實現：

• 長度： 將問題轉換為經過 $lca$ 中轉的路徑後，路徑長度 $l$ 可以用深度來計算：$l = depth[x] + depth[y] - 2 * depth[lca]$；
• 權重： 同理，權重 $w[x,y]$ 可以通過 $w[x, lca]$ 與 $w[lca, y]$ 累加計算；

現在的關鍵問題是，如何快速地找到 $<x, y>$ 的最近公共祖先 LCA？

對於單次 LCA 操作來說，我們可以走 DFS 實現 $O(n)$ 時間複雜度的演演算法，而對於多次 LCA 操作可以使用 倍增演演算法 預處理以空間換時間，單次 LCA 操作的時間複雜度進位 $O(lgn)$。

在 LeetCode 有倍增的模板題 1483. 樹節點的第 K 個祖先。

在求 LCA 時，我們先把 $<x, y>$ 跳到相同高度，再利用倍增演演算法向上跳 $2^j$ 個父節點，直到到達相同節點即為最近公共祖先。

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))
        }

        // 預處理深度、倍增祖先節點、倍增路徑資訊
        val m = 32 - Integer.numberOfLeadingZeros(n - 1)
        val depth = IntArray(n)
        val parent = Array(n) { IntArray(m) { -1 }} // parent[i][j] 表示 i 的第 2^j 個父節點
        val cnt = Array(n) { Array(m) { IntArray(U) }} // cnt[i][j] 表示 <i - 2^j> 個父節點的路徑資訊
        
        fun dfs(i: Int, par: Int) {
            for ((to, w) in graph[i]) {
                if (to == par) continue // 避免迴環
                depth[to] = depth[i] + 1
                parent[to][0] = i
                cnt[to][0][w] = 1
                dfs(to, i)
            }
        }

        dfs(0, -1) // 選擇 0 作為根節點

        // 預處理倍增
        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) // 二進位制分解
                w.indices.forEach { w[it] += cnt[x][j][it] } // 記錄路徑資訊
                x = parent[x][j] // 向上跳 2^j 個父節點
                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 個父節點
                }
                // 最後再跳一次就是 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
    }
}

複雜度分析：

• 時間複雜度：$O(nlgn·U)$ 預處理的時間複雜度是 $O(nlgn·U)$，單次查詢的時間是 $O(lgn·U)$；
• 空間複雜度：$O(nlgn·U)$ 預處理倍增資訊空間。

---

推薦閱讀

LeetCode 上分之旅系列往期回顧：

• LeetCode 單週賽第 360 場 · 當 LeetCode 考樹上倍增，出題的趨勢在變化嗎
• LeetCode 單週賽第 359 場 · 結合離散化的線性 DP 問題
• LeetCode 雙週賽第 112 場 · 電腦科學本質上是數學嗎？
• LeetCode 雙週賽第 111 場 · 按部就班地解決動態規劃問題

⭐️ 永遠相信美好的事情即將發生，歡迎加入小彭的 Android 交流社群~