关于后端:LeetCode-双周赛-101DP中心位贪心裴蜀定理Dijkstra最小环

大家好，我是小彭。

这周比较忙，上周末的双周赛题解当初才更新，虽迟但到哈。上周末这场是 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-di...

题目形容

给你两个只蕴含 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-...

题目形容

给你一个字符串 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$；

类似题目：

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 。

环是指以同一节点开始和完结，并且门路中的每条边仅应用一次。

题解一（枚举边 + 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)$。