技術文章 » LeetCode 雙週賽 101，DP/中心位貪心/裴蜀定理/Dijkstra/最小環

LeetCode 雙週賽 101，DP/中心位貪心/裴蜀定理/Dijkstra/最小環

2023-04-09 06:00:37

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

大家好，我是小彭。

這周比較忙，上週末的雙週賽題解現在才更新，雖遲但到哈。上週末這場是 LeetCode 第 101 場雙週賽，整體有點難度，第 3 題似乎比第 4 題還難一些。

周賽大綱

2605. 從兩個數位陣列裡生成最小數位（Easy）

  • 題解一：雜湊表 $O(n + m)$ 空間
  • 題解二：位運算 $O(1)$ 空間

2606. 找到最大開銷的子字串（Medium）

  • 動態規劃 O(n)

2607. 使子陣列元素和相等（Medium）

  • 題解 1：拼接陣列 + 中位數貪心 · 錯誤
  • 題解 2：陣列分組 + 中位數貪心 $O(nlgn)$
  • 題解 3：裴蜀定理 + 中位數貪心 $O(nlgn)$
  • 題解 4：裴蜀定理 + 中位數貪心 + 快速選擇 $O(n)$

2608. 圖中的最短環（Hard）

  • 題解 1：列舉邊 + Dijkstra 最短路 + 最小堆 $O(m + m^2·lgn)$
  • 題解 2：列舉邊 + BFS $O(m + m^2)$

2605. 從兩個數位陣列裡生成最小數位（Easy）

題目地址

https://leetcode.cn/problems/form-smallest-number-from-two-digit-arrays/description/

題目描述

給你兩個只包含 1 到 9 之間數位的陣列 nums1 和 nums2 ，每個陣列中的元素 互不相同 ，請你返回 最小 的數位，兩個陣列都 至少 包含這個數位的某個數位。

題解一（雜湊表）

簡單模擬題，需要對 API 比較熟悉才能寫出精煉的程式碼。

思路：優先選擇兩個陣列交集的最小值，否則取兩個陣列的最小值再拼接。

class Solution {
    fun minNumber(nums1: IntArray, nums2: IntArray): Int {
        val set1 = nums1.toHashSet()
        val set2 = nums2.toHashSet()
        // 優先選擇交集
        val set = set1.intersect(set2)
        if (!set.isEmpty()) return Collections.min(set)
        // 選擇最小值
        val min1 = Collections.min(set1)
        val min2 = Collections.min(set2)
        // 拼接
        return Math.min(10 * min1 + min2, 10 * min2 + min1)
    }
}

複雜度分析：

  • 時間複雜度：$O(n + m)$ 其中 $n$ 是 $nums1$ 陣列的長度，$m$ 是 $nums2$ 陣列的長度；
  • 空間複雜度：$O(n + m)$ 雜湊表空間

題解二（位運算）

使用二進位制位標記代替雜湊表

class Solution {
    fun minNumber(nums1: IntArray, nums2: IntArray): Int {
        var flag1 = 0
        var flag2 = 0
        for (num in nums1) {
            flag1 = flag1 or (1 shl num)
        }
        for (num in nums2) {
            flag2 = flag2 or (1 shl num)
        }
        // numberOfTrailingZeros：最低位連續 0 的個數
        // 交集
        val flag = flag1 and flag2
        if (flag > 0) return Integer.numberOfTrailingZeros(flag)
        // 最小值
        val min1 = Integer.numberOfTrailingZeros(flag1)
        val min2 = Integer.numberOfTrailingZeros(flag2)
        // 拼接
        return Math.min(10 * min1 + min2, 10 * min2 + min1)
    }
}

複雜度分析：

  • 時間複雜度：$O(n + m)$ 其中 $n$ 是 $nums1$ 陣列的長度，$m$ 是 $nums2$ 陣列的長度；
  • 空間複雜度：$O(1)$ 雜湊表空間

2606. 找到最大開銷的子字串（Medium）

題目地址

