具有k个的总子串-Java 学习之路

给定二进制字符串s，我们需要找到其子字符串的数量，其中包含恰好为“1”的k个字符 .

例如：s =“1010”且k = 1，答案= 6 .

现在，我在累积和数组上使用二进制搜索技术解决了它 .

我还用另一种方法来解决它 . 方法如下：

对于每个位置i，找到在i处结尾的总子串，其中包含正好为k的'1'字符 .
为了找到在i处结尾的总子串，其中包含恰好为1的k个字符，它可以表示为索引j的集合，使得子串j到i恰好包含k'1' . 答案是集合的大小 . 现在，为了找到给定位置i的所有这样的j，我们可以将问题重新解释为找到所有j这样的

从[1]到[j - 1]的1的数量=从1到i的总数 - [从j到i的总数= k] .

即，从[1]到[j-1]的个数= C [i] -k

等于C [j - 1] = C [i] - k，

其中C是累积和数组，其中C [i] =从1到i的字符串的字符总和 . 现在，问题很简单，因为我们可以通过计算总和为C [i] -k的所有前缀来使用等式找到j的所有可能值 .

但我找到了这个解决方案，

int main() {
    cin >> k >> S;
    C[0] = 1;
    for (int i = 0; S[i]; ++i) {
        s += S[i] == '1';
        ++C[s];
    }
    for (int i = k; i <= s; ++i) {
        if (k == 0) {
            a += (C[i] - 1) * C[i] / 2;
        } else {
            a += C[i] * C[i - k];
        }
    }
    cout << a << endl;
    return 0;
}

在代码中，S是给定的字符串，K如上所述，C是累积和数组，a是答案 . 使用乘法的代码是什么，我不知道 . 有人可以解释算法吗？

1 回答

1
如果您看到计算 C[i] 的方式，则 C[i] 表示 i th 1 和 i+1 st 1 之间的字符数 .

如果你举一个例子 S = 1001000
```
C[0] = 1 
                   C[1] = 3 // length of 100
                   C[2] = 4 // length of 1000
```
所以出现疑问， Why multiplication

说你的 K=1 ，那么你想找出只有一个 1 的子串，现在你知道在第一个 1 之后有两个零 since C[1] = 3 . 因此，子串的数量将为3，因为您必须包含此1 .
```
{1,10,100}
```
但是当你来到第二部分时： C[2] =4

现在，如果你看到 1000 并且你知道你可以制作4个子串（等于C [2]）
```
{1,10,100,1000}
```
而且你应该注意到 1 之前有 C[1]-1 零 .

因此，通过包含那些零，您可以创建更多子字符串，在这种情况下，包括 0 一次
```
0{1,10,100,1000}
      => {01,010,0100,01000}
```
和 00 一次
```
00{1,10,100,1000}
      => {001,0010,00100,001000}
```
所以基本上你正在制作 C[i] 以 1 开头的子串，你可以在这个之前追加 i 个零，并制作另一个 C[i] * C[i-k]-1 子串 . i varies from 1 to C[i-k]-1 （-1因为我们想留下最后一个） .
```
((C[i-k]-1)* C[i]) +C[i]
   => C[i-k]*C[i]
```
回复于 2024-04-29T23:31:54+08:00

具有k个的总子串

1 回答

相关问题