本文介绍了给定二进制字符串"10110".查找所有子串的计数,其中设置位数=> n的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我们可以用蛮力解决这个问题,获取所有可能的子字符串,并检查设置的位数是否大于n.

We could solve this question in brute force, taking all possible substrings and checking if the set bit count is greater n.

我被要求在o(n)中解决这个问题.我在o(n)中找不到任何可以解决这个问题的答案.

I was asked to solve this in o(n). I could not find any answer which could achieve this in o(n).

是否有可能在0(n)中获得二进制字符串的所有可能的子字符串?

Is it possible to get all possible substrings of binary string in 0(n)?

推荐答案

答案已更改(在问题陈述中注意到 >=).

Answer changed (noticed >= in problem statement).

制作两个索引-leftright.

我们要考虑从位置left开始至少包含k ones的子字符串.

We want to account substrings starting from position left containing at least k ones.

首先移动right,直到位数达到k.

At first move right until bit count reaches k.

现在,我们有一些好"的提示了.子字符串从left开始并在right之后的任何位置结束,因此我们可以在结果中添加len(s) - right + 1.

Now we have some "good" substrings starting at left and ending in any position after right, so we can add len(s) - right + 1 to result.

left递增1,直到下一个one.

Increment left by 1 until the next one.

重复移动right,依此类推.算法是线性的.

Repeat moving right and so on. Algorithm is linear.

Python示例:

s = '0010110010'
#s = '110010110010'
k = 2
left = 0
right = 0
res = 0
cnt = 0
while right < len(s):
    while (right < len(s)) and (cnt < k):
        if s[right] == "1":
            cnt += 1
        right +=1
    while (left <= right) and (cnt >= k):
        addend = len(s) + 1 - right
        res += addend
        print(left, right, addend, res)  #intermediate debug output
        if s[left] == "1":
            cnt -= 1
        left +=1
print(res)

0 5 6 6
1 5 6 12
2 5 6 18
3 6 5 23
4 6 5 28
5 9 2 30
30

这篇关于给定二进制字符串"10110".查找所有子串的计数,其中设置位数=> n的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

10-19 03:04