大家好,我是小彭。
这周比较忙,上周末的双周赛题解当初才更新,虽迟但到哈。上周末这场是 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 = 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 = 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 = 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)$。