圆括号改变O(n)算法

Question

如果我有一个由n (和close )括号组成的n长度字符串，当我从左向右遍历该字符串的每个子字符串时，当当前时刻的闭括号比开括号多时，我必须计算每次将close )圆括号更改为open (的次数。

例如:n= 3，s= ) ( )：

%s的所有子字符串都将为[ ), ) (, ) ( ), (, ( ), ) ]

我们必须计算所有的子串，就像在) ( )中我们有close =1和open = 0，close > open因此是count++。现在，当前处理的字符串是( ( )，没有更多的更改要做。类似地，当我们对所有子串执行此操作时，计数将为4。

我写了一个暴力破解代码。我猜想有没有办法用O(n)或者其他的东西，使用堆栈或者动态编程来做到这一点呢？

我的蛮力是这样的: 1.创建给定字符串的每个子串。O(n^2)。2.一次迭代一个子字符串以计算更改。O(n)因此，总复杂度为O(n^3)

Answer 1

O注释没有考虑诸如记账/状态变量等内容，它只与必须处理输入数据的频率有关。如果我没理解错的话，你只需要对每个字符进行一次循环。由于在单次循环期间，没有任何信息可以告诉您更深一层的字符信息，因此除了一次循环遍历整个字符串之外，您绝对别无选择。因此，O(N)是该任务的最佳复杂度。

如果你的"bruteforce代码“循环不止一次(也就是不是O(N))，把它贴在这里，人们就会看了。

Answer 2

通过做一些预计算，这个问题可以在O(n^2)内解决。取大小为n(字符串长度)的左右两个数组。leftindex将存储从s到sindex的所有左括号，同样，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;
}