天天看點
傳回

LeetCode 雙周賽 101，動态規劃/中心位貪心/裴蜀定理/最小環

作者：彭旭銳
本文已收錄到 AndroidFamily，技術和職場問題，請關注公衆号 [彭旭銳] 提問。

大家好，我是小彭。

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

LeetCode 雙周賽 101，動态規劃/中心位貪心/裴蜀定理/最小環

周賽大綱

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 ，每個數組中的元素 互不相同 ，請你傳回 最小 的數字，兩個數組都 至少 包含這個數字的某個數位。

LeetCode 雙周賽 101，動态規劃/中心位貪心/裴蜀定理/最小環

題解一（散清單）

簡單模拟題，需要對 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. 找到最大開銷的子字元串

題目位址

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 的所有子字元串中的最大開銷。

LeetCode 雙周賽 101，動态規劃/中心位貪心/裴蜀定理/最小環

題解（動态規劃）

簡單動态規劃問題。

先根據題意維護 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 的 子數組 的元素總和都相等，傳回所需要的最少運算次數。

子數組 是數組的一個連續部分。

LeetCode 雙周賽 101，動态規劃/中心位貪心/裴蜀定理/最小環

問題分析

分析 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；

相似題目：

  • 462. 最小操作次數使數組元素相等 II

2608. 圖中的最短環（Hard）

題目位址

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

題目描述

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

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

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

LeetCode 雙周賽 101，動态規劃/中心位貪心/裴蜀定理/最小環

題解一（枚舉邊 + 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)
動态規劃 Leet
上一篇: 你所不知道Linux下的chattr指令
下一篇: JS實作複選框全選/全取消功能

繼續閱讀