Как найти число 010 в определенном диапазоне двоичной строки - PullRequest
Новая
       37

Как найти число 010 в определенном диапазоне двоичной строки

0 голосов
/ 26 июня 2018

Дана двоичная строка.Как найти вхождения "010" в пределах определенного диапазона строки.
Например, у меня есть строка "0100110" .Если заданный диапазон равен 3 7 (индексирование на основе 1), то на выходе будет 4 .Я не мог найти более быстрый способ решить его.

Попытавшись это, я могу решить это в O (N) сложности.Подход таков: сначала я указываю положение всех '1' в пределах определенного диапазона, и, используя эту позицию, я выясню число '0' как вперед, так и вперед.,А затем умножьте число '0' , найденное в спине, на один '1' с числом '0' в найденном в четверти.Затем суммируйте умноженный результат для каждого из '1' в пределах определенного диапазона.

Для данного примера позиция '1' в пределах диапазона составляет {5, 6} .Теперь для индекса 5 у меня число '0' в обоих направлениях равно 2 и 1 соответственно.Таким образом, мы можем сделать подпоследовательность "010" is 2 .Аналогично для индекса 6 мы также получаем ответ 2 .Всего мы можем сделать подпоследовательность "010" всего 4 раз.

Но когда у нас есть ряд Q запросов определенных диапазонов для данной строки, тогда мой подход легко достигает сложности времени O (N 2 ) .Я много пробовал, но не смог найти способ его оптимизировать.Кто-нибудь может мне помочь с подходом, который менее чем O (N 2 ) сложность?Просто упомянуть, что ограничение по времени должно быть 1 секунда .Будет плюсом, если вы предоставите псевдокод.

~ Заранее спасибо.

1 Ответ

0 голосов
/ 26 июня 2018

Предварительная обработка: сделать вспомогательный массив, содержащий кумулятивное число нулей до заданной позиции (с aux [0] = 0) 

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

Для данного L..R сканирования диапазона для единиц, для каждого индекса k 1 получить число нулей в диапазоне - операция O (1) 

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

Таким образом, у нас есть O(R-L) время на запрос и наихудший случай O(Q*N) для Q запросов

Но посмотрите внимательно на формулу: 

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 и LRProd являются константами для данного запроса, и мы должны вычислить суммы 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
...