https://leetcode.cn/problems/find-the-substring-with-maximum-cost/

題目描述

給你一個字串 s ，一個字元 互不相同 的字串 chars 和一個長度與 chars 相同的整數陣列 vals 。

子字串的開銷 是一個子字串中所有字元對應價值之和。空字串的開銷是 0 。

字元的價值 定義如下：

  • 如果字元不在字串 chars 中，那麼它的價值是它在字母表中的位置（下標從 1 開始）。
    • 比方說，'a' 的價值為 1 ，'b' 的價值為 2 ，以此類推，'z' 的價值為 26 。
  • 否則，如果這個字元在 chars 中的位置為 i ，那麼它的價值就是 vals[i] 。

請你返回字串 s 的所有子字串中的最大開銷。

題解（動態規劃）

簡單動態規劃問題。

先根據題意維護 a-z 每個字母的開銷，再求 53. 最長子陣列和 問題。

定義 dp[i] 表示以 [i] 為結尾的最大子陣列和，則有

  • 與 $a[0, i - 1]$ 拼接：$dp[i] = dp[i - 1] + vals[i]$
  • 不與 $a[i - 1]$ 拼接（單獨作為子陣列）：$dp[i] = vals[i]$
class Solution {
    fun maximumCostSubstring(s: String, chars: String, vals: IntArray): Int {
        // 初值
        val fullVals = IntArray(26) { it + 1 }
        // 更新
        for ((i, c) in chars.withIndex()) {
            fullVals[c - 'a'] = vals[i]
        }
        // 動態規劃
        val n = s.length
        var max = 0
        val dp = IntArray(n + 1)
        for (i in 1..n) {
            val curValue = fullVals[s[i - 1] - 'a']
            dp[i] = Math.max(curValue, dp[i - 1] + curValue)
            max = Math.max(max, dp[i])
        }
        return max
    }
}

捲動陣列優化：

class Solution {
    fun maximumCostSubstring(s: String, chars: String, vals: IntArray): Int {
        // 初值
        val fullVals = IntArray(26) { it + 1 }
        // 更新
        for ((i, c) in chars.withIndex()) {
            fullVals[c - 'a'] = vals[i]
        }
        // 動態規劃
        val n = s.length
        var max = 0
        var pre = 0
        for (i in 1..n) {
            val curValue = fullVals[s[i - 1] - 'a']
            pre = Math.max(curValue, pre + curValue)
            max = Math.max(max, pre)
        }
        return max
    }
}

另一種理解，視為 vals[i] 總與前序子陣列拼接，而前序子陣列的權值不低於 0：

  • $dp[i] = Math.max(dp[i - 1], 0) + vals[i]$
class Solution {
    fun maximumCostSubstring(s: String, chars: String, vals: IntArray): Int {
        // 初值
        val fullVals = IntArray(26) { it + 1}
        // 更新
        for ((i, c) in chars.withIndex()) {
            fullVals[c - 'a'] = vals[i]
        }
        // 動態規劃
        val n = s.length
        var max = 0
        var pre = 0
        for (i in 1..n) {
            pre = Math.max(pre, 0) + fullVals[s[i - 1] - 'a']
            max = Math.max(max, pre)
        }
        return max
    }
}

2607. 使子陣列元素和相等（Medium）

題目地址

https://leetcode.cn/problems/make-k-subarray-sums-equal/

題目描述

給你一個下標從 0 開始的整數陣列 arr 和一個整數 k 。陣列 arr 是一個迴圈陣列。換句話說，陣列中的最後一個元素的下一個元素是陣列中的第一個元素，陣列中第一個元素的前一個元素是陣列中的最後一個元素。

你可以執行下述運算任意次：

  • 選中 arr 中任意一個元素，並使其值加上 1 或減去 1 。

執行運算使每個長度為 k 的 子陣列 的元素總和都相等，返回所需要的最少運算次數。

子陣列 是陣列的一個連續部分。

問題分析

分析 1： 先不考慮迴圈陣列的前提，分析資料約束 「對於滿足每個長度為 k 的子陣列的和相等」，那麼

