2025-03-27:统计满足 K 约束的子字符串数量Ⅰ。用go语言,给定一个二进制字符串 s 和一个整数 k,定义满足 k 约

举报
福大大架构师每日一题 发表于 2025/03/27 09:12:33 2025/03/27
【摘要】 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。

大体步骤如下:

  1. 初始化变量:

    • 字符串 s = “1010101”,整数 k = 2。

    • 定义一个长度为 2 的数组 count,用于统计字符 ‘0’ 和 ‘1’ 的数量。

    • 定义结果变量 res 用于存储满足 k 约束的子字符串数量。

    • 定义指针 i 和 j 用于标记子字符串的起始位置和结束位置。

  2. 循环遍历字符串 s:

    • 对于每个字符 s[j],根据其值更新 count 数组中对应的计数值。

    • 判断当前子字符串是否满足 k 约束。如果超出约束,则移动起始指针 i 直到满足约束。

    • 计算当前子字符串满足约束的数量并累加到 res 中。

  3. 返回最终结果 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。