技術文章 » LeetCode 周賽 346（2023/05/21）僅 68 人 AK 的最短路問題

LeetCode 周賽 346（2023/05/21）僅 68 人 AK 的最短路問題

2023-05-23 06:02:01

本文已收錄到 AndroidFamily，技術和職場問題，請關注公眾號 [彭旭銳] 提問。

單週賽 345 概覽

T1. 刪除子串後的字串最小長度（Easy）

標籤：棧

T2. 字典序最小回文串（Medium）

標籤：貪心、雙指標

T3. 求一個整數的懲罰數（Medium）

標籤：回溯、狀態壓縮、字首和

T4. 修改圖中的邊權（Hard）

標籤：貪心、最短路

T1. 刪除子串後的字串最小長度（Easy）

https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/

題解（棧）

使用棧模擬掃描過程，當掃描到 D 和 B 時檢查棧頂元素，最後棧內剩餘的元素個數就是無法消除的最小長度：

class Solution {
    fun minLength(s: String): Int {
        val stack = ArrayDeque<Char>()
        for (c in s) {
            if (c == 'D' && stack.isNotEmpty() && stack.peek() == 'C') stack.pop()
            else if (c == 'B' && stack.isNotEmpty() && stack.peek() == 'A') stack.pop()
            else stack.push(c)
        }
        return stack.size
    }
}

複雜度分析：

  • 時間複雜度：$O(n)$ 其中 n 為 s 字串的長度；
  • 空間複雜度：$O(n)$ 棧空間。

T2. 字典序最小回文串（Medium）

https://leetcode.cn/problems/lexicographically-smallest-palindrome/

題解（貪心）

貪心思路：當對稱位置不相等時，只需要將其中一個位置修改到與另一個位置相同時，得到的操作次數是最少的：

class Solution {
    fun makeSmallestPalindrome(s: String): String {
        val arr = s.toCharArray()
        val n = s.length
        // 判斷迴文串寫法
        for (i in 0 until n / 2) {
            val j = n - 1 - i
            if(arr[i] != arr[j]) {
                val temp = if(arr[i] < arr[j]) arr[i] else arr[j]
                arr[i] = temp
                arr[j] = temp
            }
        }
        return String(arr)
    }
}

複雜度分析：

  • 時間複雜度：$O(n)$ 其中 n 為 s 字串的長度；
  • 空間複雜度：$O(n)$ 字元陣列空間。

T3. 求一個整數的懲罰數（Medium）

https://leetcode.cn/problems/find-the-punishment-number-of-an-integer/

題解一（子集型回溯）

列舉每個數，使用子集型回溯檢查是否存在滿足條件的切分方案：

class Solution {
    fun punishmentNumber(n: Int): Int {
        if (n <= 3) return 1
        var ret = 0
        for (x in 4 .. n) {
            val target = x * x
            if (backTrack("$target", 0, x)) ret += target
        }
        return ret + 1 /* 1 滿足條件 */
    }

    // 子集型回溯
    private fun backTrack(str : String, i : Int, target : Int) : Boolean {
        if (i == str.length) return target == 0
        var cur = 0
        for (to in i until str.length) {
            cur = cur * 10 + (str[to] - '0')
            if (backTrack(str, to + 1, target - cur)) return true
        }
        return false
    }
}

複雜度分析：

  • 時間複雜度：$O(n^2)$ 每個數位 i 轉字串後的長度為 $log_i$，而列舉長度為 $log_i$ 的字串的切分方案後 $2^{log_i}$ = i 種方案，因此整體的時間複雜度是 $O(n^2)$；
  • 空間複雜度：$O(lgn)$ 遞迴棧空間。

題解二（狀態壓縮）

由於數位的長度小於 32，我們可以用 int 表示所有切分方案，再檢查是否存在滿足條件的切分方案：

class Solution {
    fun punishmentNumber(n: Int): Int {
        if (n <= 3) return 1
        var ret = 0
        for (x in 4 .. n) {
            val target = x * x
            if (check("$target", x)) ret += target
        }
        return ret + 1 /* 1 滿足條件 */
    }

    // 狀態壓縮
    private fun check(str : String, target : Int) : Boolean {
        val m = str.length
        val upper = (1 shl m) - 1
        for (k in 1 .. upper) {
            var last = 0
            var sum = 0
            for (i in 0 until m) {
                val cur = str[i] - '0'
                if (k and (1 shl i) != 0) {
                    // 拆
                    sum += last
                    last = cur
                } else{
                    // 不拆
                    last = last * 10 + cur
                }
            }
            if (sum + last == target) return true
        }
        return false
    }
}

複雜度分析：

  • 時間複雜度：同上；
  • 空間複雜度：$O(1)$ 僅使用常數級別空間。

題解三（預處理 + 字首和）

題解一和題解二在多個測試用例間會重複計算相同數位的切分方案，我們可以預處理 1 - 1000 中所有滿足條件的數平方，並維護字首和陣列：

class Solution {

    companion object {
        private val U = 1000
        private val preSum = IntArray(U + 1)
        init {
            for (x in 4 .. U) {
                val target = x * x
                if (check("$target", x)) preSum[x] += target
                preSum[x] += preSum[x - 1]
            }
        }

        // 狀態壓縮
        private fun check(str : String, target : Int) : Boolean {
        }
    }

    fun punishmentNumber(n: Int): Int {
        return preSum[n] + 1
    }
}

複雜度分析：

  • 時間複雜度：$O(U^2)$ 其中 U 是資料大小上界；
  • 空間複雜度：$O(U)$ 字首和陣列空間。

