本文已收錄到 AndroidFamily，技術(shù)和職場問題，請關(guān)注公眾號(hào) [彭旭銳] 提問。

大家好，我是小彭。

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

周賽大綱

2605.?從兩個(gè)數(shù)字?jǐn)?shù)組里生成最小數(shù)字（Easy）

• 題解一：散列表 $O(n + m)$ 空間
• 題解二：位運(yùn)算 $O(1)$ 空間

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

• 動(dòng)態(tài)規(guī)劃 O(n)

2607.?使子數(shù)組元素和相等（Medium）

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

2608.?圖中的最短環(huán)（Hard）

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

2605.?從兩個(gè)數(shù)字?jǐn)?shù)組里生成最小數(shù)字（Easy）

題目地址

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

題目描述

給你兩個(gè)只包含 1 到 9 之間數(shù)字的數(shù)組?nums1?和?nums2?，每個(gè)數(shù)組中的元素?互不相同?，請你返回?最小?的數(shù)字，兩個(gè)數(shù)組都?至少?包含這個(gè)數(shù)字的某個(gè)數(shù)位。

題解一（散列表）

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

思路：優(yōu)先選擇兩個(gè)數(shù)組交集的最小值，否則取兩個(gè)數(shù)組的最小值再拼接。

class Solution {
    fun minNumber(nums1: IntArray, nums2: IntArray): Int {
        val set1 = nums1.toHashSet()
        val set2 = nums2.toHashSet()
        // 優(yōu)先選擇交集
        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)
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n + m)$ 其中 $n$ 是 $nums1$ 數(shù)組的長度，$m$ 是 $nums2$ 數(shù)組的長度；
• 空間復(fù)雜度：$O(n + m)$ 散列表空間

題解二（位運(yùn)算）

使用二進(jìn)制位標(biāo)記代替散列表

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：最低位連續(xù) 0 的個(gè)數(shù)
        // 交集
        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)
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n + m)$ 其中 $n$ 是 $nums1$ 數(shù)組的長度，$m$ 是 $nums2$ 數(shù)組的長度；
• 空間復(fù)雜度：$O(1)$ 散列表空間

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

題目地址

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

題目描述

給你一個(gè)字符串?s?，一個(gè)字符?互不相同?的字符串?chars?和一個(gè)長度與?chars?相同的整數(shù)數(shù)組?vals?。

子字符串的開銷?是一個(gè)子字符串中所有字符對應(yīng)價(jià)值之和?？兆址拈_銷是?0?。

字符的價(jià)值?定義如下：

• 如果字符不在字符串?chars?中，那么它的價(jià)值是它在字母表中的位置（下標(biāo)從?1?開始）。
  • 比方說，'a'?的價(jià)值為?1?，'b'?的價(jià)值為?2?，以此類推，'z'?的價(jià)值為?26?。
• 否則，如果這個(gè)字符在?chars?中的位置為?i?，那么它的價(jià)值就是?vals[i]?。

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

題解（動(dòng)態(tài)規(guī)劃）

簡單動(dòng)態(tài)規(guī)劃問題。

先根據(jù)題意維護(hù) a-z 每個(gè)字母的開銷，再求 53. 最長子數(shù)組和 問題。

定義 dp[i] 表示以 [i] 為結(jié)尾的最大子數(shù)組和，則有

• 與 $a[0, i - 1]$ 拼接：$dp[i] = dp[i - 1] + vals[i]$
• 不與 $a[i - 1]$ 拼接（單獨(dú)作為子數(shù)組）：$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]
        }
        // 動(dòng)態(tài)規(guī)劃
        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
    }
}

滾動(dòng)數(shù)組優(yōu)化：

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]
        }
        // 動(dòng)態(tài)規(guī)劃
        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] 總與前序子數(shù)組拼接，而前序子數(shù)組的權(quán)值不低于 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]
        }
        // 動(dòng)態(tài)規(guī)劃
        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.?使子數(shù)組元素和相等（Medium）

題目地址

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

題目描述

