2025-03-27:统计满足 K 约束的子字符串数量Ⅰ。用go语言,给定一个二进制字符串 s 和一个整数 k,定义满足 k 约
【摘要】 2025-03-27:统计满足 K 约束的子字符串数量Ⅰ。用go语言,给定一个二进制字符串 s 和一个整数 k,定义满足 k 约束的条件为:字符串中 0 的数量不超过 k;字符串中 1 的数量不超过 k。求 s 中满足 k 约束的子字符串数量。1 <= s.length <= 50。1 <= k <= s.length。s[i] 是 ‘0’ 或 ‘1’。输入:s = “1010101”, k...
2025-03-27:统计满足 K 约束的子字符串数量Ⅰ。用go语言,给定一个二进制字符串 s 和一个整数 k,定义满足 k 约束的条件为:
字符串中 0 的数量不超过 k;
字符串中 1 的数量不超过 k。
求 s 中满足 k 约束的子字符串数量。
1 <= s.length <= 50。
1 <= k <= s.length。
s[i] 是 ‘0’ 或 ‘1’。
输入:s = “1010101”, k = 2。
输出:25。
解释:
s 的所有子字符串中,除了长度大于 5 的子字符串外,其余子字符串都满足 k 约束。
题目来自leetcode3258。
大体步骤如下:
-
初始化变量:
-
字符串 s = “1010101”,整数 k = 2。
-
定义一个长度为 2 的数组 count,用于统计字符 ‘0’ 和 ‘1’ 的数量。
-
定义结果变量 res 用于存储满足 k 约束的子字符串数量。
-
定义指针 i 和 j 用于标记子字符串的起始位置和结束位置。
-
-
循环遍历字符串 s:
-
对于每个字符 s[j],根据其值更新 count 数组中对应的计数值。
-
判断当前子字符串是否满足 k 约束。如果超出约束,则移动起始指针 i 直到满足约束。
-
计算当前子字符串满足约束的数量并累加到 res 中。
-
-
返回最终结果 res。
总的时间复杂度:
- 假设字符串 s 的长度为 n,算法的时间复杂度为 O(n)。因为只需遍历一次字符串 s。
总的额外空间复杂度:
- 算法的额外空间复杂度为 O(1)。因为只使用了常数个额外变量和常数个长度为 2 的数组。
这样的实现可以高效地计算满趛 k 约束的子字符串数量。
Go完整代码如下:
package main
import (
"fmt"
)
func countKConstraintSubstrings(s string, k int) int {
n := len(s)
count := [2]int{}
res := 0
i := 0
for j := 0; j < n; j++ {
count[int(s[j]-'0')]++
for count[0] > k && count[1] > k {
count[int(s[i]-'0')]--
i++
}
res += j - i + 1
}
return res
}
func main() {
s := "1010101"
k := 2
result := countKConstraintSubstrings(s, k)
fmt.Println(result)
}
Python完整代码如下:
# -*-coding:utf-8-*-
def count_k_constraint_substrings(s, k):
n = len(s)
count = [0, 0]
res = 0
i = 0
for j in range(n):
count[int(s[j])] += 1
while count[0] > k and count[1] > k:
count[int(s[i])] -= 1
i += 1
res += j - i + 1
return res
s = "1010101"
k = 2
result = count_k_constraint_substrings(s, k)
print(result)
【声明】本内容来自华为云开发者社区博主,不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)