$a[i]+a[i+1] +…+a[i+k-1] == a[i+1]+a[i+2]+…+a[i+k-1]+a[i+k]$

等式兩邊化簡得：

$a[i]=a[i+k]$

也就是說，陣列上每間隔 k 的元素要相等。因此我們需要將每間隔 k 的元素分為一組，再將組內元素調整為相等值；

分析 2： 如何將組內元素調整為相等值呢？可以證明選擇中位數的貪心做法是最優的。

分析 3： 考慮迴圈陣列的前提，對於 i + k ≥ len(arr) 的情況，需要對陣列下標取模來模擬迴圈

題解一（拼接陣列 + 中位數貪心 · 錯誤）

迴圈陣列有拼接一倍陣列的模擬做法，我們模擬出 2*n 長度的陣列，在存取每個位置時，將所有同組的陣列分為一組，再排序取中位數。

不過，這個思路在這道題裡是不對的，因為同一個分組有可能迴圈多輪才會遇到。即使不考慮錯誤，在這道題的資料範圍上也會記憶體溢位。

錯誤測試用例：$arr = [1, 5, 8, 10], k = 3$

class Solution {
    fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
        val n = arr.size
        var ret = 0L
        // 延長一倍陣列
        val visited = BooleanArray(2 * n)
        for (i in 0 until 2 * n) {
            if (visited[i]) continue
            // 分組
            val bucket = ArrayList<Int>()
            for (j in i until 2 * n step k) {
                bucket.add(arr[j % n])
                visited[j] = true
            }
            // 排序
            Collections.sort(bucket)
            // println(bucket.joinToString())
            // 中位數貪心
            val midVal = bucket[bucket.size / 2]
            for (element in bucket) {
                ret += Math.abs(element - midVal)
            }
        }
        return ret / 2 // 擴充了一倍陣列，所以運算元也翻倍了
    }
}

題解二（陣列分組 + 中位數貪心）

既然不能使用陣列，那麼可以在記憶體迴圈中一直迴圈取同分組為止，直到出現迴環後退出：

class Solution {
    fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
        val n = arr.size
        var ret = 0L
        val visited = BooleanArray(n)
        for (i in 0 until n) {
            if (visited[i]) continue
            // 分組
            val bucket = ArrayList<Int>()
            var j = i
            while (!visited[j]) {
                bucket.add(arr[j % n])
                visited[j] = true
                j = (j + k) % n
            }
            // 排序
            Collections.sort(bucket)
            // 中位數貪心
            val midVal = bucket[bucket.size / 2]
            for (element in bucket) {
                ret += Math.abs(element - midVal)
            }
        }
        return ret
    }
}

複雜度分析：

  • 時間複雜度：$O(nlgn)$ 其中 $n$ 為 $arr$ 陣列長度，每個元素最多存取一次，且排序一次，所以整體時間是 $O(nlgn)$；
  • 空間複雜度：$O(n + lgn)$ 標記陣列空間 + 排序遞迴棧空間。

題解三（裴蜀定理 + 中位數貪心）

根據前文分析，我們需要保證最終陣列是以 $k$ 為迴圈週期的，而回圈陣列本身又是以 $n$ 為迴圈週期的。根據 裴蜀定理 ，如果一個陣列存在週期 $k$ 和週期 $n$，那麼必然存在週期 $gcb(k, n)$，而 $gcb(k, n)$ 必然小於 $n$，我們就將問題變成非迴圈陣列問題。

  • 裴蜀定理：設 a，b 是不全為零的整數，則存在整數 x , y，使得 ax + by = gcb(a,b)
class Solution {
    fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
        val n = arr.size
        // 最大公約數
        val m = gcb(n, k)
        var ret = 0L
        // 最多隻有 m 組
        for (i in 0 until m) {
            // 分組
            val bucket = ArrayList<Int>()
            for (j in i until n step m) {
                bucket.add(arr[j])
            }
            // 排序
            Collections.sort(bucket)
            val midVal = bucket[bucket.size / 2]
            for (element in bucket) {
                ret += Math.abs(element - midVal)
            }
        }

