欢迎光临
我们一直在努力

【Go语言LeetCode刷题手记|第三天】713. 乘积小于 K 的子数组 3258. 统计满足 K 约束的子字符串数量 I

目录

前言

713. 乘积小于 K 的子数组 – 力扣(LeetCode)

3258. 统计满足 K 约束的子字符串数量 I – 力扣(LeetCode)

总结


前言

今天我们来到不定长滑动窗口。


713. 乘积小于 K 的子数组 – 力扣(LeetCode)

给你一个整数数组 nums 和一个整数 k ,请你返回子数组内所有元素的乘积严格小于 k 的连续子数组的数目。

我们注意到nums[i]是大于等于1的,也就是说如果k<=1的话,直接返回0即可。

这道题目最巧妙的地方在于,我们枚举右端点right,如果找到了符合条件,也就是乘积小于k的子数组时,这时候从[left, right],[left+1,right],……,一直到[right,right]都是符合条件的子数组,因为窗口越缩短乘积就越小,连[left, right]都符合了更不要说后面的[left+1,right],……,一直到[right,right]了,因此我们的结果ans应该加上right-left+1,为什么要加1呢?我们可以代数来进行判断,比如left是1,right是2,这时候应该有[1,2]和[2]两个子数组(这里1,2是索引),所以是2-1+1=2,搞不清楚要不要加一的时候就可以用这种特殊值的方法来判断要不要加一。代码:

func numSubarrayProductLessThanK(nums []int, k int) int {
if k <= 1 {
return 0 // 如果k<=1永远不可能存在子数组,直接返回0
}
ans := 0 // 暂存结果初始化为0
left := 0 // 左端点
pro := 1 // 暂存乘积
for right, x := range nums {
pro *= x // 更新成绩,x进入窗口

for pro >= k { // 如果 乘积大于等于k 则缩小窗口
pro /= nums[left]
left++
}
ans += right-left+1 // 乘积小于k时,记录子数组的数量
}
return ans
}

如果我们没主要到k <= 1的时候没有结果就会产生越界的情况

如果不显式判断的话,我们应该怎么写呢?只需要在缩小窗口时加上一个判断left <= right 即可。如下图:

func numSubarrayProductLessThanK(nums []int, k int) int {
ans := 0 // 暂存结果初始化为0
left := 0 // 左端点
pro := 1 // 暂存乘积
for right, x := range nums {
pro *= x // 更新成绩,x进入窗口

for pro >= k && left <= right{ // 如果 乘积大于等于k 则缩小窗口,left严格小于等于right否则越界
pro /= nums[left]
left++
}
ans += right-left+1 // 乘积小于k时,记录子数组的数量
}
return ans
}

  • 时间复杂度:O(n),其中 n 为 nums 的长度。虽然写了个二重循环,但是内层循环中对 left 加一的总执行次数不会超过 n 次,所以总的时间复杂度为 O(n)。
  • 空间复杂度:O(1),仅用到若干额外变量。

3258. 统计满足 K 约束的子字符串数量 I – 力扣(LeetCode)

给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件,则认为该字符串满足 k 约束:

  • 字符串中 0 的数量最多为 k。
  • 字符串中 1 的数量最多为 k。

返回一个整数,表示 s 的所有满足 k 约束 的子字符串的数量。

这道题目是一个简单题,但是我调试了半天都没过,因为我没有认真审题,注意题目里“如果一个 二进制字符串 满足以下任一条件”,任一条件,我以为要全部满足,所以一直跟样例差几个,这道题没什么好说的,也是和上一道题目一样,我们用cnt1和cnt0来记录1和0的数量,如果两个条件都不满足时,我们就缩小窗口,如果满足条件了,那么此时从[left, right],[left+1,right],……,一直到[right,right]都是符合条件的,跟上题是一个套路。我们直接看代码,这里没写注释,因为如果理解了上题的思路再做这题就是降维打击,我们直接看代码也可以理解:

func countKConstraintSubstrings(s string, k int) int {
left := 0
cnt1, cnt0 := 0, 0
ans := 0
for right, ch := range s {
if ch == '1' {
cnt1++
}else {
cnt0++
}
for cnt0 > k && cnt1 > k {
out := s[left]
if out == '1' {
cnt1–
}else {
cnt0–
}
left++
}
ans += right-left+1
}
return ans
}

  • 时间复杂度:O(n),其中 n 是 s 的长度。注意 left 只会增加不会减少,所以二重循环的时间复杂度为 O(n)。
  • 空间复杂度:O(1)。

总结

我们前两期刷了定长滑动窗口,今天做了两道不定长滑动窗口,可以看见这些题目都是有套路的,按照模板一步一步分析题目即可ac。

如果我的内容对你有帮助,请点赞,评论,收藏。创作不易,大家的支持就是我坚持下去的动力!

赞(0)
未经允许不得转载:171主机测评 » 【Go语言LeetCode刷题手记|第三天】713. 乘积小于 K 的子数组 3258. 统计满足 K 约束的子字符串数量 I
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址