Скобки изменяют алгоритм O (n) - PullRequest
Новая
       54

Скобки изменяют алгоритм O (n)

0 голосов
/ 15 февраля 2020

Если у меня есть строка длиной n с открытыми ( и закрывающими ) круглыми скобками, и мне нужно посчитать, сколько раз я изменяю закрывающие ) круглые скобки, чтобы открывать ( каждый раз, когда у меня есть больше закрывающих скобок, чем открытых в текущий момент, при обходе слева направо в каждой подстроке этой строки.

Например: n = 3, s = ) ( ):

все подстрока s будет [ ), ) (, ) ( ), (, ( ), ) ]

, которую мы будем считать во всей подстроке, как в ) ( ) у нас есть close = 1 и open = 0, close> open, следовательно count +. Теперь текущая обработанная строка - ( ( ), и больше ничего не нужно делать. Точно так же, когда мы сделаем это для всех подстрок, число будет 4.

Я написал код грубой силы. Я предполагаю, есть ли способ сделать это с помощью стека или динамического программирования c, чтобы сделать в O (N) или что-то в этом роде?

Моя грубая сила выглядит так: 1. Создайте каждую подстроку из данной строки , O (N ^ 2). 2. Итерация по одной подстроке за раз для подсчета изменений. O (n) Следовательно, общая сложность O (n ^ 3)

Ответы [ 2 ]

0 голосов
/ 17 февраля 2020

Проблема может быть решена в O (n ^ 2), выполнив некоторые предварительные вычисления. Возьмите два массива слева и справа от размера n (длина строки). left [index] не будет хранить ни одной левой круглой скобки от s [0] до s [index], аналогично right не будет хранить никакой правой круглой скобки. Таким образом, для вашего примера s = ")()" слева будет [0, 1, 1], а справа будет [1, 1, 2]. Это предварительное вычисление может быть сделано в O (n). Теперь нам нужно выяснить, сколько левых скобок нужно было добавить за каждый интервал (i, j). Таким образом, для каждого интервала и подвести их. Для каждого интервала вычислите это значение, используя предварительно вычисленный массив в O (1). Для итерации каждого интервала нам понадобится O (n ^ 2). Таким образом, общая сложность O (n ^ 2). 

int main(){
    vector<int>prefix_sum_left_parentheisis(1000, 0);
    vector<int>prefix_sum_right_parentheisis(1000, 0);
    string s = ")()";
    int count_left_parenthesis = 0;
    int count_right_parenthesis = 0;

    int index = 0;
    for(auto ch:s) {
        if(ch=='(')
            count_left_parenthesis++;
        else
            count_right_parenthesis++;

        prefix_sum_left_parentheisis[index] = count_left_parenthesis;
        prefix_sum_right_parentheisis[index] = count_right_parenthesis;
        index++;
    }

    auto total = 0;
    for(auto i = 0; i < s.size(); i++) {
        for(auto j = i; j < s.size(); j++) {
            if(i == 0) {
                total += max(0, prefix_sum_right_parentheisis[j] - prefix_sum_left_parentheisis[j]);
            }
            else {
                auto count_left_parenthesis_in_range = prefix_sum_left_parentheisis[j] - prefix_sum_left_parentheisis[i-1];
                auto count_right_parenthesis_in_range = prefix_sum_right_parentheisis[j] - prefix_sum_right_parentheisis[i-1];
                total += max(0,count_right_parenthesis_in_range - count_left_parenthesis_in_range);
            }
        }
    }
    cout << "answer is: " << total;
}
0 голосов
/ 15 февраля 2020

В аннотации O не учитываются такие вещи, как переменные бухгалтерии / состояния и т. Д. c. Это связано только с тем, как часто входные данные должны быть обработаны. Если я правильно поняла вашу задачу, вам просто нужно l oop один раз пройти через каждого персонажа. Поскольку во время этого единственного l oop вам не доступна информация, которая говорит вам что-то о символах, расположенных ниже, у вас нет абсолютно никакого выбора, кроме как один раз l oop пройти по всей строке. Поэтому O (N) - лучшая из возможных сложностей для этой задачи.

Если ваш «код грубой силы» повторяется более одного раза (иначе это не O (N)), опубликуйте его здесь, и люди будут искать.

...