- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
本文已收录到 AndroidFamily ,技术和职场问题,请关注公众号 [彭旭锐] 和 [BaguTree Pro] 知识星球提问.
T1. 最长奇偶子数组(Easy) 。
T2. 和等于目标值的质数对(Medium) 。
T3. 不间断子数组(Medium) 。
T4. 所有子数组中不平衡数字之和(Hard) 。
https://leetcode.cn/problems/longest-even-odd-subarray-with-threshold/
容易想到的方法是枚举每个位置开始的子数组,并计算最长奇偶子数组长度,可以得到时间复杂度为 O(n^2) 的解法.
class Solution {
fun longestAlternatingSubarray(nums: IntArray, threshold: Int): Int {
var i = 0
var j = 0
val n = nums.size
var ret = 0
while (j < n) {
while (i < n && (nums[i] % 2 != 0 || nums[i] > threshold)) i++
if (i >= n) break
j = i + 1
while (j < n && (nums[j] % 2 != nums[j - 1] % 2 && nums[j] <= threshold)) j++
ret = Math.max(ret, j - i)
i ++
}
return ret
}
}
复杂度分析:
实际上,数组被分割为若干个满足奇偶子数组的片段,最长奇偶子数组不会被其他更长的奇偶子数组所包含。因此,我们不需要枚举所有位置开始的子数组,而是枚举所有片段,修改仅在于于 ++j 修改为 i = j 而已.
class Solution {
fun longestAlternatingSubarray(nums: IntArray, threshold: Int): Int {
var i = 0
var j = 0
val n = nums.size
var ret = 0
while (j < n) {
while (i < n && (nums[i] % 2 != 0 || nums[i] > threshold)) i++
if (i >= n) break
j = i + 1
while (j < n && (nums[j] % 2 != nums[j - 1] % 2 && nums[j] <= threshold)) j++
ret = Math.max(ret, j - i)
i = j // 唯一修改
}
return ret
}
}
复杂度分析:
https://leetcode.cn/problems/prime-pairs-with-target-sum/
先预处理出数据范围内所有质数,再使用两数之和寻找匹配项.
class Solution {
companion object {
private val U = 1000000
private val primes = generatePrime(U)
private val primeSet = primes.toHashSet()
private fun generatePrime(n : Int): LinkedList<Int> {
// 线性筛
val primes = LinkedList<Int>()
val isPrime = BooleanArray(n + 1) { true }
for (e in 2..n) {
if (isPrime[e]) {
primes.add(e)
}
// 标记
for (prime in primes) {
if (prime * e >= n) break
isPrime[prime * e] = false
if (e % prime == 0) break // 保证被最小的质因子标记
}
}
return primes
}
}
fun findPrimePairs(n: Int): List<List<Int>> {
val ret = LinkedList<List<Int>>()
for (x in primes) {
val y = n - x
// 去重
if (y < x) break
if (primeSet.contains(y)) ret.add(listOf(x, y))
}
return ret
}
}
复杂度分析:
根据奇偶数性质,如果 n 为奇数,那么当且仅当 偶数 + 奇数 = 奇数,而在所有质因子中,仅存在唯一的偶数 2。因此,当 n 为奇数时,只需要判断 n - 2 是否为质因子即可,且仅存在唯一的匹配.
class Solution {
companion object {
// 预处理 ...
}
fun findPrimePairs(n: Int): List<List<Int>> {
val ret = LinkedList<List<Int>>()
if (n % 2 == 1) {
if (primeSet.contains(n - 2)) ret.add(listOf(2, n - 2))
return ret
}
for (x in primes) {
val y = n - x
// 去重
if (y < x) break
if (primeSet.contains(y)) ret.add(listOf(x, y))
}
return ret
}
}
复杂度分析:
https://leetcode.cn/problems/continuous-subarrays/
这道题与 1438. 绝对差不超过限制的最长连续子数组 是几乎相同的,区别在于本题固定绝对差至多为 2,且目标结果是方案数而不是最长不间断子数组.
与本周赛 T1 类似,我们使用滑动窗口并维持窗口内的数据特征,从而计算满足条件的子数组方案数。同时我们发现,每个以 nums[i] 为结尾的最长不间断子数组 [i, j],都能提供 j - i + 1 个方案,因此我们只需要求出每段连续的不间断子数组,再累加结果.
class Solution {
fun continuousSubarrays(nums: IntArray): Long {
var i = 0
var ret = 0L
for (j in nums.indices) {
// 收缩左指针
for (k in i until j) {
if (Math.abs(nums[k] - nums[j]) > 2) i = k + 1
}
ret += j - i + 1
}
return ret
}
}
复杂度分析:
题解一中每次移动右指针,都需要枚举窗口元素检查是否满足绝对差至多为 2,最坏情况下时间复杂度是 O(n^2)。为优化时间复杂度,我们使用有序集合,每次仅需要检查集合中的最小值与 nums[j] 的大小关系:
class Solution {
fun continuousSubarrays(nums: IntArray): Long {
var i = 0
var ret = 0L
val tree = TreeMap<Int, Int>()
for (j in nums.indices) {
// 收缩左指针
while (!tree.isEmpty() && (nums[j] - tree.firstKey() > 2 || tree.lastKey() - nums[j] > 2)) {
tree[nums[i]] = tree[nums[i]]!! - 1
if (0 == tree[nums[i]]!!) tree.remove(nums[i])
i++
}
tree[nums[j]] = tree.getOrDefault(nums[j], 0) + 1
ret += j - i + 1
}
return ret
}
}
复杂度分析:
同理,我们使用双堆也可以实现平衡树相同的功能.
class Solution {
fun continuousSubarrays(nums: IntArray): Long {
var ret = 0L
var i = 0
val maxHeap = PriorityQueue<Int>() { i1, i2 ->
nums[i2] - nums[i1]
}
val minHeap = PriorityQueue<Int>() { i1, i2 ->
nums[i1] - nums[i2]
}
for (j in nums.indices) {
// 收缩左指针
while (!maxHeap.isEmpty() && nums[maxHeap.peek()] - nums[j] > 2) {
maxHeap.remove(i)
minHeap.remove(i)
i++
}
while (!minHeap.isEmpty() && nums[j] - nums[minHeap.peek()] > 2) {
maxHeap.remove(i)
minHeap.remove(i)
i++
}
maxHeap.offer(j)
minHeap.offer(j)
ret += maxHeap.size
// ret += j - i + 1
}
return ret
}
}
复杂度分析:
求滑动窗口的极值问题有单调队列的经验解.
在有序集合的解法中,忽略了滑动窗口中元素的顺序关系:当元素 nums[i] 后方出现出现更大的元素时,那么 nums[i] 不可能对滑动窗口的 x - nums[j] 的结果有贡献;同理,当 nums[i] 后方出现更小的元素时,那么 nums[i] 不可能对滑动窗口的 nums[i] - x 的结果有贡献.
对结果没有贡献的元素,应该提前弹出数据结构(在平衡树和堆的解法中,会保留在数据结构中,从而拉低时间复杂度).
class Solution {
fun continuousSubarrays(nums: IntArray): Long {
var ret = 0L
var i = 0
// 从队头到队尾递减(维护滑动窗口的最大值)
val maxQueue = ArrayDeque<Int>()
// 从队头到队尾递增(维护滑动窗口的最小值)
val minQueue = ArrayDeque<Int>()
for (j in nums.indices) {
// 维护单调性
while (!maxQueue.isEmpty() && maxQueue.peekLast() < nums[j]) maxQueue.pollLast()
while (!minQueue.isEmpty() && minQueue.peekLast() > nums[j]) minQueue.pollLast()
maxQueue.offer(nums[j])
minQueue.offer(nums[j])
// 维护滑动窗口极值
while (maxQueue.peekFirst() - minQueue.peekFirst() > 2) {
if (nums[i] == maxQueue.peekFirst()) maxQueue.pollFirst()
if (nums[i] == minQueue.peekFirst()) minQueue.pollFirst()
i++
}
ret += j - i + 1
}
return ret
}
}
复杂度分析:
https://leetcode.cn/problems/sum-of-imbalance-numbers-of-all-subarrays/
题目的不平衡度表示子数组排序后与前驱元素的差值大于 1 的个数(长度为 k 的子数组的最大不平衡度为 k - 1),最直接的做法是先排序再计数。我们可以维护子数组的有序集合,并维护插入前后的不平衡度:
class Solution {
fun sumImbalanceNumbers(nums: IntArray): Int {
var ret = 0
for (i in 0 until nums.size) {
var cnt = 0
val tree = TreeSet<Int>()
for (j in i until nums.size) {
val pivot = nums[j]
val lower = tree.floor(pivot) // 小于等于
val higher = tree.ceiling(pivot) // 大于等于
if (null != lower && null != higher && higher - lower > 1) cnt--
if (null != lower && pivot - lower > 1) cnt++
if (null != higher && higher - pivot > 1) cnt ++
tree.add(pivot)
// 子数组结果
ret += cnt
}
}
return ret
}
}
复杂度分析:
由于我们并不需要得到排序后的数组,而是检查每个元素与前驱的关系,因此对于每个元素 nums[i],我们只需要检查 nums[i] + 1 和 nums[i] - 1 是否存在.
枚举子数组元素 i,并维护不平衡度 cnt:
class Solution {
fun sumImbalanceNumbers(nums: IntArray): Int {
var ret = 0
for (i in 0 until nums.size) {
var cnt = 0
val set = HashSet<Int>()
for (j in i until nums.size) {
val x = nums[j]
// 维护不平衡度
if (!set.contains(x)) {
cnt++
if (set.contains(x + 1)) cnt--
if (set.contains(x - 1)) cnt--
set.add(nums[j])
}
// 子数组结果
ret += cnt - 1 // 减 1 是因为最后一个元素不会构造不平衡度
}
}
return ret
}
}
复杂度分析:
思路参考: https://leetcode.cn/problems/sum-of-imbalance-numbers-of-all-subarrays/solutions/2327213/onde-by-dengyun-yyl3/ 。
好棒的思维! 。
使用逆向思维,我们考虑每个元素 nums[i] 能够贡献的不平衡度,以 nums[i] 为中心点向左右扩展直到遇到最近的 nums[i] - 1,使用乘法原理可以计算出 nums[i] 对多少个子数组产生贡献度.
需要考虑到,如果 nums[i] 是作为子数组的最小值时,是不会产生贡献度的,所以我们要把这部分子数组减去。然而,在使用乘法原理时我们无法方便地知道 nums[i] 在子数组中排序的位置,也就无法知道应该减去多少无效子数组。使用整体思维,我们先忽略无效子数组,同时发现每个子数组中都会存在一个最小值,因此整体来看无效子数组的个数就是子数组的个数,即 N*(N+1)/2; 。
同时,为了优化时间复杂度,我们可以在第一次线性遍历中预处理出以 nums[i] 开始的后缀中最近的 nums[i] - 1 的位置。在第二次线性遍历中求出以 nums[i] 为中点的前缀中的最近 nums[i] - 1 的位置.
最后还有一个细节,考虑到存在重复数的测试用例 [2,3,1,4,3],排序后 [1,2,3,3,4] 中只有最左边的 3 会贡献不平衡度。为了避免重复计算,我们规定排序后最左边的 3 来自于当前子数组中最右边的 3,因此在预处理后缀数组时,我们要使用 Math.min(ids[nums[i]], ids[nums[i] - 1]) 来中断遍历.
class Solution {
fun sumImbalanceNumbers(nums: IntArray): Int {
val n = nums.size
// 前缀数组和后缀数组
// ids:记录每个元素最近出现位置
var ids = IntArray(n + 1) { n }
val prefix = IntArray(n + 1) { -1 }
val suffix = IntArray(n + 1) { n }
// 预处理后缀数组
for (i in n - 1 downTo 0) {
suffix[i] = Math.min(ids[nums[i]], ids[nums[i] - 1])
ids[nums[i]] = i
}
// 预处理前缀数组
ids = IntArray(n + 1) { -1 }
for (i in 0 until n) {
prefix[i] = ids[nums[i] - 1]
ids[nums[i]] = i
}
// 乘法原理
var ret = 0
for (i in 0 until n) {
ret += (i - prefix[i]) * (suffix[i] - i)
}
return ret - n * (n + 1) / 2
}
}
在计算前缀数组时累加结果:
class Solution {
fun sumImbalanceNumbers(nums: IntArray): Int {
val n = nums.size
// 前缀数组和后缀数组
// ids:记录每个元素最近出现位置
var ids = IntArray(n + 1) { n }
var prefix = -1
val suffix = IntArray(n + 1) { n }
// 预处理后缀数组
for (i in n - 1 downTo 0) {
suffix[i] = Math.min(ids[nums[i]], ids[nums[i] - 1])
ids[nums[i]] = i
}
// 预处理前缀数组 + 乘法原理
var ret = 0
ids = IntArray(n + 1) { -1 }
for (i in 0 until n) {
prefix = ids[nums[i] - 1]
ids[nums[i]] = i
ret += (i - prefix) * (suffix[i] - i)
}
return ret - n * (n + 1) / 2
}
}
复杂度分析:
最后此篇关于LeetCode周赛352(2023/07/02)一场关于子数组的专题周赛的文章就讲到这里了,如果你想了解更多关于LeetCode周赛352(2023/07/02)一场关于子数组的专题周赛的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我有这个 html 代码: HELLO WORLD! X V HELLO WORLD! X V 我想按 X(类关闭)将父 div 的高度更改为 20px 并显示 V(类打开),但在每个 d
在会计应用程序的许多不同实现中,有两种主要的数据库设计方法来保存日志和分类帐数据。 只保留 Journal 信息,然后 Ledger 只是 Journal 的一个 View (因为 journal 总
我想在另一个子里面有一个子, sub a { sub b { } } 我想为每次调用 sub b 创建一个新的 sub a 实例。有没有办法在 Perl 中做到这一点? 当我运行上面的
我有一些代码正在查找重复项并突出显示单元格: Private Sub cmdDups_Click() Dim Rng As Range Dim cel As Range Set Rng = ThisW
可能有一个简单的解决方案,但我很难过。 我有一个包含一个 ID 字段的主表。在两个可能的字段中有一个具有该 ID 的子表。想象一个由选手 A 和选手 B 组成的 double 队。Master 表将有
假设我有一个包含对象的数组: [ { "id": "5a97e047f826a0111b754beb", "name": "Hogwarts", "parentId": "
我正在尝试对 MySQL 数据库表执行一对父/子模型的批量插入,但似乎无法使用标准的 ActiveRecord 功能来完成。所以,我尝试了 activerecord-import gem,但它也不支持
我有一个带有多个子类的父抽象类。最终,我希望通过 GUI 中的进度条显示子类中完成的进度。 我目前所做的,我意识到这是行不通的,是在父类中声明为每个子类将覆盖的虚拟方法的事件方法定义。所以像: pub
是否可以通过键数组在对象中设置变量?例如我有这个对象: var obj = {'outer': {'inner': 'value'} }; 并希望设置由键数组选择的值: var keys = ['ou
我有一个名为 companies 的 MySQL 表,如下所示: +---------+-----------+-----------+ | id_comp | comp_name | id_pare
我正在尝试使用 sublime text 在 sublime text 上的 ionic 上打开我的第一个应用程序。它给了我一个“找不到命令”的错误。如何修复? 我试过这些命令: sudo rm -r
不好意思问,但我正在使用 webapp2,我正在设计一个解决方案,以便更容易定义路由 based on this google webapp2 route function .但这完全取决于能够在子级
我有代表树的数字字符串(我不知道是否有官方名称): 012323301212 上面的例子代表了 2 棵树。根用 0 表示。根的直接子代为“1”,“1”的直接子代为“2”,依此类推。我需要将它们分组到由
是否可以在当前 Activity 之上添加 Activity 。例如,假设我单击一个按钮,然后它将第二个 Activity 添加到当前 Activity 。而第二个 Activity 只覆盖了我当前
我很难思考如何为子资源建模。 以作者的书籍为例。你可以有 N 本书,每本书只有一位作者。 /books GET /books POST /books/id PUT /books/id DELETE 到
有人可以向我解释以下内容(python 2.7) 来自已解析文件的两个字符串数字: '410.9''410.9 '(注意尾随空格) A_LIST = ['410.9 '] '410.9' in '41
背景 在 PowerShell 中构建 hash table 是很常见的通过特定属性快速访问对象,例如以 LastName 为基础建立索引: $List = ConvertFrom-Csv @' I
我真的很难弄清楚如何调用嵌套 Polymer Web 组件的函数。 这是标记: rise-distribution组件有 canPlay我想从 rise-playlist
我写了一个小工具转储(以 dot 格式)一个项目的依赖关系图,其中所有位于同一目录中的文件都聚集在一个集群中。当我尝试生成包含相应图形的 pdf 时,dot开始哭: 命令 dot -Tpdf trim
给定一个 CODE ref,是否可以: 访问该 CODE ref 的解析树 通过指定 CODE ref 的解析树来创建一个新的 CODE ref,该解析树可以包含在 1 中返回的解析树的元素 通常我们
我是一名优秀的程序员,十分优秀!