        return ret
    }

    private fun gcb(a: Int, b: Int): Int {
        if (b == 0) return a
        return gcb(b, a % b)
    }
}

複雜度分析：

  • 時間複雜度：$O(nlgn)$ 其中 $n$ 為 $arr$ 陣列長度，每個元素最多存取一次，且排序一次，所以整體時間是 $O(nlgn)$；
  • 空間複雜度：$O(n + lgn)$ 分組空間 + 排序遞迴棧空間，分組空間最大為 $n$；

題解四（裴蜀定理 + 中位數貪心 + 快速選擇）

排序是為了尋找中位數，沒必要對整個分組排序，可以優化為快速選擇，時間複雜度優化到 $O(n)$，Nice！

class Solution {
    fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
        val n = arr.size
        // 最大公約數
        val m = gcb(n, k)
        var ret = 0L
        // 最多隻有 m 組
        for (i in 0 until m) {
            // 分組
            val bucket = ArrayList<Int>()
            for (j in i until n step m) {
                bucket.add(arr[j])
            }
            // 快速選擇
            quickSelect(bucket)
            val midVal = bucket[bucket.size / 2]
            for (element in bucket) {
                ret += Math.abs(element - midVal)
            }
        }
        return ret
    }

    // 快速選擇中位數
    private fun quickSelect(bucket: ArrayList<Int>) {
        val mid = bucket.size / 2
        var left = 0
        var right = bucket.size - 1
        while (true) {
            val pivot = partition(bucket, left, right)
            if (mid == pivot) {
                break
            } else if (pivot < mid) {
                left = pivot + 1
            } else {
                right = pivot - 1
            }
        }
    }

    // return：分割區
    private fun partition(bucket: ArrayList<Int>, left: Int, right: Int): Int {
        var p = left
        for (i in left until right) {
            if (bucket[i] < bucket[right]) {
                bucket.swap(p++, i)
            }
        }
        bucket.swap(p, right)
        return p
    }

    private fun <T> ArrayList<T>.swap(first: Int, second: Int) {
        val temp = this[first]
        this[first] = this[second]
        this[second] = temp
    }

    // 迭代寫法
    private fun gcb(a: Int, b: Int): Int {
        var x = a
        var y = b
        while (y != 0) {
            val temp = x % y
            x = y
            y = temp
        }
        return x
    }
}

複雜度分析：

  • 時間複雜度：$O(n)$ 其中 $n$ 為 $arr$ 陣列長度，每個元素最多存取一次；
  • 空間複雜度：$O(n)$ 分組空間，分組空間最大為 $n$；

相似題目：

2608. 圖中的最短環（Hard）

題目地址

https://leetcode.cn/problems/shortest-cycle-in-a-graph/

題目描述

現有一個含 n 個頂點的 雙向 圖，每個頂點按從 0 到 n - 1 標記。圖中的邊由二維整數陣列 edges 表示，其中 edges[i] = [ui, vi] 表示頂點 ui 和 vi 之間存在一條邊。每對頂點最多通過一條邊連線，並且不存在與自身相連的頂點。

返回圖中 最短 環的長度。如果不存在環，則返回 -1 。

環 是指以同一節點開始和結束，並且路徑中的每條邊僅使用一次。

題解一（列舉邊 + Dijkstra 最短路 + 最小堆）

這道題是 最小環 模板題：給出一個圖，問圖中邊權和最小的環是多大，圖的最小環也稱圍長。

暴力解法：對於每條邊 $(u, v)$，求不經過 $(u,v)$ 邊從 $u$ 到 $v$ 的最短路 $len$，那麼包含 $(u,v)$ 的最短環就是 $len + 1$。列舉所有邊，則所有答案的最小值就是圖的最小環。

class Solution {

    private val INF = Integer.MAX_VALUE

