string - 如何在二进制字符串的某个范围内找到010的数量
问题描述
给定一个二进制字符串。如何在字符串的某个范围内查找“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秒。如果您提供伪代码,那将是一个加号。
〜提前谢谢。
解决方案
预处理:使辅助数组包含到给定位置的累积零数(辅助[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
请注意,LRSum
andLRProd
是给定查询的常数,我们必须计算一个位置的 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
推荐阅读
- python - Python:如何创建一组元组?
- spring-boot - 如何在同一个应用程序中创建具有客户端和服务器的 RSocket 应用程序?
- swift - 如何拥有一个运行数据库请求并从视图返回变量的 Swift 文件
- xamarin - Xamarin - 将文件下载到用户选择的特定目录
- excel - Excel VBA从两个日期在表格中创建和添加多行
- android - 数据未上传到 Firebase 数据库 (Android Studio)
- charts - 如何在谷歌图表上显示具有相同 x 和 y 的多个数据点的信息的工具提示
- java - MAVEN 无法解决依赖关系
- python - 将向量 Numpy 与不同的 Datetime 对象进行比较
- mysql - 使用 uuid 作为默认值时如何使用 LAST_INSERT_ID()?