> 科技资讯 > LeetCode 双周赛 101,DP/中心位贪心/裴蜀定理/Dijkstra/最小环

LeetCode 双周赛 101,DP/中心位贪心/裴蜀定理/Dijkstra/最小环

科技资讯 投稿 5600℃ 0 评论

LeetCode 双周赛 101,DP/中心位贪心/裴蜀定理/Dijkstra/最小环

本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。

这周比较忙，上周末的双周赛题解现在才更新，虽迟但到哈。上周末这场是 LeetCode 第 101 场双周赛，整体有点难度，第 3 题似乎比第 4 题还难一些。

周赛大纲

    题解一：散列表 $O(n + m$ 空间
  • 题解二：位运算 $O(1$ 空间

2606. 找到最大开销的子字符串（Medium）

    动态规划 O(n

    题解 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）

题目地址

题目描述

给你两个只包含 1 到 9 之间数字的数组 nums1 和 nums2 ，每个数组中的元素 互不相同 ，请你返回 最小 的数字，两个数组都 至少 包含这个数字的某个数位。

题解一（散列表）

思路：优先选择两个数组交集的最小值，否则取两个数组的最小值再拼接。

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）

题目地址

题目描述

给你一个字符串 s ，一个字符 互不相同 的字符串 chars 和一个长度与 chars 相同的整数数组 vals 。

子字符串的开销 是一个子字符串中所有字符对应价值之和。空字符串的开销是 0 。

字符的价值 定义如下：

    如果字符不在字符串 chars 中，那么它的价值是它在字母表中的位置（下标从 1 开始）。
    • 比方说，'a' 的价值为 1 ，'b' 的价值为 2 ，以此类推，'z' 的价值为 26 。
  • 否则，如果这个字符在 chars 中的位置为 i ，那么它的价值就是 vals[i] 。

s 的所有子字符串中的最大开销。

题解（动态规划）

先根据题意维护 a-z 每个字母的开销，再求 53. 最长子数组和 问题。

    与 $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 的子数组的和相等”，那么

等式两边化简得：

也就是说，数组上每间隔 k 的元素要相等。因此我们需要将每间隔 k 的元素分为一组，再将组内元素调整为相等值；

分析 2： 如何将组内元素调整为相等值呢？可以证明选择中位数的贪心做法是最优的。

分析 3： 考虑循环数组的前提，对于 i + k ≥ len(arr 的情况，需要对数组下标取模来模拟循环

题解一（拼接数组 + 中位数贪心 · 错误）

不过，这个思路在这道题里是不对的，因为同一个分组有可能循环多轮才会遇到。即使不考虑错误，在这道题的数据范围上也会内存溢出。

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$ 标记数组空间 + 排序递归栈空间。

题解三（裴蜀定理 + 中位数贪心）

    裴蜀定理：设 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$；

题解四（裴蜀定理 + 中位数贪心 + 快速选择）

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）

题目地址

题目描述

现有一个含 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，所以已经访问过的节点是不会存在更短路径的。所以我们不需要使用堆，直接使用队列，最先进入队列中的节点一定是最短路长度最短的节点。

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

编程笔记 » LeetCode 双周赛 101,DP/中心位贪心/裴蜀定理/Dijkstra/最小环

赞同 (31) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