給你一個(gè)下標(biāo)從?0?開始的整數(shù)數(shù)組?arr?和一個(gè)整數(shù)?k?。數(shù)組?arr?是一個(gè)循環(huán)數(shù)組。換句話說，數(shù)組中的最后一個(gè)元素的下一個(gè)元素是數(shù)組中的第一個(gè)元素，數(shù)組中第一個(gè)元素的前一個(gè)元素是數(shù)組中的最后一個(gè)元素。

你可以執(zhí)行下述運(yùn)算任意次：

• 選中?arr?中任意一個(gè)元素，并使其值加上?1?或減去?1?。

執(zhí)行運(yùn)算使每個(gè)長度為?k?的?子數(shù)組?的元素總和都相等，返回所需要的最少運(yùn)算次數(shù)。

子數(shù)組?是數(shù)組的一個(gè)連續(xù)部分。

問題分析

分析 1： 先不考慮循環(huán)數(shù)組的前提，分析數(shù)據(jù)約束 “對于滿足每個(gè)長度為 k 的子數(shù)組的和相等”，那么

$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]$

也就是說，數(shù)組上每間隔 k 的元素要相等。因此我們需要將每間隔 k 的元素分為一組，再將組內(nèi)元素調(diào)整為相等值；

分析 2： 如何將組內(nèi)元素調(diào)整為相等值呢？可以證明選擇中位數(shù)的貪心做法是最優(yōu)的。

分析 3： 考慮循環(huán)數(shù)組的前提，對于 i + k ≥ len(arr) 的情況，需要對數(shù)組下標(biāo)取模來模擬循環(huán)

題解一（拼接數(shù)組 + 中位數(shù)貪心 · 錯(cuò)誤）

循環(huán)數(shù)組有拼接一倍數(shù)組的模擬做法，我們模擬出 2*n 長度的數(shù)組，在訪問每個(gè)位置時(shí)，將所有同組的數(shù)組分為一組，再排序取中位數(shù)。

不過，這個(gè)思路在這道題里是不對的，因?yàn)橥粋€(gè)分組有可能循環(huán)多輪才會(huì)遇到。即使不考慮錯(cuò)誤，在這道題的數(shù)據(jù)范圍上也會(huì)內(nèi)存溢出。

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

class Solution {
    fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
        val n = arr.size
        var ret = 0L
        // 延長一倍數(shù)組
        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())
            // 中位數(shù)貪心
            val midVal = bucket[bucket.size / 2]
            for (element in bucket) {
                ret += Math.abs(element - midVal)
            }
        }
        return ret / 2 // 擴(kuò)充了一倍數(shù)組，所以操作數(shù)也翻倍了
    }
}

題解二（數(shù)組分組 + 中位數(shù)貪心）

既然不能使用數(shù)組，那么可以在內(nèi)存循環(huán)中一直循環(huán)取同分組為止，直到出現(xiàn)回環(huán)后退出：

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)
            // 中位數(shù)貪心
            val midVal = bucket[bucket.size / 2]
            for (element in bucket) {
                ret += Math.abs(element - midVal)
            }
        }
        return ret
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(nlgn)$ 其中 $n$ 為 $arr$ 數(shù)組長度，每個(gè)元素最多訪問一次，且排序一次，所以整體時(shí)間是 $O(nlgn)$；
• 空間復(fù)雜度：$O(n + lgn)$ 標(biāo)記數(shù)組空間 + 排序遞歸?？臻g。

題解三（裴蜀定理 + 中位數(shù)貪心）

根據(jù)前文分析，我們需要保證最終數(shù)組是以 $k$ 為循環(huán)周期的，而循環(huán)數(shù)組本身又是以 $n$ 為循環(huán)周期的。根據(jù) 裴蜀定理 ，如果一個(gè)數(shù)組存在周期 $k$ 和周期 $n$，那么必然存在周期 $gcb(k, n)$，而 $gcb(k, n)$ 必然小于 $n$，我們就將問題變成非循環(huán)數(shù)組問題。

• 裴蜀定理：設(shè) a，b 是不全為零的整數(shù)，則存在整數(shù) x , y，使得 ax + by = gcb(a,b)

