给定二进制字符串&"10110".查找所有子串的计数，其位数为设置位数=> n [英] Given a binary string "10110". Find the count of all the substring with number of set bit count >= n

问题描述

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

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

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

解决方案

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

制作两个索引-左和右.

我们要考虑从位置 left 开始的子字符串，其中至少包含 k 个一个.

首先将向右移动，直到位数达到 k .

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

将左递增1，直到下一个一个.

重复右移 等.算法是线性的.

Python示例:

  s ='0010110010'#s ='110010110010'k = 2左= 0右= 0res = 0零=正确时<镜片):而(权利 

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

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

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

解决方案

Answer changed (noticed >= in problem statement).

Make two indices - left and right.

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

At first move right until bit count reaches k.

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.

Increment left by 1 until the next one.

Repeat moving right and so on. Algorithm is linear.

Python example:

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！