    fun findShortestCycle(n: Int, edges: Array<IntArray>): Int {
        // 建圖
        val graph = Array(n) { ArrayList<Int>() }.apply {
            for (edge in edges) {
                this[edge[0]].add(edge[1])
                this[edge[1]].add(edge[0])
            }
        }
        // 列舉邊
        var ret = INF
        for (edge in edges) {
            ret = Math.min(ret, dijkstra(graph, edge[0], edge[1]))
        }
        return if (INF == ret) -1 else ret
    }

    private fun dijkstra(graph: Array<ArrayList<Int>>, u: Int, v: Int): Int {
        // 最短路長度
        val dis = IntArray(graph.size) { INF }.apply {
            this[u] = 0
        }
        // 最小堆
        val heap = PriorityQueue<Int>() { e1, e2 ->
            dis[e1] - dis[e2]
        }.apply {
            this.offer(u)
        }
        // BFS
        outer@ while (!heap.isEmpty()) {
            // 使用 O(lgn) 找出已選集中最短路長度最小的節點
            val x = heap.poll()
            // 鬆弛相鄰點
            for (y in graph[x]) {
                // 忽略 (u, v) 邊
                if (x == u && y == v) continue
                if (dis[x] + 1 /* 邊權為 1 */ < dis[y]) {
                    dis[y] = dis[x] + 1
                    heap.offer(y)
                }
                // 找到 u -> v 的最短路
                if (y == v) break@outer
            }
        }
        return if(INF == dis[v]) INF else dis[v] + 1
    }
}

複雜度分析：

  • 時間複雜度：$O(m + m^2·lgn)$ 其中 $n$ 為頂點個數，$m$ 為邊個數，每條邊跑 Dijkstra 最短路每輪迭代以 $O(lgn)$ 取出已選集中最短路長度最小的節點，每次 Dijkstra 的時間是 $O(m·lgn)$；
  • 空間複雜度：$O(m + n)$ 圖空間 + 最小堆空間，使用鄰接表可以降低空間到 $O(m + n)$。

題解二（列舉邊 + BFS）

由於這道題的邊權是 1，所以不需要使用高階的圖論演演算法也能做。

為什麼呢，因為每個邊權的長度是 1，所以已經存取過的節點是不會存在更短路徑的。所以我們不需要使用堆，直接使用佇列，最先進入佇列中的節點一定是最短路長度最短的節點。

class Solution {

    private val INF = Integer.MAX_VALUE

    fun findShortestCycle(n: Int, edges: Array<IntArray>): Int {
        // 建圖
        val graph = Array(n) { ArrayList<Int>() }.apply {
            for (edge in edges) {
                this[edge[0]].add(edge[1])
                this[edge[1]].add(edge[0])
            }
        }
        // 列舉邊
        var ret = INF
        for (edge in edges) {
            ret = Math.min(ret, bfs(graph, edge[0], edge[1]))
        }
        return if (INF == ret) -1 else ret
    }

    private fun bfs(graph: Array<ArrayList<Int>>, u: Int, v: Int): Int {
        // 最短路長度
        val dis = IntArray(graph.size) { INF }.apply {
            this[u] = 0
        }
        // 最小堆
        val queue = LinkedList<Int>().apply {
            this.offer(u)
        }
        // BFS
        outer@ while (!queue.isEmpty()) {
            // 取隊頭
            val x = queue.poll()
            // 鬆弛相鄰點
            for (y in graph[x]) {
                // 忽略 (u, v) 邊
                if (x == u && y == v) continue
                // 已經存取過的節點不會存在更短路
                if (INF != dis[y]) continue
                dis[y] = dis[x] + 1
                queue.offer(y)
                // 找到 u -> v 的最短路
                if (y == v) break@outer
            }
        }
        return if (INF == dis[v]) INF else dis[v] + 1
    }
}

複雜度分析：

  • 時間複雜度：$O(m + m^2)$ 在每輪 BFS 中，每條邊最多存取 2 次，因此每輪 BFS 的時間複雜度是 $O(m)$；
  • 空間複雜度：$O(m + n)$。