class Solution {
    fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
        val n = arr.size
        // 最大公約數(shù)
        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)
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(nlgn)$ 其中 $n$ 為 $arr$ 數(shù)組長度，每個(gè)元素最多訪問一次，且排序一次，所以整體時(shí)間是 $O(nlgn)$；
• 空間復(fù)雜度：$O(n + lgn)$ 分組空間 + 排序遞歸?？臻g，分組空間最大為 $n$；

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

排序是為了尋找中位數(shù)，沒必要對整個(gè)分組排序，可以優(yōu)化為快速選擇，時(shí)間復(fù)雜度優(yōu)化到 $O(n)$，Nice！

class Solution {
    fun makeSubKSumEqual(arr: IntArray, k: Int): Long {
        val n = arr.size
        // 最大公約數(shù)
        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
    }

    // 快速選擇中位數(shù)
    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：分區(qū)
    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
    }
}

復(fù)雜度分析：

• 時(shí)間復(fù)雜度：$O(n)$ 其中 $n$ 為 $arr$ 數(shù)組長度，每個(gè)元素最多訪問一次；
• 空間復(fù)雜度：$O(n)$ 分組空間，分組空間最大為 $n$；

相似題目：

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

2608.?圖中的最短環(huán)（Hard）

題目地址

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

題目描述

現(xiàn)有一個(gè)含?n?個(gè)頂點(diǎn)的?雙向?圖，每個(gè)頂點(diǎn)按從?0?到?n - 1?標(biāo)記。圖中的邊由二維整數(shù)數(shù)組?edges?表示，其中?edges[i] = [ui, vi]?表示頂點(diǎn)?ui?和?vi?之間存在一條邊。每對頂點(diǎn)最多通過一條邊連接，并且不存在與自身相連的頂點(diǎn)。

返回圖中?最短?環(huán)的長度。如果不存在環(huán)，則返回?-1?。

環(huán)?是指以同一節(jié)點(diǎn)開始和結(jié)束，并且路徑中的每條邊僅使用一次。

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

這道題是 最小環(huán) 模板題：給出一個(gè)圖，問圖中邊權(quán)和最小的環(huán)是多大，圖的最小環(huán)也稱圍長。

暴力解法：對于每條邊 $(u, v)$，求不經(jīng)過 $(u,v)$ 邊從 $u$ 到 $v$ 的最短路 $len$，那么包含 $(u,v)$ 的最短環(huán)就是 $len + 1$。枚舉所有邊，則所有答案的最小值就是圖的最小環(huán)。

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) 找出已選集中最短路長度最小的節(jié)點(diǎn)
            val x = heap.poll()
            // 松弛相鄰點(diǎn)
            for (y in graph[x]) {
                // 忽略 (u, v) 邊
                if (x == u && y == v) continue
                if (dis[x] + 1 /* 邊權(quán)為 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
    }
}

復(fù)雜度分析：

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

題解二（枚舉邊 + BFS）

由于這道題的邊權(quán)是 1，所以不需要使用高級(jí)的圖論算法也能做。

為什么呢，因?yàn)槊總€(gè)邊權(quán)的長度是 1，所以已經(jīng)訪問過的節(jié)點(diǎn)是不會(huì)存在更短路徑的。所以我們不需要使用堆，直接使用隊(duì)列，最先進(jìn)入隊(duì)列中的節(jié)點(diǎn)一定是最短路長度最短的節(jié)點(diǎn)。

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()) {
            // 取隊(duì)頭
            val x = queue.poll()
            // 松弛相鄰點(diǎn)
            for (y in graph[x]) {
                // 忽略 (u, v) 邊
                if (x == u && y == v) continue
                // 已經(jīng)訪問過的節(jié)點(diǎn)不會(huì)存在更短路
                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
    }
}

復(fù)雜度分析：文章來源地址http://www.zghlxwxcb.cn/news/detail-405868.html

• 時(shí)間復(fù)雜度：$O(m + m^2)$ 在每輪 BFS 中，每條邊最多訪問 2 次，因此每輪 BFS 的時(shí)間復(fù)雜度是 $O(m)$；
• 空間復(fù)雜度：$O(m + n)$。

到了這里，關(guān)于LeetCode 雙周賽 101，DP/中心位貪心/裴蜀定理/Dijkstra/最小環(huán)的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！