T4. 修改圖中的邊權（Hard）

https://leetcode.cn/problems/modify-graph-edge-weights/submissions/434224996/

LeetCode 少有的難題，排進歷史 Top 10 沒問題吧？

問題無解的情況：

  • 1、假設將所有負權邊設定為 INF（2*10^9）時的最短路長度 dis < target（不論是否經過負權邊），由於無法繼續增大邊權來增大最短路長度，因此問題無解；
  • 2、假設將所有負權邊設定為 1 時的最短路長度 dis > target（不論是否經過負權邊），由於繼續增大邊權最短路不可能變小，因此問題無解。

錯誤的思路：

先把所有負權邊設定為 1，再跑 Dijkstra 最短路，如果最短路長度 dis < target，那麼將其中一條負權邊繼續增大 「target - dis」，就能是該路徑的長度恰好為 target。然而，由於增加權重後最短路長度有可能變化，所以這個思路不能保證正確性。

正確的思路：

  • 1、先把所有負權邊改為 1 跑 Dijkstra 最短路，計算出起點到終點的最短路長度。同時，如果該長度 dis > target，則問題無解；如果該長度 dis == target，則直接返回；如果該長度 dis < target，則需要補全。
  • 2、問題的關鍵在於，按什麼順序修改，以及修改到什麼值。
    • 順序：利用 Dijkstra 最短路演演算法每次使用「確定集」中最短路長度最短的節點去鬆弛其他點的時機，由於修改該點不會影響已確定路徑，因此這是一個不錯的時機；
    • 修改到什麼值：需要滿足 dis[0][x] + w + dis[y][e] = target，那麼有 w = target - dis[0][x] - (dis[0][e] - dis[0][y]) = delta - dis[0][x] + dis[0][y]
  • 3、雖然修改後最短路不一定經過 w，但由於不斷的使用最短路長度最短的節點，因此最終總能修改成功，除非修改後最短路依然小於 target（例如存在直接從 s 到 e 的邊）
  • 4、最後，將未修改的邊增加到 INF。
class Solution {

    private val INF = 1e9.toInt()

    fun modifiedGraphEdges(n: Int, edges: Array<IntArray>, source: Int, destination: Int, target: Int): Array<IntArray> {
        if (source !in 0 .. n - 1 || destination !in 0 .. n - 1) return edges
        if (source == destination || edges.isNullOrEmpty()) return edges
        // 建圖（領接表，節點號 + 邊號方便修改邊權）
        val graph = Array(n) { ArrayList<IntArray>() }
        for ((i, edge) in edges.withIndex()) {
            graph[edge[0]].add(intArrayOf(edge[1], i))
            graph[edge[1]].add(intArrayOf(edge[0], i))
        }
        // 第一輪最短路
        val originDis = dijkstra1(graph, edges, source, destination)
        if (originDis[destination] > target) return emptyArray() // 無解
        // 第二輪最短路
        val delta = target - originDis[destination] // 需要補全的最短路
        val dis = dijkstra2(graph, edges, source, destination, delta, originDis)
        if (dis[destination] < target) return emptyArray() // 無解
        // 修改剩餘邊
        for (edge in edges) {
            if (edge[2] == -1) edge[2] = INF
        }
        return edges
    }

    // return:將 -1 視為 1，並計算從起點到終點的最短路
    private fun dijkstra1(graph:Array<ArrayList<IntArray>>, edges: Array<IntArray>, source :Int, destination:Int) : IntArray {
        val n = graph.size
        val visit = BooleanArray(n)
        val dis = IntArray(n) { INF }
        dis[source] = 0
        while (true) {
            // 尋找最短路長度最短的節點
            var x = -1
            for (i in 0 until n) {
                if (visit[i]) continue
                if (-1 == x || dis[i] < dis[x]) x = i
            }
            if (x == destination) break
            visit[x] = true // 標記
            // 鬆弛相鄰邊
            for (to in graph[x]) {
                var w = edges[to[1]][2]
                if (-1 == w) w = 1 // 視為 1
                if (dis[x] + w < dis[to[0]]) dis[to[0]] = dis[x] + w
            }
        }
        return dis
    }

    // 補全
    private fun dijkstra2(graph:Array<ArrayList<IntArray>>, edges: Array<IntArray>, source :Int, destination:Int, delta: Int, originDis:IntArray /* 首輪計算的最短路 */) : IntArray {
        val n = graph.size
        val visit = BooleanArray(n)
        val dis = IntArray(n) { INF }
        dis[source] = 0
        while (true) {
            // 尋找最短路長度最短的節點
            var x = -1
            for (i in 0 until n) {
                if (visit[i]) continue
                if (-1 == x || dis[i] < dis[x]) x = i
            }
            if (x == destination) break
            visit[x] = true // 標記
            // 鬆弛相鄰邊
            for (to in graph[x]) {
                var w = edges[to[1]][2]
                if (-1 == w) {
                    // 補全（兩次 Dijkstra 只修改這裡）
                    w = Math.max(delta - dis[x] + originDis[to[0]], 1) // 題目要求至少修改到 1
                    if (w >= 1) edges[to[1]][2] = w
                }
                if (dis[x] + w < dis[to[0]]) dis[to[0]] = dis[x] + w
            }
        }
        return dis
    }
}

複雜度分析：

  • 時間複雜度：$O(n^2)$ 兩輪最短路演演算法；
  • 空間複雜度：$O(m)$ 圖空間。

往期回顧