本文已收录到 AndroidFamily，技能和职场问题，请关注大众号 [彭旭锐] 发问。
大家好，我是小彭。
这周比较忙，上周末的双周赛题解现在才更新，虽迟但到哈。上周末这场是 LeetCode 第 101 场双周赛，全体有点难度，第 3 题好像比第 4 题还难一些。
周赛纲要
2605.从两个数字数组里生成最小数字（Easy）
- 题解一：散列表 O(n+m)O(n + m) 空间
- 题解二：位运算 O(1)O(1) 空间
2606.找到最大开支的子字符串（Medium）
- 动态规划 O(n)
2607.使子数组元素和持平（Medium）
- 题解 1：拼接数组 + 中位数贪心 过错
- 题解 2：数组分组 + 中位数贪心 O(nlgn)O(nlgn)
- 题解 3：裴蜀定理 + 中位数贪心 O(nlgn)O(nlgn)
- 题解 4：裴蜀定理 + 中位数贪心 + 快速挑选 O(n)O(n)
2608.图中的最短环（Hard）
- 题解 1：枚举边 + Dijkstra 最短路 + 最小堆 O(m+m2⋅lgn)O(m + m^2lgn)
- 题解 2：枚举边 + BFS O(m+m2)O(m + m^2)
2605.从两个数字数组里生成最小数字（Easy）
标题地址
leetcode.cn/problems/fo…
标题描绘
给你两个只包括 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)O(n + m) 其间 nn 是 nums1nums1 数组的长度，mm 是 nums2nums2 数组的长度；
- 空间复杂度：O(n+m)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)O(n + m) 其间 nn 是 nums1nums1 数组的长度，mm 是 nums2nums2 数组的长度；
- 空间复杂度：O(1)O(1) 散列表空间
2606.找到最大开支的子字符串（Medium）
标题地址
leetcode.cn/problems/fi…
标题描绘
给你一个字符串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]a[0, i – 1] 拼接：dp[i]=dp[i−1]+vals[i]dp[i] = dp[i – 1] + vals[i]
- 不与 a[i−1]a[i – 1] 拼接（独自作为子数组）：dp[i]=vals[i]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]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）
标题地址
leetcode.cn/problems/ma…
标题描绘
给你一个下标从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+1] +…+a[i+k-1] == a[i+1]+a[i+2]+…+a[i+k-1]+a[i+k]
等式两边化简得：
a[i]=a[i+k]a[i]=a[i+k]
也便是说，数组上每距离 k 的元素要持平。因而咱们需要将每距离 k 的元素分为一组，再将组内元素调整为持平值；
剖析 2： 如何将组内元素调整为持平值呢？能够证明挑选中位数的贪心做法是最优的。
剖析 3： 考虑循环数组的条件，关于 i + k ≥ len(arr) 的状况，需要对数组下标取模来模拟循环
题解一（拼接数组 + 中位数贪心 过错）
循环数组有拼接一倍数组的模拟做法，咱们模拟出 2*n 长度的数组，在拜访每个方位时，将一切同组的数组分为一组，再排序取中位数。
不过，这个思路在这道题里是不对的，因为同一个分组有或许循环多轮才会遇到。即便不考虑过错，在这道题的数据范围上也会内存溢出。
过错测试用例：arr=[1,5,8,10],k=3arr = [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)O(nlgn) 其间 nn 为 arrarr 数组长度，每个元素最多拜访一次，且排序一次，所以全体时刻是 O(nlgn)O(nlgn)；
- 空间复杂度：O(n+lgn)O(n + lgn) 符号数组空间 + 排序递归栈空间。
题解三（裴蜀定理 + 中位数贪心）
依据前文剖析，咱们需要确保终究数组是以 kk 为循环周期的，而循环数组本身又是以 nn 为循环周期的。依据 裴蜀定理 ，假如一个数组存在周期 kk 和周期 nn，那么必定存在周期 gcb(k,n)gcb(k, n)，而 gcb(k,n)gcb(k, n) 必定小于 nn，咱们就将问题变成非循环数组问题。
- 裴蜀定理：设 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)O(nlgn) 其间 nn 为 arrarr 数组长度，每个元素最多拜访一次，且排序一次，所以全体时刻是 O(nlgn)O(nlgn)；
- 空间复杂度：O(n+lgn)O(n + lgn) 分组空间 + 排序递归栈空间，分组空间最大为 nn；
题解四（裴蜀定理 + 中位数贪心 + 快速挑选）
排序是为了寻找中位数，没必要对整个分组排序，能够优化为快速挑选，时刻复杂度优化到 O(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)O(n) 其间 nn 为 arrarr 数组长度，每个元素最多拜访一次；
- 空间复杂度：O(n)O(n) 分组空间，分组空间最大为 nn；
类似标题：
- 462. 最小操作次数使数组元素持平 II
2608.图中的最短环（Hard）
标题地址
leetcode.cn/problems/sh…
标题描绘
现有一个含n个极点的双向图，每个极点按从0到n - 1符号。图中的边由二维整数数组edges表明，其间edges[i] = [ui, vi]表明极点ui和vi之间存在一条边。每对极点最多通过一条边连接，而且不存在与本身相连的极点。
回来图中最短环的长度。假如不存在环，则回来-1。
环是指以同一节点开端和完毕，而且途径中的每条边仅运用一次。
题解一（枚举边 + Dijkstra 最短路 + 最小堆）
这道题是 最小环 模板题：给出一个图，问图中边权和最小的环是多大，图的最小环也称围长。
暴力解法：关于每条边 (u,v)(u, v)，求不经过 (u,v)(u,v) 边从 uu 到 vv 的最短路 lenlen，那么包括 (u,v)(u,v) 的最短环便是 len+1len + 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+m2⋅lgn)O(m + m^2lgn) 其间 nn 为极点个数，mm 为边个数，每条边跑 Dijkstra 最短路每轮迭代以 O(lgn)O(lgn) 取出已选集中最短路长度最小的节点，每次 Dijkstra 的时刻是 O(m⋅lgn)O(mlgn)；
- 空间复杂度：O(m+n)O(m + n) 图空间 + 最小堆空间，运用邻接表能够降低空间到 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+m2)O(m + m^2) 在每轮 BFS 中，每条边最多拜访 2 次，因而每轮 BFS 的时刻复杂度是 O(m)O(m)；
- 空间复杂度：O(m+n)O(m + n)。
本文正在参加「金石方案」
