4

给定一个二进制字符串。如何在字符串的某个范围内查找“010”的出现。
例如，我有字符串"0100110"。如果给定的范围是3 7（基于 1 的索引），那么输出将为4。我找不到任何更快的方法来解决它。

在尝试这个时，我可以在O(N)复杂度中解决它。方法是 - 首先我指出所有“1”在一定范围内的位置，并使用这些位置我将计算来回“0”的数量。然后将后面找到的“0”数乘以单个“1”与第四次找到的“0”数。然后将一定范围内的每个'1'的乘积相加。

对于给定的示例，“1”在范围内的位置是{5, 6}。现在对于索引5，我前后的“0”数分别为2和1。所以我们可以让子序列"010"是2。同样对于索引6我们也得到答案是2。总共我们可以使子序列“010”总共是4次。

但是当我们对给定字符串有一定范围的Q查询时，我的方法很容易达到时间复杂度O(N 2 )。我尝试了很多，但未能找到优化它的方法。任何人都可以用一种小于O(N 2 )复杂度的方法来帮助我吗？顺便提一下时间限制应该是1秒。如果您提供伪代码，那将是一个加号。

〜提前谢谢。

4

1 回答 1

4

预处理：使辅助数组包含到给定位置的累积零数（辅助[0] = 0）

  0 1 0 0 1 1 0  //string
0 1 1 2 3 3 3 4  //aux array A[]

对于给定的范围扫描，对于获取范围内的零个数的L..R每个 k 索引- O(1) 操作1

P[k] = (A[k] - A[L-1]) * (A[R] - A[k])
S = Sum(P[k], k=L..R)

所以我们有每个查询的时间和Q 查询O(R-L)的最坏情况O(Q*N)

但仔细看公式：

P[k] = (A[k] - A[L-1]) * (A[R] - A[k]) = 
       A[k] * (A[R] + A[L-1]) - A[k]^2 - A[R] * A[L-1] = 
       A[k] * LRSum - A[k]^2 - LRProd
S = Sum(A[k] for ones) * LRSum - Sum(A[k]^2) - LRProd * NumOfOnes

请注意，LRSumandLRProd是给定查询的常数，我们必须计算一个位置的 A[k] 和以及相同位置的平方和。似乎我们可以使用累积数组的相同想法并在O(1)每个查询中获取结果。

快速检查(3+3)*5 - (9+9) - 4*2 = 30-18-8 = 4为您提供了示例。

使用累积数组：

  0 1 0 0 1  1  0  //string
0 1 1 2 3 3  3  4  //aux array A[]
0 0 1 1 1 4  7  7  //aux array B[]
0 0 1 1 1 10 19 19  //aux array C[]

Result = (B[R] - B[L-1]) * (A[R] + A[L-1]) - (C[R] - C[L-1]) - 
                 A[R] * A[L-1] * (R - L - 1 - (A[R] - A[L-1])) = 
         (7-1) * (4 + 1) - (19 - 1) - 4 * 1 * (7 - 2  - 4 + 1) = 4
于 2018-06-26T09:08:52.040 回答